Cod sursa(job #1539728)

Utilizator Data 1 decembrie 2015 15:06:48 Ferma2 100 cpp done Arhiva de probleme 1.05 kb
#include <cstdio>
#include <algorithm>

#define DIM 1024
#define INF 1000000000
using namespace std;

int N, K, matrix[DIM][DIM], line_sum[DIM][DIM], rectangle_sum[DIM][DIM], triangle_sum[DIM][DIM], minim, sum;

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", &matrix[i][j]);

for (int i = 1; i <= N; i ++)
for (int j = 1; j <= N; j ++) {
line_sum[i][j] = matrix[i][j] + line_sum[i][j-1];
rectangle_sum[i][j] = rectangle_sum[i-1][j] + line_sum[i][j];
triangle_sum[i][j] = triangle_sum[i-1][j-1] + line_sum[i][j];

sum += matrix[i][j];
}

K = N - K; minim = INF;
for (int i = K; i <= N; i ++)
for (int j = K; j <= i; j ++)
minim = min (minim, triangle_sum[i][j] - rectangle_sum[i][j-K] + rectangle_sum[i-K][j-K] - triangle_sum[i-K][j-K]);

printf ("%d\n", sum - minim);

return 0;
}