DP....
C. George and Job
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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:
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
5 2 1 1 2 3 4 5
output
9
input
7 1 3 2 10 7 18 5 33 0
output
61
/**
* Created by ckboss on 14-9-19.
*/
import java.util.*;
public class GeorgeandJob {
static int n,m,k;
static long[] a = new long[5050];
static long[] sum = new long[5050];
static long[][] dp = new long[5050][3];
public static void main(String[] args){
Scanner in = new Scanner(System.in);
n=in.nextInt(); m=in.nextInt(); k=in.nextInt();
for(int i=1;i<=n;i++){
a[i]=in.nextInt();
sum[i]=sum[i-1]+a[i];
}
for(int i=m;i<=n;i++){
dp[i][1]=Math.max(dp[i-1][1],sum[i]-sum[i-m]);
}
for(int j=2;j<=k;j++){
for(int i=j*m;i<=n;i++){
dp[i][j%2]=Math.max(dp[i-m][(j-1)%2]+sum[i]-sum[i-m],dp[i-1][j%2]);
}
}
long ans=0;
for(int i=k*m;i<=n;i++){
ans=Math.max(ans,dp[i][k%2]);
}
System.out.println(ans);
}
}