# Cod sursa(job #634852)

Utilizator Data 17 noiembrie 2011 18:16:56 Ferma2 Ascuns cpp done 1.56 kb
``````//eudanip
#include<stdio.h>

#define NMAX 1005
#define maxim(a,b) (a>b ? a : b)
#define minim(a,b) (a<b ? a : b)

int line[NMAX],colum[NMAX],sd[NMAX],n;
int d3[NMAX][NMAX],d2[NMAX][NMAX],sum;
int k,d[NMAX][NMAX],sol,a[NMAX][NMAX];
int l[NMAX][NMAX],c[NMAX][NMAX];

int main ()
{
int i,j,t;

freopen("ferma2.in","r",stdin);
freopen("ferma2.out","w",stdout);
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
{
scanf("%d",&a[i][j]);
line[n-i+1]+=a[i][j];
colum[j]+=a[i][j];
sd[i-j+1]+=a[i][j];
}
for(i=1;i<=n;i++)
{
line[i]+=line[i-1];
colum[i]+=colum[i-1];
sd[i]+=sd[i-1];
//printf("line[%d]=%d colum[%d]=%d sd[%d]=%d\n",i,line[i],i,colum[i],i,sd[i]);
}
for(i=1;i<=n;i++)
for(j=1;i+j<=n+1;j++)
{
d[i][j]=a[n-i+1][j]+d[i-1][j]+d[i][j-1]-d[i-1][j-1];
//printf("d[%d][%d]=%d\n",i,j,d[i][j]);
}
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
{
c[i][j]=c[i][j-1]+a[j][i];
//printf("c[%d][%d]=%d\n",i,j,c[i][j]);
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
d2[i][j]=d2[i-1][j]+c[i][minim(i+j-1,n)];

for(i=1;i<=n;i++)
for(j=i;j>=1;j--)
l[i][j]=l[i][j+1]+a[i][j];

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
d3[i][j]=d3[i-1][j]+l[n-i+1][maxim(1,n-i-j+2)];

/*for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
printf("d2[%d][%d]=%d\n",i,j,d2[i][j]);*/
for(i=0;i<=k;i++)
for(j=0;j<=k-i;j++)
{
t=k-i-j;
sum=line[i]+colum[j]-d[i][j]+sd[t]-d2[j][t]-d3[i][t];
//if(sum==839)
//	printf("%d %d %d !!! %d %d %d %d %d %d\n",i,j,t,line[i],colum[j],sd[t],d[i][j],d2[j][t],d3[i][t]);
sol=maxim(sol,sum);
}
printf("%d\n",sol);
return 0;
}

``````