# Cod sursa(job #1789242)

Utilizator Data 26 octombrie 2016 20:02:01 Ferma2 100 cpp done Arhiva de probleme 1.18 kb
``````#include <iostream>
#include <cstdio>
#define MAXN 1050

using namespace std;

int n, k, dif, tot, a[MAXN][MAXN];
int diags[MAXN][MAXN], lins[MAXN][MAXN];

{
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
{
tot += a[i][j];
diags[i-j+1][j] = a[i][j] + diags[i-j+1][j-1];
lins[i][j] = a[i][j] + lins[i][j-1];
}
dif = n-k;
}

void solve()
{
int minim = 0x3f3f3f3f;
for (int col = 1; col <= n; col++) {
int crt = 0;
for (int j = 1; j <= dif; j++)
crt += lins[col+j-1][col+j-1] - lins[col+j-1][col-1];
for (int lin = col; lin <= n - dif+1; lin++) {
if (crt < minim) minim = crt;
crt += lins[lin+dif][col+dif-1] - lins[lin+dif][col-1];
crt -= diags[lin-col+1][col+dif-1] - diags[lin-col+1][col-1];
}
}
printf("%d", tot-minim);
}

int main()
{
freopen("ferma2.in", "r", stdin);
freopen("ferma2.out", "w", stdout);

solve();

return 0;
}
``````