# Cod sursa(job #635849)

Utilizator Data 19 noiembrie 2011 15:16:09 Ferma2 90 cpp done .com 2011 1.23 kb
``````#include<fstream>
using namespace std;
int N,M,K,A[1010][1010],sum,sol=2000000000;
int sumL[2000][2000],sumC[2000][2000],sumD[2000][2000],best[2000][2000];

void Citire()
{
int i,j,x,lim;
ifstream fin("ferma2.in");
fin>>N>>K;
M=N-K;
for(i=1;i<=N;i++)
{
for(j=1;j<=i;j++)
{
fin>>A[i][j];
sumL[i][j]=sumL[i][j-1]+A[i][j];
sumC[i][j]=sumC[i-1][j]+A[i][j];
sumD[i][j]=sumD[i-1][j-1]+A[i][j];
sum+=A[i][j];
}
}
lim=N+M;
for(i=1;i<=N;i++)
{
x=sumL[i][i];
for(j=i+1;j<=lim;j++)
sumL[i][j]=x;
}
fin.close();
}

void Rezolvare()
{
int i,j,lim,suma=0;
for(i=1;i<=M;i++)
for(j=1;j<=i;j++)
suma+=A[i][j];
best[M][1]=suma;
for(j=2;j<=M;j++)
best[M][j]=best[M][j-1]-sumC[M][j-1];
for(i=M+1;i<=N;i++)
{
lim=i-M+1;
for(j=1;j<=lim;j++)
{
best[i][j]=best[i-1][j]-(sumD[i-1][j+M-1]-sumD[i-M-1][j-1])+(sumL[i][j+M-1]-sumL[i][j-1]);
sol=min(sol,best[i][j]);
}
for(j=lim+1;j<=i;j++)
best[i][j]=best[i-1][j]-(sumD[i-1][j+M-1]-sumD[i-M-1][j-1])+(sumL[i][j+M-1]-sumL[i][j-1]);
}
}

void Afisare()
{
sol=sum-sol;
ofstream fout("ferma2.out");
fout<<sol<<"\n";
fout.close();
}

int main()
{
Citire();
Rezolvare();
Afisare();
return 0;
}
``````