A9614. George and Job
编程题
普及/提高-
知识点
题目描述
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 $p_{1},p_{2},...,p_{n}$ . You are to choose $k$ pairs of integers:
$[l_{1},r_{1}],[l_{2},r_{2}],...,[l_{k},r_{k}] (1<=l_{1}<=r_{1}<l_{2}<=r_{2}<...<l_{k}<=r_{k}<=n; r_{i}-l_{i}+1=m),$ in such a way that the value of sum  is maximal possible. Help George to cope with the task.
Given a sequence of $n$ integers $p_{1},p_{2},...,p_{n}$ . You are to choose $k$ pairs of integers:
$[l_{1},r_{1}],[l_{2},r_{2}],...,[l_{k},r_{k}] (1<=l_{1}<=r_{1}<l_{2}<=r_{2}<...<l_{k}<=r_{k}<=n; r_{i}-l_{i}+1=m),$ in such a way that the value of sum  is maximal possible. Help George to cope with the task.
输入格式
The first line contains three integers $n$ , $m$ and $k$ $(1<=(m×k)<=n<=5000)$ . The second line contains $n$ integers $p_{1},p_{2},...,p_{n}$ $(0<=p_{i}<=10^{9})$ .
输出格式
Print an integer in a single line — the maximum possible value of sum.
输入输出样例
输入 #1
5 2 1 1 2 3 4 5
输出 #1
9
输入 #2
7 1 3 2 10 7 18 5 33 0
输出 #2
61