#include<stdio.h>
#define INF -6e12
/*
C. George and Job
http://c...content-available-to-author-only...s.com/problemset/problem/467/C
*/
typedef long long int LL;
int n,m;
LL sum[5005];
LL arr[5005];
LL memo[5005][5005];
char calculated[5005][5005];
LL MAX(LL a,LL b)
{
return a > b ? a : b;
}
LL dp(int index,int k)
{
// Meaning that we have crossed the array boundary but we still have some
// m sized ranges to consider.
if(index > n-m && k > 0)
return INF;
// All the k ranges have been considered for the sum. No need to recurse further.
if(k == 0)
return 0;
// If the result for this subproblem has already been calculated, then return the result
if(calculated[index][k] == 1)
return memo[index][k];
LL ans1,ans2;
// Do not consider the current range. Move on to the next one
ans1=dp(index+1,k);
// Consider the current range and recurse on the next non overlapping range.
ans2=dp(index+m,k-1) + sum[index];
calculated[index][k]=1;
memo[index][k]=MAX(ans1,ans2);
return MAX(ans1,ans2);
}
int main()
{
int i,k;
scanf("%d%d%d",&n
,&m
,&k
);
for(i=0;i<n;i++)
for(i=0;i<m;i++)
sum[0]+=arr[i];
for(i=1;i<=(n-m);i++)
{
sum[i]=sum[i-1];
sum[i]-= arr[i-1];
sum[i]+= arr[m+i-1];
}
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2RlZmluZSBJTkYgLTZlMTIKCi8qCkMuIEdlb3JnZSBhbmQgSm9iCmh0dHA6Ly9jLi4uY29udGVudC1hdmFpbGFibGUtdG8tYXV0aG9yLW9ubHkuLi5zLmNvbS9wcm9ibGVtc2V0L3Byb2JsZW0vNDY3L0MKKi8KCnR5cGVkZWYgbG9uZyBsb25nIGludCBMTDsKCmludCBuLG07CgpMTCBzdW1bNTAwNV07CkxMIGFycls1MDA1XTsKTEwgbWVtb1s1MDA1XVs1MDA1XTsKY2hhciBjYWxjdWxhdGVkWzUwMDVdWzUwMDVdOwoKTEwgTUFYKExMIGEsTEwgYikKewoJcmV0dXJuIGEgPiBiID8gYSA6IGI7Cn0KCkxMIGRwKGludCBpbmRleCxpbnQgaykKewoJLy8gTWVhbmluZyB0aGF0IHdlIGhhdmUgY3Jvc3NlZCB0aGUgYXJyYXkgYm91bmRhcnkgYnV0IHdlIHN0aWxsIGhhdmUgc29tZSAKCS8vIG0gc2l6ZWQgcmFuZ2VzIHRvIGNvbnNpZGVyLgoJaWYoaW5kZXggPiBuLW0gJiYgayA+IDApCglyZXR1cm4gSU5GOwoJCgkvLyBBbGwgdGhlIGsgcmFuZ2VzIGhhdmUgYmVlbiBjb25zaWRlcmVkIGZvciB0aGUgc3VtLiBObyBuZWVkIHRvIHJlY3Vyc2UgZnVydGhlci4KCWlmKGsgPT0gMCkKCXJldHVybiAwOwoJCgkvLyBJZiB0aGUgcmVzdWx0IGZvciB0aGlzIHN1YnByb2JsZW0gaGFzIGFscmVhZHkgYmVlbiBjYWxjdWxhdGVkLCB0aGVuIHJldHVybiB0aGUgcmVzdWx0CglpZihjYWxjdWxhdGVkW2luZGV4XVtrXSA9PSAxKQoJcmV0dXJuIG1lbW9baW5kZXhdW2tdOwoJCglMTCBhbnMxLGFuczI7CgkKCS8vIERvIG5vdCBjb25zaWRlciB0aGUgY3VycmVudCByYW5nZS4gTW92ZSBvbiB0byB0aGUgbmV4dCBvbmUKCWFuczE9ZHAoaW5kZXgrMSxrKTsKCQoJLy8gQ29uc2lkZXIgdGhlIGN1cnJlbnQgcmFuZ2UgYW5kIHJlY3Vyc2Ugb24gdGhlIG5leHQgbm9uIG92ZXJsYXBwaW5nIHJhbmdlLgoJYW5zMj1kcChpbmRleCttLGstMSkgKyBzdW1baW5kZXhdOwoJCgljYWxjdWxhdGVkW2luZGV4XVtrXT0xOwoJbWVtb1tpbmRleF1ba109TUFYKGFuczEsYW5zMik7CglyZXR1cm4gTUFYKGFuczEsYW5zMik7Cn0KCmludCBtYWluKCkKewoJaW50IGksazsKCQoJc2NhbmYoIiVkJWQlZCIsJm4sJm0sJmspOwoJCglmb3IoaT0wO2k8bjtpKyspCglzY2FuZigiJWxkIiwmYXJyW2ldKTsKCQoJZm9yKGk9MDtpPG07aSsrKQoJc3VtWzBdKz1hcnJbaV07CgkKCWZvcihpPTE7aTw9KG4tbSk7aSsrKQoJewoJCXN1bVtpXT1zdW1baS0xXTsKCQkKCQlzdW1baV0tPSBhcnJbaS0xXTsKCQlzdW1baV0rPSBhcnJbbStpLTFdOwoJfQoJCglwcmludGYoIiVsbGRcbiIsZHAoMCxrKSk7CgkKCXJldHVybiAwOwp9