# Cod sursa(job #636743)

Utilizator Data 19 noiembrie 2011 23:02:21 Ferma2 20 cpp done .com 2011 1.04 kb
``````#include <stdio.h>
#define NMax 1010

const char IN[]="ferma2.in",OUT[]="ferma2.out";

int N,K,Rez;
int a[NMax][NMax];
int S[NMax][NMax] , S2[NMax][NMax] , S3[NMax][NMax];
int T[NMax][NMax];

int max(int x,int y){
return x>y ? x : y;
}

int main()
{
int i,j,k;
freopen(IN,"r",stdin);
scanf("%d%d",&N,&K);
for (i=1;i<=N;++i) for (j=1;j<=i;++j)
{
scanf("%d",&a[i][j]);
S[i][j]=a[i][j]+S[i-1][j-1];
S2[i][j]=a[i][j]+S2[i-1][j];
S3[i][j]=a[i][j]+S3[i][j-1];
}

for (i=0;i<=N && i<=K;++i)
{
j=K-i;
for (k=0;k<i;++k)
T[i][j]+= S3[N-k][N-k];
for (k=0;k<j;++k)
T[i][j]+= S2[N-i][k+1];
Rez=max(Rez,T[i][j]);
}

for (k=1;k<=N;++k)
for (i=0;i<=N;++i)
{
j=K-(i+k);
if (j<0) break;
T[i][j]= T[i+1][j] + S3[N-i][j] - S3[N-i][N-i-k+1] + /*a[N-i][N-i-k+2] +  a[N-i][N-i-k+3]*/ +S[N-i][N-i-k+1] - S[N-i-k][j] ;
// T[i][j+1] - S2[N-i][j+1] + a[j+1][j+1] + a[j+2][j+1] + S[N-i][j+k] - S[N-i-k][j]);
Rez=max(Rez,T[i][j]);
}

freopen(OUT,"w",stdout);
printf("%d\n",Rez);
fclose(stdout);
return 0;
}

``````