# Cod sursa(job #2090011)

Utilizator Data 17 decembrie 2017 14:47:42 Ferma2 100 cpp done Arhiva de probleme 1.4 kb
``````#include <bits/stdc++.h>
#define MAXN 1000

int v[1 + MAXN][1 + MAXN];
long long s[1 + MAXN][1 + MAXN];
long long diag[1 + MAXN][1 + MAXN];
long long oriz[1 + MAXN][1 + MAXN];
long long vert[1 + MAXN][1 + MAXN];
int main(){
FILE*fi,*fo;
fi=fopen("ferma2.in","r");
fo=fopen("ferma2.out","w");

int n, k;
long long sum = 0;
fscanf(fi,"%d%d", &n, &k);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= i; j++){
int x;
fscanf(fi,"%d", &x);
diag[i][j] = diag[i - 1][j - 1] + x;
oriz[i][j] = oriz[i][j - 1] + x;
vert[i][j] = vert[i - 1][j] + x;
v[i][j] = x;
sum += x;
}
}
int nlat = n - k;
for(int i = 1; i <= nlat; i++)
for(int j = 1; j <= i; j++)
s[nlat][1] += v[i][j];
for(int i = nlat; i <= n; i++){
if(i != nlat)
s[i][1] = s[i - 1][1] + oriz[i][nlat] - diag[i - 1][nlat];
for(int j = 2; j <= i; j++)
s[i][j] = s[i][j - 1] - (vert[i][j - 1] - vert[i - nlat][j - 1]) + (diag[i][j + nlat - 1] - diag[i - nlat][j - 1]);
}
long long min = 1000000000000000000;
for(int i = nlat; i <= n; i++)
for(int j = 1; j + nlat - 1 <= i; j++)
if(s[i][j] < min)
min = s[i][j];
fprintf(fo,"%lld", sum - min);
fclose(fi);
fclose(fo);
return 0;
}
``````