# Cod sursa(job #1783479)

Utilizator Data 19 octombrie 2016 00:38:30 Ferma2 100 cpp done cerculdeinfo-lectia3-programaredinamica1 1.11 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[0][0]+=v[i][j];
Min=min(Min,D[0][0]);
for(int i=1;i<=K;i++)
D[i][0]=D[i-1][0]+Row[i+N-K][N-K]-Diag[i+N-K-1][N-K],Min=min(Min,D[i][0]);

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