# Cod sursa(job #2056225)

Utilizator Data 4 noiembrie 2017 10:05:32 Ferma2 0 cpp done Arhiva de probleme 1.32 kb
``````#include <fstream>

using namespace std;

ifstream fin ("ferma2.in");
ofstream fout("ferma2.out");

/// facem sume partiale pe linii, coloane, diagolanle
/// determinam subtriunghiul de latura L = n-k (dupa k zile) de suma minima, restul ramas va fi suma maxima cautata

int sl[1005][1005], sc[1005][1005], sd[1005][1005]; /// sume partiale pe linii, coloane, diagonale
int S, smin; /// S - suma totala

int main()
{
int n, k;
fin >> n >> k;
int L = n-k;

for(int i = 1; i <= n; ++i)
for(int j = 1, x; j <= i; ++j)
{
fin >> x;
S += x;
sc[i][j] = x + sc[i-1][j];
sl[i][j] = x + sl[i][j-1];
sd[i][j] = x + sd[i-1][j-1];
}
fin.close();

for(int i = 1; i <= L; ++i)
smin += sl[i][i];
int suma, s; /// s - triunghiul lipit de cateta stanga
suma = s = smin;
for(int i = L + 1; i <= n; ++i)
{
s = s - sd[i-1][L] + sl[i][L];
suma = s;
smin = min(smin, suma);
for(int j = L+1; j <= i; ++j)
{
suma = suma - (sd[i][j] - sd[i-k][j-k]) + (sc[i][j-k] - sc[i-k][j-k]);
smin = min(smin, suma);
}
}
fout << S - smin;
return 0;
}

/*
56
82 5
55 3 11
67 46 52 12
62 20 54 85 14
66 32 40 78 52 22
*/
``````