# Cod sursa(job #635800)

Utilizator Data 19 noiembrie 2011 14:57:00 Ferma2 10 cpp done .com 2011 1.56 kb
``````#include <fstream>
using namespace std;

ifstream fi ("ferma2.in");
ofstream fo ("ferma2.out");

const int dim = 1005;
int Po[dim][dim], Pv[dim][dim], Pd[dim][dim], A[dim][dim], N, K, S, SM, T;

void back (int x1, int y1, int x2, int y2, int k)
{
if (T < 0)
return;
T += 3500;

if (k == K)
{
SM = S > SM ? S : SM;
return;
}

S += Po[x2][y2] - Po[x2][y1-1];
back (x1, y1, x2-1, y2-1, k+1);
S -= Po[x2][y2] - Po[x2][y1-1];

S += Pv[x2][y1] - Pv[x1-1][y1];
back (x1+1, y1+1, x2, y2, k+1);
S -= Pv[x2][y1] - Pv[x1-1][y1];

S += Pd[x2][y2] - Pd[x1-1][y1-1];
back (x1+1, y1, x2, y2-1, k+1);
S -= Pd[x2][y2] - Pd[x1-1][y1-1];
}

void greedy (int x1, int y1, int x2, int y2, int k)
{
if (k == K)
{
SM = S > SM ? S : SM;
return;
}

int a = Po[x2][y2] - Po[x2][y1-1];
int b = Pv[x2][y1] - Pv[x1-1][y1];
int c = Pd[x2][y2] - Pd[x1-1][y1-1];
if (c > a && c > b)
{
S += c;
greedy (x1, y1, x2-1, y2-1, k+1);
S -= c;
}
else if (b > a && b > c)
{
S += b;
back (x1+1, y1+1, x2, y2, k+1);
S -= b;
}
else if (a > b && a > c)
{
S += a;
back (x1+1, y1, x2, y2-1, k+1);
S -= a;
}
else
{
fo << "error";
}
}

void cit ()
{
int i, j;
fi >> N >> K;
for (i = 1; i <= N; i++)
for (j = 1; j <= i; j++)
{
fi >> A[i][j];

Po[i][j] = A[i][j] + Po[ i ][j-1];
Pv[i][j] = A[i][j] + Pv[i-1][ j ];
Pd[i][j] = A[i][j] + Pd[i-1][j-1];
}
}

int main ()
{
cit ();

//back (1, 1, N, N, 0);
greedy (1, 1, N, N, 0);

fo << SM;

return 0;
}

``````