# Cod sursa(job #636374)

Utilizator Data 19 noiembrie 2011 19:27:02 Ferma2 100 cpp done .com 2011 1.77 kb
``````#include<assert.h>
#include<stdio.h>
#include<algorithm>
using namespace std;

int n,k,l,sol,s,u,nov5[1001],a[1001][1001],line[1001][1001],col[1001][1001],diag[1001][1001];

{
assert(freopen("ferma2.in","r",stdin)!=NULL);
int i,j;
scanf("%d%d",&n,&k);
for(i=1;i<=n;++i)
for(j=1;j<=i;++j)
{
scanf("%d",&a[i][j]);
sol+=a[i][j];
line[i][j]=line[i][j-1]+a[i][j];
col[i][j]=col[i-1][j]+a[i][j];
diag[i][j]=diag[i-1][j-1]+a[i][j];
}
}

void solve()
{
int i,j,tr=0;
l=n-k;
if(l==0)
{
sol=0;
return ;
}
for(i=1;i<=l;++i)
for(j=1;j<=i;++j)
tr+=a[i][j];
s=tr;
nov5[1]=tr;
++u;
k++;
//printf("%d\n",tr);
for(i=2;i<=k;++i)
{
tr=nov5[u]+line[i+l-1][l]-diag[i+l-2][l];
nov5[++u]=tr;
s=min(s,tr);
//printf("%d\n",tr);
for(j=2;j<=i;++j)
{
tr=tr-col[i+l-1][j-1]+col[i-1][j-1]+diag[i+l-1][j+l-1]-diag[i-1][j-1];
s=min(s,tr);
// printf("%d\n",tr);
}
}
sol=sol-s;
}

void write()
{
assert(freopen("ferma2.out","w",stdout)!=NULL);
//for(int i=1;i<=u;++i)
//printf("%d ",nov5[i]);
//printf("\n");
//for(int i=1;i<=n;++i)
//   {for(int j=1;j<=i;++j)
//     printf("%d ",line[i][j]);
//  printf("\n");}
//for(int i=1;i<=n;++i)
//  {for(int j=1;j<=i;++j)
//     printf("%d ",col[i][j]);
// printf("\n");}
//for(int i=1;i<=n;++i)
//{for(int j=1;j<=i;++j)
// printf("%d ",diag[i][j]);
// printf("\n");}
printf("%d",sol);
}

int main()
{
//assert(freopen("ferma2.out","w",stdout)!=NULL);