# Cod sursa(job #1474751)

Utilizator Data 22 august 2015 20:11:46 Ferma2 100 cpp done Arhiva de probleme 1.34 kb
``````#include<fstream>
using namespace std;
ifstream f("ferma2.in"); ofstream g("ferma2.out");
const int N = 1002;
//const int INF =
int n,k,a[N][N],sl[N][N],sc[N][N],sd[N][N],d[N][N];
void citire()
{   f>>n>>k;
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
f>>a[i][j];
}
void calc()
{   for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
{   sl[i][j]=sl[i][j-1]+a[i][j];
sc[i][j]=sc[i-1][j]+a[i][j];
sd[i][j]=sd[i-1][j-1]+a[i][j];
}
}
void dinamica()  // d[i][j] = profitul minimim pentru un triunghi de latura n - k, cu coltul in (i, j)
{   int i,j;
for (i=1;i<=n;++i)
for(j=1;j<=i;++j)
d[i][j]=-1;
d[n][1]=0;
for(i=k+1;i<=n;++i) d[n][1]+=sl[i][i- k];
for(j=2;j<=k+1;++j)
d[n][j]= d[n][j-1]-(sc[n][j-1]-sc[k][j-1])+(sd[n][j+ n-k-1]-sd[k][j-1]);
for(i=n-1;i>=n-k;--i)
for(j=1;j+n-k-1<=i;++j)
d[i][j]=d[i+1][j]-(sl[i+1][j+n -k-1]- sl[i+1][j-1])+(sd[i][j+n-k-1]-sd[i-(n-k)][j-1]);
}
void rez()
{   int minim=0x3f3f3f3f,sum=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
{   sum+=a[i][j];
if(d[i][j]!=-1 && d[i][j]<minim) minim=d[i][j];
}
g<<sum-minim<<'\n'; g.close();
}
int main()
{   citire();
calc();
dinamica();
rez();
return 0;
}
``````