# Cod sursa(job #636313)

Utilizator Data 19 noiembrie 2011 18:43:51 Ferma2 0 cpp done .com 2011 1.45 kb
``````#include<stdio.h>
#include<assert.h>
#include<algorithm>
using namespace std;

int n,k,l,s,sm,xm,ym,a[1001][1001],diag[1001][1001],col[1001][1001],line[1001][1001],diag2[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]);
diag2[i][j]=a[i][j]+diag2[i-1][j-1]+diag2[i-1][j];
line[i][j]=a[i][j]+line[i][j-1]+line[i-1][j];
col[i][j]=a[i][j]+col[i-1][j]+col[i][j-1];
}
for(i=1;i<=n;++i)
for(j=0;j<n;++j)
diag[i][j]=a[i][i+j]+diag[i-1][i+j-1]+diag[i][i+j+1];
}

inline int valid(int x,int y)
{
return (x-y+1)>=l;
}

inline int val(int x,int y)
{
int z;
z=0;
z+=diag[n][y+l];
z+=col[n][y-1];
z+=line[n][n]-line[x][x];
z-=col[x][y-1];
z-=diag2[x+l][y];
z-=diag[n][y+l]-diag[x][y+l];
return sm-z;
}

void solve()
{
int i,j;
l=n-k;
for(i=1;i<=n;++i)
for(j=1;j<=i;++j)
sm+=a[i][j];
if(l==0)
{
s=sm;
return;
}
s=0;
for(i=1;i<=n;++i)
for(j=1;j<=i;++j)
if(valid(i,j))
{
s=max(s,val(i,j));
xm=i;
ym=j;
}
}

void write()
{
assert(freopen("ferma2.out","w",stdout)!=NULL);
printf("%d %d %d",s,xm,ym);
}

int main()
{