# Cod sursa(job #1778017)

Utilizator Data 13 octombrie 2016 11:23:23 Ferma2 100 cpp done Arhiva de probleme 1.73 kb
``````#include <cstdio>
#include <cctype>

using namespace std;

const int BUFF_SIZE = (1 << 17);

FILE *fin;
int buffp = BUFF_SIZE - 1;
char buff[BUFF_SIZE];

inline void next_char() {
if (++buffp == BUFF_SIZE) {
buffp = 0;
}
}

inline int get_num() {
int num = 0;
while (isdigit(buff[buffp]) == 0)
next_char();
while (isdigit(buff[buffp])) {
num = num * 10 + buff[buffp] - '0';
next_char();
}
return num;
}

const int MAXN = 1000;

int diag[MAXN + 1][MAXN + 1], left[MAXN + 1][MAXN + 1], up[MAXN + 1][MAXN + 1], tri[MAXN + 1][MAXN + 1];

inline int minimum(int a, int b) {
if (a < b)
return a;
return b;
}

int main() {
FILE *fout;
int n, k, i, j, side, sum, minsum, num;
fin = fopen("ferma2.in", "r");
n = get_num(); k = get_num();
sum = 0;
for (i = 1; i <=n; ++i)
for (j = 1; j <= i; ++j) {
sum += (num = get_num());
diag[i][j] = diag[i - 1][j - 1] + num;
left[i][j] = left[i][j - 1] + num;
up[i][j] = up[i - 1][j] + num;
}
fclose(fin);
side = n - k;
for (i = 1; i <= side; ++i)
tri[1][1] += up[side][i];
minsum = tri[1][1];
for (i = 2; i + side - 1 <= n; ++i) {
tri[i][1] = tri[i - 1][1] - diag[i + side - 2][side] + left[i + side - 1][side];
minsum = minimum(minsum, tri[i][1]);
for (j = 2; j <= i; ++j) {
tri[i][j] = tri[i][j - 1] + diag[i + side - 1][j + side - 1] - diag[i - 1][j - 1] - up[i + side - 1][j - 1] + up[i - 1][j - 1];
minsum = minimum(minsum, tri[i][j]);
}
}
fout = fopen("ferma2.out", "w");
fprintf(fout, "%d\n", sum - minsum);
fclose(fout);
return 0;
}
``````