Cod sursa(job #347171)
#include <cstdio>
#include <cstring>
#define file_in "ferma.in"
#define file_out "ferma.out"
#define Nmax 10010
#define Kmax 1111
#define Inf 0x3f3f3f3f
int N,K;
int i,j,k,ind;
int P[Nmax];
int S[2][2][Kmax];
inline int max(int a, int b) { return a>b?a:b; }
inline int abs(int a) { return a>=0?a:-a; }
int main()
{
freopen(file_in,"r",stdin);
freopen(file_out,"w",stdout);
scanf("%d %d", &N, &K);
for (i=1;i<=N;++i)
{
scanf("%d", &P[i]);
}
for (i=0;i<=K;++i)
{
S[0][0][i]=-Inf;
S[0][1][i]=-Inf;
}
S[0][0][0]=0;
ind=1;
for (i=1;i<=N;++i)
{
ind^=1;
S[ind][0][0]=S[ind^1][0][0];
S[ind][1][0]=-Inf;
for (j=1;j<=K;++j)
{
S[ind][0][j]=max(S[ind^1][0][j],S[ind^1][1][j]);
S[ind][1][j]=P[i]+max(S[ind^1][1][j],max(S[ind^1][0][j-1],S[ind^1][1][j-1]));
}
}
printf("%d", max(S[ind^1][0][K],S[ind^1][1][K]));
fclose(stdin);
fclose(stdout);
return 0;
}