【cf467C】George and Job

2014年9月19日1,1391

The new ITone 6 has been released recently and George got really keen to buy it. Unfortunately, he didn’t have enough money, so George was going to work as a programmer. Now he faced the following problem at the work.

Given a sequence of n integers p1, p2, …, pn. You are to choose k pairs of integers:

[l1, r1], [l2, r2], …, [lk, rk] (1 ≤ l1 ≤ r1 < l2 ≤ r2 < … < lk ≤ rk ≤ nri - li + 1 = m), 
in such a way that the value of sum is maximal possible. Help George to cope with the task.

Input

The first line contains three integers n, m and k (1 ≤ (m × k) ≤ n ≤ 5000). The second line contains n integers p1, p2, …, pn (0 ≤ pi ≤ 109).

Output

Print an integer in a single line — the maximum possible value of sum.

Sample test(s)
input

output

input

output

题解

直接dp。。。二维+前缀和搞搞就好

 

  • caozy6232014年9月19日 下午12:22 回复

    代码好像复制错了吧

    #1