Maximum subsequence value - MarisaOJ: Marisa Online Judge

Maximum subsequence value

Time limit: 1000 ms
Memory limit: 256 MB
The value of a sequence $B$ of $m$ elements is $1 \times B_1 + 2 \times B_2 + ... + m \times B_m$. Given an array $A$ of $n$ integers, find a subsequences of $k$ elements so that: - The indices of two consecutive chosen elements differ no more than $m$. - The value of the subsequence is maximum. ### Input - The first line contains three integers $n,m,k$. - The second line contains $n$ integer $A_i$. ### Output - Print the maximum value of the sequence. ### Constraints - $1 \le n,m \le 10^5$. - $1 \le k \le min(n,200)$. - $1 \le A_i \le 10^9$. ### Example Input: ``` 7 2 3 1 9 2 4 5 3 7 ``` Output: ``` 35 ```