# Cod sursa(job #2361169)

Utilizator Data 2 martie 2019 13:33:07 Ferma2 20 cpp-64 done Arhiva de probleme 1.27 kb
``````#include <fstream>

using namespace std;

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

int a[1005][1005], col[1005], lin[1005], ipo[1005];
int sp[1005][1005], sp1[1005][1005], sp2[1005][1005];
int d, Max, n, k, x;

int main()  {
fin >> n >> k;
for (int i = 1; i <= n; ++i)  {
for (int j = 1; j <= i; ++j)  {
fin >> a[i][j];
col[j] += a[i][j];
lin[n - i + 1] += a[i][j];
ipo[i - j + 1] += a[i][j];
}
}
for (int i = 1; i <= n; ++i)  {
for (int j = 1; j <= n; ++j)
sp[i][j] = sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1] + a[i][j];
}
for (int i = n; i; --i)  {
for (int j = 1; j <= n; ++j)
sp1[i][j] = sp1[i + 1][j] + sp1[i][j - 1] - sp1[i + 1][j - 1] + a[i][j];
for (int j = n; j; --j)
sp2[i][j] = sp2[i + 1][j] + sp2[i][j + 1] - sp2[i + 1][j + 1] + a[i][j];
}
for (int i = 2; i <= n; ++i)  {
col[i] += col[i - 1];
lin[i] += lin[i - 1];
ipo[i] += ipo[i - 1];
}
for (int i = 0; i <= k; ++i)  {
for (int j = 0; i + j <= k; ++j)  {
d = k - i - j;
x = col[i] + lin[j] + ipo[d] - sp[d][i] - sp1[n - j + 1][i] - sp2[n - j + 1][d];
if (x > Max)  {
Max = x;
//        fout << x << ' ' << i << ' ' << j << ' ' << d << '\n';
}
}
}
fout << Max;
return 0;
}
``````