# Cod sursa(job #1307540)

Utilizator Data 2 ianuarie 2015 15:15:46 Ferma2 100 c done Arhiva de probleme 1.21 kb
``````#include <stdio.h>
#define MAXN 1000
#define INF 2000000000
int vert[MAXN + 1][MAXN + 1], diag[MAXN + 1][MAXN + 1];

inline int caut(int sum, int k, int i, int j){
int min = sum;
while(j <= i){
sum += diag[i][j] - diag[i - k][j - k];
sum -= vert[i][j - k] - vert[i - k][j - k];
if(min > sum)
min = sum;
j++;
}
return min;
}

int main(){
FILE *in = fopen("ferma2.in", "r");
int n, k, i, j, x, sumt = 0;
fscanf(in, "%d%d", &n, &k);
k = n - k;
for(i = 1; i <= n; i++){
for(j = 1; j <= i; j++){
fscanf(in, "%d", &x);
sumt += x;
vert[i][j] = x + vert[i - 1][j];
diag[i][j] = x + diag[i - 1][j - 1];
}
}
fclose(in);
int sum = 0, min = INF;
for(i = 1; i <= k; i++){
for(j = 1; j <= i; j++){
sum += vert[i][j] - vert[i - 1][j];
}
}
if(sum < min)
min = sum;
for(i = k + 1; i <= n; i++){
sum -= diag[i][k + 1];
for(j = 1; j <= k + 1; j++)
sum += vert[i][j] - vert[i - 1][j];
if(min > sum)
min = sum;
x = caut(sum, k, i, k + 1);
if(x < min)
min = x;
}
FILE *out = fopen("ferma2.out", "w");
fprintf(out, "%d", sumt - min);
fclose(out);
return 0;
}
``````