# Cod sursa(job #1503748)

Utilizator Data 16 octombrie 2015 20:58:54 Ferma2 100 cpp done Arhiva de probleme 1.56 kb
``````#include <fstream>

using namespace std;

const int N=1005;

ifstream fin("ferma2.in");
ofstream fout("ferma2.out");

int lin[N], col[N], diag[N], b[N][N], c[N][N], drept[N][N], inter1[N][N], inter2[N][N];

void afis(int n)
{
int i;
for(i=1;i<=n;i++) fout<<lin[i]<<" "; fout<<"\n";
for(i=1;i<=n;i++) fout<<col[i]<<" "; fout<<"\n";
for(i=1;i<=n;i++) fout<<diag[i]<<" "; fout<<"\n";
}

int main()
{
int n, k, i, j, d, x, sol=0;
fin>>n>>k;
for(i=1;i<=n;i++)
{
for(j=1;j<=i;j++)
{
fin>>x;
lin[n-i+1]+=x;
col[j]+=x;
diag[i-j+1]+=x;
b[i][j]=b[i-1][j]+x;
c[i][j]=c[i][j-1]+x;
drept[i][j]=x+drept[i-1][j]+drept[i][j-1]-drept[i-1][j-1];
}
}
for(i=1;i<=n;i++)
{
lin[i]+=lin[i-1];
col[i]+=col[i-1];
diag[i]+=diag[i-1];
}
//afis(n);
for(i=1;i<=k;i++)
{
for(j=1;i+j<=k;j++)
{
inter1[i][j]=inter1[i-1][j]+b[i+j-1][i];
inter2[i][j]=inter2[i-1][j]+c[n-i+1][n-i+1]-c[n-i+1][n-i+1-j];
//fout<<inter2[i][j]<<" ";
}
//fout<<"\n";
}
for(i=0;i<=k;i++)
{
for(j=0;j+i<=k;j++)
{
d=k-i-j;
x=lin[i]+col[j]+diag[d]-inter1[j][d]-inter2[i][d]-(drept[n][j]-drept[n][0]-drept[n-i][j]+drept[n-i][0]);
sol=max(sol, x);
//fout<<x<<" ";
}
//fout<<"\n";
}
fout<<sol;
fin.close();
fout.close();
}
``````