# Cod sursa(job #1756491)

Utilizator Data 12 septembrie 2016 22:13:08 Ferma2 100 cpp done Arhiva de probleme 1.24 kb
``````#include <cstdio>
#define NMax 1000
#define INF 1<<30

int prc[NMax+1][NMax+1];
int col[NMax+1][NMax+1];
int lin[NMax+1][NMax+1];
int a[NMax+1][NMax+1];
int N,K,ans,minim=INF;

void Precalc()
{
int i,j;

for(i = 1; i <= N; ++i)
for(j = 1; j <= i; ++j)
{
prc[i-j][j] = prc[i-j][j-1] + a[i][j];
col[j][i] = col[j][i-1] + a[i][j];
lin[i][j] = lin[i][j-1] + a[i][j];
ans += a[i][j];
}
}

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

int i,j,L,first,temp;

scanf("%d %d",&N,&K);
for(i = 1; i <= N; ++i)
for(j = 1; j <= i; ++j) scanf("%d",&a[i][j]);

Precalc();

L = N-K; first = 0;
for(i = 1; i <= L; ++i) first += prc[i-1][L-i+1];
minim = first;

for(i = 2; i <= N-L+1; ++i)
{
first = first - prc[i-2][L] + lin[i+L-1][L];

temp = first;
if( temp < minim ) minim = temp;

for(j = 2; j <= i; ++j)
{
temp = temp - ( col[j-1][i+L-1] - col[j-1][i-1] ) + ( prc[i-j][j+L-1] - prc[i-j][j-1] );
if( temp < minim ) minim = temp;
}
}

printf("%d\n", ans-minim );

return 0;
}
``````