# Cod sursa(job #636596)

Utilizator Data 19 noiembrie 2011 21:38:58 Ferma2 10 cpp done .com 2011 1.26 kb
``````#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int N , a[1005][1005] , K , sol = 0 , linie = 0 , col = 0 , diag = 0;

void up_linie (int D)
{
linie = 0;

for (int i = D ; i <= N ; ++i)
linie += a[i][D];
}
void up_col (int D)
{
col = 0;

for (int i = 1 ; i <= N - D + 1 ; ++i)
col += a[N - D + 1][i];
}
void up_diag (int D)
{
diag = 0;

for (int i = D ; i <= N ; ++i)
diag += a[i][i - D + 1];
}

int main ()
{
freopen ("ferma2.in" , "r" , stdin);
freopen ("ferma2.out" , "w" , stdout);

scanf ("%d %d" , &N , &K);

for (int i = 1 ; i <= N ; ++i)
for (int j = 1 ; j <= i ; ++j)
scanf ("%d" , &a[i][j]);

for (int i = 1 ; i <= N ; ++i)
{
linie += a[i][1];
diag += a[i][i];
col += a[N][i];
}

int dim = N , aux;

for (int t = 1 ; t <= K ; ++t)
{
aux = max (max (linie , col) , diag);

sol += aux;

if (aux == linie)
{
up_linie(t + 1);
diag -= a[t][t];
col -= a[dim][t];
}

else if (aux == col)
{
up_col(t + 1);
linie -= a[dim][1];
diag -= a[dim][dim];
--dim;
}

else
{
up_diag (t + 1);
linie -= a[t][1];
col -= a[dim][dim - t + 1];
}
}

printf ("%d" , sol);

return 0;
}
``````