# Cod sursa(job #2056214)

Utilizator Data 4 noiembrie 2017 09:59:31 Ferma2 0 cpp done Arhiva de probleme 1.63 kb
``````#include <bits/stdc++.h>

using namespace std;

/**

82
55 3
67 46 52
62 20 54 85
66 32 40 78 52

1.facem sume partiale pe linii, coloane, diagonale
2.determinam subtriunghuil de latura L = n - k de suma minima
*/

int a[1002][1002];

int stot;

int n, k;
/// sume partiale pe linii, coloane, diagonale
int sc[1002][1002];
int sl[1002][1002];
int sd[1002][1002];

ofstream fout("ferma2.out");

{
ifstream fin("ferma2.in");
fin >> n >> k;

for(int i = 1; i <= n; i++)
for(int j = 1; j <= i; j++)
{
fin >> a[i][j];
stot += a[i][j];
}
fin.close();
}

void Sume_Partiale()
{
int i, j;

for (i = 1; i <= n; i++)
for (j = 1; j <= i; j++)
{
sl[i][j] = sl[i][j - 1] + a[i][j];
sc[i][j] = sc[i - 1][j] + a[i][j];
sd[i][j] = sd[i - 1][j - 1] + a[i][j];
}
}

void Solve()
{
int i, j, s(0);
int smin, suma;
int L = n - k; /// lg subtringhiului

/// Suma primului subtriunghi cu coltul in (1, 1)
for (i = 1; i <= L; i++)
s += sl[i][i];
smin = suma = s;

for (i = L + 1; i <= n; i++)
{
s = s - sd[i - 1][L] + sl[i][L];
suma = s;
smin = min(smin, suma);
for (j = L + 1; j <= i; j++)
{
suma = suma - (sd[i][j] - sd[i - L][j - L]) + sl[i][j] - sl[i][j - L];
smin = min(smin, suma);
}
}

fout << (stot - smin) << "\n";
}

int main()
{