Sum of maxes - MarisaOJ: Marisa Online Judge

Sum of maxes

Time limit: 2000 ms
Memory limit: 512 MB
Given a sequence $a_1, a_2, \ldots, a_n$ of $n$ numbers. The cost of a consecutive segment $l, r$ is the maximum value among $a_l,a_{l+1},...,a_r$. Divide the sequence into $k$ consecutive segments such that the total cost of the segments is minimized. ### Input - The first line contains two positive integers $n, k.$ - The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n.$ ### Output - Print the result of the problem. ### Constraints - $ 1 \le n \le 200000.$ - $1 \le a_1,a_2,...,a_n \le 10^6.$ - $1 \le k \le 500.$ ### Example Input ``` 5 2 1 2 3 4 5 ``` Output ``` 6 ```
Topic
Data structure
Dynamic Programming
Rating 1800
Source IZHO
Solution (0) Solution