# Cod sursa(job #636620)

Utilizator Data 19 noiembrie 2011 21:51:25 Ferma2 30 cpp done .com 2011 1.43 kb
``````#include <cstdio>
#include <cassert>
#define Nmax 1005
#define InFile "ferma2.in"
#define OutFile "ferma2.out"

using namespace std;

int n, K;
int N[Nmax][Nmax], lin[Nmax][Nmax], col[Nmax][Nmax], diag[Nmax][Nmax];
int M[2][Nmax][Nmax];

void sume();
void solve();

int main()
{
assert (freopen (InFile, "r", stdin));
assert (freopen (OutFile, "w", stdout));
sume();
solve();
return 0;
}

{
int i, j;
scanf ("%d %d\n", &n, &K);
for (i=1; i<=n; i++)
for (j=1; j<=i; j++)
scanf ("%d\n", &N[i][j]);
}

void sume()
{
int i, j, k;
//linii
for (i=1; i<=n; i++)
for (j=1; j<=i; j++)
lin[i][j]=lin[i][j-1]+N[i][j];

//coloane
for (j=1; j<=n; j++)
for (i=j; i<=n; i++)
col[i][j]=col[i-1][j]+N[i][j];

//diagonale
for (i=1; i<=n; i++)
for (j=i, k=1; j<=n; j++, k++)
diag[j][k]=diag[j-1][k-1]+N[j][k];
}

void solve()
{
int z, i, j, cr=1, ant=0, k=n-K+1, Max, nr;
for (z=1; z<=K; z++)
{
for (i=k; i<=n; i++)
for (j=1; j<=i-k+1; j++)
{
Max=M[ant][i-1][j]+(lin[i][j+k]-lin[i][j]);

nr=M[ant][i][j+1]+(col[i][j]-col[i-k][j]);
if (nr>Max) Max=nr;

nr=M[ant][i][j]+(diag[i][j+k-1]-diag[i-k][j-1]);
if (nr>Max) Max=nr;
M[cr][i][j]=Max;
}
k++; ant^=1; cr^=1;
}
printf ("%d\n", M[ant][n][1]);
}
``````