# Cod sursa(job #2080015)

Utilizator Data 2 decembrie 2017 12:06:50 Ferma2 100 cpp done Arhiva de probleme 1.17 kb
``````#include <cstdio>
#include <iostream>

using namespace std;
int a[1001][1001],sv[1001][1001],so[1001][1001],sd[1001][1001],d[1001][1001];
int main()
{
FILE *fin=fopen ("ferma2.in","r");
FILE *fout=fopen ("ferma2.out","w");
int n,k,s,i,j,l,sol;
fscanf(fin,"%d%d",&n,&k);
s=0;
for (i=1;i<=n;i++)
for (j=1;j<=i;j++){
fscanf (fin,"%d",&a[i][j]);
s+=a[i][j];
sv[i][j]=sv[i-1][j]+a[i][j];
so[i][j]=so[i][j-1]+a[i][j];
sd[i][j]=sd[i-1][j-1]+a[i][j];
}
//calculez normal d[1][1]
l=n-k;
for (i=1;i<=l;i++)
for (j=1;j<=i;j++)
d[1][1]+=a[i][j];
sol=d[1][1];
for (i=2;i+l-1<=n;i++){
// cand j=1 calculez pe d[i][j] din d[i-1][j]
j=1;
d[i][j]=d[i-1][j]-(sd[i+l-2][j+l-1]-sd[i-2][j-1])+so[i+l-1][j+l-1];
sol=min (sol,d[i][j]);
for (j=2;j<=i;j++){
// il calculez pe d[i][j] din d[i][j-1]
d[i][j]=d[i][j-1]-(sv[i+l-1][j-1]-sv[i-1][j-1])+(sd[i+l-1][j+l-1]-sd[i-1][j-1]);
sol=min(sol,d[i][j]);
}
}
fprintf (fout,"%d",s-sol);
return 0;
}
``````