# Cod sursa(job #1777431)

Utilizator Data 12 octombrie 2016 14:47:25 Ferma2 0 cpp done Arhiva de probleme 0.96 kb
``````﻿#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define INF 2000000000
#define MaxN 1005
using namespace std;

FILE *IN,*OUT;
int N,K,v[MaxN][MaxN],Row[MaxN][MaxN],Column[MaxN][MaxN],Diag[MaxN][MaxN],D[MaxN][MaxN],S=0,Min=INF;

int main()
{
IN=fopen("ferma2.in","r");
OUT=fopen("ferma2.out","w");

fscanf(IN,"%d%d",&N,&K);
for(int i=1;i<=N;i++)
for(int j=1;j<=i;j++)
{
fscanf(IN,"%d",&v[i][j]);
Row[i][j]=Row[i][j-1]+v[i][j];
Column[i][j]=Column[i-1][j]+v[i][j];
Diag[i][j]=Diag[i-1][j-1]+v[i][j];
S+=v[i][j];
}
for(int i=1;i<=N-K;i++)
for(int j=1;j<=i;j++)
D[1][1]+=v[i][j];
for(int i=2;i<=K+1;i++)
D[i][1]=D[i-1][1]+Row[i+K-2][K-1]-Diag[i+K-3][K-1],Min=min(Min,D[i][1]);

for(int i=2;i<=K+1;i++)
for(int j=2;j<=i;j++)
D[i][j]=D[i][j-1]+Column[i-1][j-1]-Column[i+K-2][j-1]-Diag[i-1][j-1]+Diag[i+K-2][j+K-2],Min=min(Min,D[i][j]);
fprintf(OUT,"%d",S-Min);
return 0;
}``````