# Cod sursa(job #1044)

Utilizator Data 12 decembrie 2006 15:00:17 Ferma 100 cpp done Arhiva de probleme 1.06 kb
``````#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 10240;
const int KMAX = 1024;
const int INF = 0x3f3f3f3f;

int N, K;
int A[NMAX];
int S[NMAX];
int DP[2][NMAX];
int rez;

void citire() {
FILE *fin = fopen("ferma.in", "rt");
int i;

fscanf(fin, " %d %d", &N, &K);

for (i = 0; i < N; ++i)
fscanf(fin, " %d", A + i);

fclose(fin);
}

void complete(int i) {
int j, k, k1, mx;

for (; i <= K; ++i) {
k = i & 1; k1 = k ^ 1;

mx = 0;

for (j = 1; j < N; ++j) {
DP[k][j] = max(DP[k][j - 1], S[j] + mx),
mx >?= DP[k1][j] - S[j];
}
}
}

void dinamica() {
int i, k;

for (S[0] = A[0], i = 1; i < N; ++i)
S[i] = S[i - 1] + A[i];

complete(1);

k = K & 1;

for (i = 0; i < N; ++i)
rez >?= DP[k][i];

DP[1][0] = S[0];
for (i = 1; i < N; ++i)
DP[1][i] = max(DP[1][i - 1], S[i]);

complete(2);

for (i = 0; i < N; ++i)
rez >?= DP[k][i] + S[N - 1] - S[i];
}

void afisare() {
FILE *fout = fopen("ferma.out", "wt");

fprintf(fout, "%d\n", rez);

fclose(fout);
}

int main() {
citire();
dinamica();
afisare();
return 0;
}

``````