Cod sursa(job #640850)
# include <fstream>
using namespace std;
ifstream f ("ferma2.in");
ofstream g ("ferma2.out");
int s=0,a[1006][1006],smin=1000000000,sum[1005][1005],k,i,j,n,sl[1005][1005],sc[1005][1005];
int main ()
{
f>>n>>k;
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
{
f>>a[i][j];
sc[i][j]+=sc[i-1][j]+a[i][j];
sl[i][j]+=sl[i][j-1]+a[i][j];
s+=a[i][j];
}
k=n-k;
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
{
if (j<=k)
sum[i][j]=sum[i-1][j-1]+sl[i][j];
else
sum[i][j]=sum[i-1][j-1]-(sc[i-1][j-k]-sc[i-k-1][j-k])+(sl[i][j]-sl[i][j-k]);
if (j>=k)
if (smin>sum[i][j])
smin=sum[i][j];
}
g<<s-smin;
return 0;
}