# Cod sursa(job #2056220)

Utilizator Data 4 noiembrie 2017 10:03:23 Ferma2 0 cpp done Arhiva de probleme 1.4 kb
``````#include <bits/stdc++.h>

using namespace std;
/**
facem sume partiale pe linii,coloane,diagonale
determinam subtriunghiul de latura L=n-k
de suma minima
*/
const short NMAX=1001;
int lin[NMAX][NMAX],col[NMAX][NMAX],diag[NMAX][NMAX],lat;
int n,k,a[NMAX][NMAX],Stotal;
ifstream fin("ferma2.in");
ofstream fout("ferma2.out");
{
fin>>n>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
fin>>a[i][j];
int x=a[i][j];
Stotal+=x;
}
}
inline void SUM_Part()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
lin[i][j]=lin[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];
}
}
inline void DP()
{
lat=n-k;
int s,smin,suma;
///calculez suma formata din primele lat linii
smin=0;
for(int i=1;i<=lat;i++)
smin+=lin[i][i];
suma=s=smin;
for(int i=lat+1;i<=n;i++)
{
s-=(diag[i-1][lat] + lin[i][lat]);
suma=s;
smin=min(smin,s);
for(int j=lat+1;j<=i;j++)
{
suma=suma-(diag[i][j]-diag[i-lat][j-lat])+(col[i][j-lat]-col[i-lat][j-lat]);
smin=min(smin,suma);
}
}
fout<<(Stotal-smin)<<"\n";
}
int main()
{
SUM_Part();
DP();
fin.close();
fout.close();
return 0;
}
``````