# PBinfo #4611 – birocratie2 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Boris este un afacerist de succes, având contracte care aduc pe de o parte venituri (dobânzi, comisioane etc.) dar și obligații la taxe (impozite, rate etc.).  

Boris s-a hotărât să viziteze o clădire de birouri. Clădirea are un singur nivel în care birourile sunt lipite unele de altele formând un caroiaj pătratic de dimensiune N x N. Planul birourilor se poate reprezenta ca o matrice pătratică, unde birourile sunt elemente din matrice cu liniile și coloanele numerotate de la 1 la N. Mai exact, la linia i, coloana j se găsește biroul (i, j). 

Boris va intra în clădire prin biroul (1, 1) și va trece printr-o serie de birouri. Traseul se va termina în biroul (N, N). La trecerea dintr-un birou în altul se permite:


pe același rând doar de la stânga la dreapta: (i, j) → (i, j+1);
pe aceeași coloană doar de sus în jos: (i, j) → (i+1, j);
în sens diagonal în următoarele două direcții: (i, j) → (i+1, j-1), dar și (i, j) → (i-1, j+1).

Totuși, Boris nu se va mai întoarce niciodată într-un birou din care a ieșit.

De câte ori Boris vizitează un birou (i, j) el încheie un contract în valoare de B(i, j) lei. Dacă B(i, j) > 0, atunci el primește B(i, j) lei, iar dacă B(i, j) < 0, el plătește -B(i, j) lei. Scopul lui Boris este acela de a ieși din clădire cu un câștig total maxim. Câștigul se definește ca fiind totalul de bani primiți minus totalul de bani plătiți pe traseu.

Atenție! Câștigul poate să fie și negativ dacă Boris plătește mai mult decât primește.

Cerința
Cunoscând planul birourilor și valorile B(i, j) pentru 1 ≤ i, j ≤ N care îl așteaptă pe Boris în fiecare birou, ajutați-l să calculeze câștigul maxim pe care îl poate avea la ieșirea din clădire.

Date de intrare
Fișierul de intrare birocratie.in conține pe prima linie numărul N, iar pe următoarele N linii câte N numere întregi separate prin spații, reprezentând valorile B(i, j) pentru 1 ≤ i, j ≤ N.

Date de ieșire
Fișierul de ieșire birocratie.out va conține o singură linie pe care se află un singur număr întreg reprezentând câștigul maxim posibil.

Restricții și precizări

5 ≤ N ≤ 1000
-1000 ≤ B(i,j) ≤ 1000 pentru 1 ≤ i, j ≤ N
Pentru 12 puncte, B are toate elementele pozitive, N ≤ 300
Pentru 12 puncte, B are toate elementele egale și negative, N ≤ 300
Pentru 15 puncte, Pe fiecare diagonală paralelă cu diagonala secundară elementele din B sunt egale, N ≤ 300
Pentru 13 puncte, Elementele de pe chenarul lui B sunt negative, iar celelalte elemente sunt pozitive, N ≤ 300
Pentru 13 puncte, Toate elementele din B sunt egale în valoare absolută (modul), elementele de pe chenar sunt pozitive, iar celelalte  elemente sunt negative, N ≤ 300
Pentru 16 puncte, N ≤ 300
Pentru 19 puncte, Fără restricții suplimentare.

Mai sus prin chenarul lui B ne referim la elementele care se află pe prima/ultima linie și prima/ultima coloană.

Exemplu:
birocratie.in

5
1 2 5 8 2
1 3 -10 2 1
0 9 1 -7 3
-2 3 4 -1 2
3 -4 2 3 1
birocratie.out

42
Explicație
Câștigul maxim este 42, obținut adunând elementele evidențiate în traseul ilustrat mai jos.

## Cod sursă C++

```cpp
/// Szabo Zoltan   Comlexitate O(n^2)    100 de puncte
#include <fstream>
using namespace std;
ifstream cin("birocratie.in");
ofstream cout("birocratie.out");
/*void tipar(int B[][302],int n)
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
            fout<<B[i][j]<<" ";
        fout<<endl;
    }
}
*/
int d,n,B[1002][1002],SUM, MAXIM[1002][1002],VECTMAX1[1002],VECTMAX2[1002];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cin>>B[i][j];
    for(int i=0 ; i<=n ; i++)
        for(int j=0 ; j<=n ; j++)
            MAXIM[i][j]=-2000000000;
    MAXIM[1][1]=B[1][1];
    for(int i=2 ; i<=n ; i++)
    {
        for(int j=1;j<=n;j++)
            VECTMAX1[j]=-2000000000;
        int l=i;
        int c=1;
        if(l-1>0 and MAXIM[l-1][c]+B[l][c]>VECTMAX1[c])
            VECTMAX1[c]=MAXIM[l-1][c]+B[l][c];
        if(c-1>0 and MAXIM[l][c-1]+B[l][c]>VECTMAX1[c])
            VECTMAX1[c]=MAXIM[l][c-1]+B[l][c];
        while(l>1 and c<n)
        {
            l--;c++;
            if(l-1>0 and MAXIM[l-1][c]+B[l][c]>VECTMAX1[c])
                VECTMAX1[c]=MAXIM[l-1][c]+B[l][c];
            if(c-1>0 and MAXIM[l][c-1]+B[l][c]>VECTMAX1[c])
                VECTMAX1[c]=MAXIM[l][c-1]+B[l][c];
            if(c-1>0 and VECTMAX1[c-1]+B[l][c]>VECTMAX1[c])
                VECTMAX1[c]=VECTMAX1[c-1]+B[l][c];
        }
        for(int j=1;j<=n;j++)
            VECTMAX2[j]=-2000000000;
        l=1;
        c=i;
        if(l-1>0 and MAXIM[l-1][c]+B[l][c]>VECTMAX2[c])
            VECTMAX2[c]=MAXIM[l-1][c]+B[l][c];
        if(c-1>0 and MAXIM[l][c-1]+B[l][c]>VECTMAX2[c])
            VECTMAX2[c]=MAXIM[l][c-1]+B[l][c];
        MAXIM[l][c]=max(VECTMAX1[c],VECTMAX2[c]);
        while(l<n and c>1)
        {
            l++;c--;
            if(c-1>0 and MAXIM[l-1][c]+B[l][c]>VECTMAX2[c])
                VECTMAX2[c]=MAXIM[l-1][c]+B[l][c];
            if(l-1>0 and MAXIM[l][c-1]+B[l][c]>VECTMAX2[c])
                VECTMAX2[c]=MAXIM[l][c-1]+B[l][c];
            if(c+1<=n and VECTMAX2[c+1]+B[l][c]>VECTMAX2[c])
                VECTMAX2[c]=VECTMAX2[c+1]+B[l][c];
            MAXIM[l][c]=max(VECTMAX1[c],VECTMAX2[c]);
        }
    }
    for(int j=2 ; j<=n ; j++)
    {
        for(int i=1;i<=n;i++)
            VECTMAX1[i]=-2000000000;
        int l=n;
        int c=j;
        if(l-1>0 and MAXIM[l-1][c]+B[l][c]>VECTMAX1[c])
            VECTMAX1[c]=MAXIM[l-1][c]+B[l][c];
        if(c-1>0 and MAXIM[l][c-1]+B[l][c]>VECTMAX1[c])
            VECTMAX1[c]=MAXIM[l][c-1]+B[l][c];
        while(l>1 and c<n)
        {
            l--;c++;
            if(l-1>0 and MAXIM[l-1][c]+B[l][c]>VECTMAX1[c])
                VECTMAX1[c]=MAXIM[l-1][c]+B[l][c];
            if(c-1>0 and MAXIM[l][c-1]+B[l][c]>VECTMAX1[c])
                VECTMAX1[c]=MAXIM[l][c-1]+B[l][c];
            if(c-1>0 and VECTMAX1[c-1]+B[l][c]>VECTMAX1[c])
                VECTMAX1[c]=VECTMAX1[c-1]+B[l][c];
        }
        for(int i=1;i<=n;i++)
            VECTMAX2[i]=-2000000000;
        l=j;
        c=n;
        if(l-1>0 and MAXIM[l-1][c]+B[l][c]>VECTMAX2[c])
            VECTMAX2[c]=MAXIM[l-1][c]+B[l][c];
        if(c-1>0 and MAXIM[l][c-1]+B[l][c]>VECTMAX2[c])
            VECTMAX2[c]=MAXIM[l][c-1]+B[l][c];
        MAXIM[l][c]=max(VECTMAX1[c],VECTMAX2[c]);
        while(l<n and c>1)
        {
            l++;c--;
            if(c-1>0 and MAXIM[l-1][c]+B[l][c]>VECTMAX2[c])
                VECTMAX2[c]=MAXIM[l-1][c]+B[l][c];
            if(l-1>0 and MAXIM[l][c-1]+B[l][c]>VECTMAX2[c])
                VECTMAX2[c]=MAXIM[l][c-1]+B[l][c];
            if(c+1<=n and VECTMAX2[c+1]+B[l][c]>VECTMAX2[c])
                VECTMAX2[c]=VECTMAX2[c+1]+B[l][c];
            MAXIM[l][c]=max(VECTMAX1[c],VECTMAX2[c]);
        }
    }
    cout<<MAXIM[n][n];
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4611)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4611/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4611/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)