# Cod sursa(job #1783585)

Utilizator Data 19 octombrie 2016 09:45:53 Ferma2 100 cpp done Arhiva de probleme 1.15 kb
``````#include <bits/stdc++.h>
using namespace std;
ifstream f("ferma2.in");
ofstream g("ferma2.out");
const int nMax = 1003;
int lin[nMax][nMax];
int col[nMax][nMax];
int diag[nMax][nMax];
int n , k , x, total;
inline void Solve() {
int lim = n - k , sumlin = 0, sol, suma = 0;
for(int i = 1; i <= lim; i++) {
sumlin += lin[i][i];
}
sol = suma = sumlin;
for(int i = 2; i <= k + 1; i++) {

suma = sumlin = sumlin += lin[i + lim - 1][lim] - diag[i + lim - 2][lim];
sol = min(sol, suma);
for(int j = 2; j <= i; j++) {

suma = suma - (col[i + lim - 1][j - 1] - col[i - 1][j - 1]) +
(diag[i + lim - 1][j + lim - 1] - diag[i - 1][j - 1]);
sol = min(sol, suma);
}

}
g<< total - sol << "\n";
}
int main()
{

f >> n >> k;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= i; j++) {
f >> x;
total += x;
lin[i][j] = lin[i][j - 1] + x;
col[i][j] = col[i - 1][j] + x;
diag[i][j] = diag[i - 1][j - 1] + x;
}
}
Solve();
return 0;
}
``````