# Cod sursa(job #1276903)

Utilizator Data 26 noiembrie 2014 23:05:54 Ferma2 100 cpp done Arhiva de probleme 1.2 kb
``````#include <cstdio>
#include <algorithm>

#define NMAX 1007

using namespace std;

int n, k, Sum, Ans;
int a[NMAX][NMAX], Diag[NMAX][NMAX], Lin[NMAX][NMAX], Col[NMAX][NMAX], Dp[NMAX][NMAX];

int main(){
freopen("ferma2.in", "r", stdin);
freopen("ferma2.out", "w", stdout);
scanf("%d %d", &n, &k);
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= i; ++j){
scanf("%d", &a[i][j]);
Sum += a[i][j];
Lin[i][j] = Lin[i][j - 1] + a[i][j];
Col[i][j] = Col[i - 1][j] + a[i][j];
Diag[i][j] = Diag[i - 1][j - 1] + a[i][j];
}
}
k = n - k;
for(int i = 1 ; i <= k ; ++i)
for(int j = 1 ; j <= i; ++j)
Dp[1][1] += a[i][j];
Ans = Dp[1][1];
for(int i = 2 ; i <= n - k + 1; ++i){
Dp[i][1] = Dp[i - 1][1] - Diag[i + k - 2][k] + Lin[i + k - 1][k];
Ans = min(Ans, Dp[i][1]);
for(int j = 2 ; j <= i ; ++j){
Dp[i][j] = Dp[i][j - 1] + Diag[i + k - 1][j + k - 1] - Diag[i - 1][j - 1] - Col[i + k - 1][j - 1] + Col[i - 1][j - 1];
Ans = min(Ans, Dp[i][j]);
}
}
Ans = Sum - Ans;
printf("%d\n", Ans);
return 0;
}
``````