# Cod sursa(job #1798216)

Utilizator Data 4 noiembrie 2016 22:36:14 Ferma2 100 c done Arhiva de probleme 1.39 kb
``````#include <stdio.h>
#include <stdlib.h>
int a[1001][1001],sumv[1001][1001],sumo[1001][1001],rez[1001][1001],sumd[1001][1001];
int main()
{
int i,j,n,k,min,s,x;
freopen("ferma2.in","r",stdin);
freopen("ferma2.out","w",stdout);
scanf("%d%d",&n,&k);
s=0;
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++)
sumv[i][j]=sumv[i-1][j]+a[i][j];
for(i=1; i<=n; i++)
for(j=1; j<=i; j++)
sumo[i][j]=sumo[i][j-1]+a[i][j];
for(i=1; i<=n; i++)
{
x=i;
j=1;
while(x<=n)
{
sumd[x][j]=sumd[x-1][j-1]+a[x][j];
x++;
j++;
}
}
for(i=1; i<=n-k; i++)
for(j=1; j<=i; j++)
rez[n-k][1]+=a[i][j];
min=rez[n-k][1];
for(i=n-k+1,j=2; i<=n; i++,j++){
rez[i][j]=rez[i-1][j-1]-(sumv[i-1][j-1]-sumv[i-1-(n-k)][j-1])+(sumo[i][j+(n-k)-1]-sumo[i][j-1]);
if(rez[i][j]<min)
min=rez[i][j];
}
for(i=n-k+1; i<=n; i++)
for(j=1; j<i-n+k+1; j++){
rez[i][j]=rez[i-1][j]-(sumd[i-1][j+(n-k)-1]-sumd[i-1-(n-k)][j-1])+(sumo[i][j+(n-k)-1]-sumo[i][j-1]);
if(rez[i][j]<min)
min=rez[i][j];
}
printf("%d\n",s-min);

return 0;
}
``````