# Cod sursa(job #1943837)

Utilizator Data 28 martie 2017 20:42:44 Ferma2 10 cpp done Arhiva de probleme 1.14 kb
``````#include <cstdio>
using namespace std;

int n, k, a[1001][1001], l[1001][1001], c[1001][1001], d[1001][1001];
int main()
{
freopen("ferma2.in", "r", stdin);
freopen("ferma2.out", "w", stdout);
scanf("%d%d", &n, &k);
int Sum = 0;
for(int i = 1; i <= n ; ++i){
for(int j = 1; j <= i ; ++j){
scanf("%d", &a[i][j]), Sum += a[i][j];
l[i][j] = l[i][j - 1] + a[i][j];
c[i][j] = c[i - 1][j] + a[i][j];
d[i][j] = d[i - 1][j - 1] + a[i][j];
}
}
if(k == n) {printf("%d", Sum); return 0;}
else if(k == 0) {printf("%d", 0); return 0;}
int Smin = 0;
for(int i = 1; i <= n - k ; ++i)
Smin = Smin + l[i][i];
int Min = Smin;
for(int i = 2; i <= k + 1 ; ++i){
Smin = Smin + l[i + n - k - 1][n - k] - d[i + n - k - 2][n - k];
if(Smin < Min) Min = Smin;
for(int j = 2; j <= i ; ++j){
Smin = Smin - (c[i + n - k - 1][j - 1] - c[i - 1][j - 1]) + (d[i + n - k - 1][j + n - k - 1] - d[i - 1][j - 1]);
if(Smin < Min) Min = Smin;
}
}
printf("%d", Sum - Min);
return 0;
}
``````