# Cod sursa(job #635630)

Utilizator Data 19 noiembrie 2011 13:40:19 Ferma2 100 cpp done .com 2011 1.63 kb
``````#include <cstdio>

#define Nmax 1024

int N, K, i, j;
int V[Nmax][Nmax], L[Nmax][Nmax], D[Nmax][Nmax], C[Nmax][Nmax], A[Nmax][Nmax], S, best;

int main()
{
freopen("ferma2.in","r",stdin);
freopen("ferma2.out","w",stdout);

scanf("%d %d", &N, &K);
K = N - K;

for (i=0; i<N; ++i)
for (j=0; j<=i; ++j)
{
scanf("%d", &V[i][j]);
S += V[i][j];
}

//first triangle
for (i=0; i<K; ++i)
for (j=0; j<=i; ++j)
A[0][0] += V[i][j];

//lines
for (i=K-1; i<N; ++i)
{
for (j=0; j<K; ++j)
L[i][0] += V[i][j];
for (j=1; j+K-1<=i; ++j)
L[i][j] += L[i][j-1] + V[i][j+K-1] - V[i][j-1];
}

//diags
for (i=0; i+K<=N; ++i)
{
for (j=0; j<K; ++j)
D[i][0] += V[i+j][j];
for (j=1; i+j+K-1<N; ++j)
D[i+j][j] += D[i+j-1][j-1] + V[i+j+K-1][j+K-1] - V[i+j-1][j-1];
}

//cols
for (i=0; i+K<=N; ++i)
{
for (j=i; j<i+K; ++j)
C[i][i] += V[j][i];
for (j=i+1; j+K-1<N; ++j)
C[j][i] += C[j-1][i] + V[j+K-1][i] - V[j-1][i];
}

//total
best = A[0][0];
for (i=0; i+K<N; ++i)
{
for (j=0; j<=i; ++j)
{
A[i+1][j] = A[i][j] - D[i][j] + L[i+K][j];
if (A[i+1][j] < best) best = A[i+1][j];
}
A[i+1][i+1] = A[i+1][i] - C[i+1][i] + D[i+1][i+1];
if (A[i+1][i+1] < best) best = A[i+1][i+1];
}

printf("%d\n", S - best);

return 0;
}
``````