# Cod sursa(job #1784865)

Utilizator Data 20 octombrie 2016 16:30:09 Ferma2 100 cpp done Arhiva de probleme 1.23 kb
``````#include <cstdio>
#define MAXN 1000

int a[MAXN+1][MAXN+1], so[MAXN+1][MAXN+1], sv[MAXN+1][MAXN+1], sd[MAXN+1][MAXN+1];
inline int min2(int a, int b){
return (a<b ? a : b);
}

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

int i, j, n, k, lat, s=0, smin, si=0;

scanf("%d%d", &n, &k);
lat = n-k;

for(i=1; i<=n; ++i){
for(j=1; j<=i; ++j){
scanf("%d", &a[i][j]);
s += a[i][j];
}
}

for(i=1;i<=n; ++i)
for(j=1; j<=i; ++j){
so[i][j] = so[i][j-1] + a[i][j];
sv[i][j] = sv[i-1][j] + a[i][j];
sd[i][j] = sd[i-1][j-1] + a[i][j];
}

if(lat == 0){
printf("%d", s);
return 0;
}

for(i=1; i<=lat; ++i)
si += so[i][i];

a[lat][lat] = smin = si;
for(i=lat+1; i<=n; ++i)
{
a[i][lat] = a[i-1][lat] + so[i][lat] - sd[i-1][lat];
smin = min2(smin, a[i][lat]);
for(j=lat+1; j<=i; ++j){
a[i][j] = a[i][j-1] + sd[i][j] - sd[i-lat][j-lat] - (sv[i][j-lat] - sv[i-lat][j-lat]);
smin = min2(smin, a[i][j]);
}
}
printf("%d", s - smin);

return 0;
}
``````