# Cod sursa(job #1943805)

Utilizator Data 28 martie 2017 20:25:11 Ferma2 10 cpp done Arhiva de probleme 1.26 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;}
else if(k == n - 1){
int Min = 2000000000;
for(int i = 1; i <= n ; ++i)
for(int j = 1; j <= i ; ++j)
if(a[i][j] < Min) Min = a[i][j];
printf("%d", Sum - Min);
return 0;
}
int Min = 2000000000;
for(int i = 1; i <= k + 1; ++i){
for(int j = 1; j <= i ; ++j){
int Sol = l[i + n - k - 1][j + n - k - 1] - l[i + n - k - 1][j - 1] + c[i + n - k - 1][j] - c[i - 1][j] + d[i + n - k - 2][j + n - k - 2] - d[i][j] - a[i + n - k - 1][j];
if(Sol < Min)
Min = Sol;
}
}
printf("%d", Sum - Min);
return 0;
}
``````