Problema Birocratie

Problema Birocratie

fișier de intrare xxxxxxxxxx.xx

fișier de ieșire birocratie.out

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

×

Xxxxx 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 𝑁 𝑁 . 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 𝑁 . Mai exact, la linia 𝑖, coloana 𝑗 se găsește biroul (𝑖, 𝑗).

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

• pe același rând doar de la stânga la dreapta: (𝑖, 𝑗) → (𝑖, 𝑗 + 1);

• pe aceeași coloană doar de sus în jos: (𝑖, 𝑗) → (𝑖 + 1, 𝑗);

• în sens diagonal în următoarele două direcții:

– (𝑖, 𝑗) → (𝑖 + 1, 𝑗 − 1), dar și

– (𝑖, 𝑗) → (𝑖 − 1, 𝑗 + 1).

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

( ) ( )

De câte ori Xxxxx vizitează un birou 𝑖, 𝑗 el încheie un contract în valoare de 𝐵 𝑖, 𝑗 lei. Dacă

( ) ( ) ( ) − ( )

𝐵 𝑖, 𝑗 > 0, atunci el primește 𝐵 𝑖, 𝑗 lei, iar dacă 𝐵 𝑖, 𝑗 < 0, el plătește 𝐵 𝑖, 𝑗 lei. Scopul lui Xxxxx 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ă Xxxxx plătește mai mult decât primește.

Cerință

( ) ≤ ≤

Cunoscând planul birourilor și valorile 𝐵 𝑖, 𝑗 pentru 1 𝑖, 𝑗 𝑁 care îl așteaptă pe Xxxxx î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.inconține pe prima linie numărul 𝑁 , iar pe următoarele 𝑁 linii câte 𝑁 numere întregi separate prin spații, reprezentând valorile 𝐵 (𝑖, 𝑗) pentru 1 ≤ 𝑖, 𝑗 ≤ 𝑁 .

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

• 5 ≤ 𝑁 ≤ 1 000

• −1 000 ≤ 𝐵 (𝑖, 𝑗) ≤ 1 000 pentru 1 ≤ 𝑖, 𝑗 ≤ 𝑁 .

#	Punctaj	Restricții
1	12	𝐵 are toate elementele pozitive, 𝑁 ≤ 300.
2	12	𝐵 are toate elementele egale și negative, 𝑁 ≤ 300.

3 15 Pe fiecare diagonală paralelă cu diagonala secundară elementele din 𝐵 sunt egale, 𝑁 ≤ 300.

4 13 Elementele de pe chenarul lui 𝐵 sunt negative, iar celelalte elemente sunt pozitive, 𝑁 ≤ 300.

5 13 Toate elementele din 𝐵 sunt egale în valoare absolută (modul), elementele de pe chenar sunt pozitive, iar celelalte elemente sunt negative, 𝑁 ≤ 300.

6 16 𝑁 ≤ 300

7 19 fără restricții suplimentare.

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

Exemple

xxxxxxxxxx.xx	xxxxxxxxxx.xxx	Explicații
5	42	Câștigul maxim este 42,
1 2 5 8 2		obiinut adunând elementele
1 3 -10 2 1		evideniiate în traseul
0 9 1 -7 3		ilustrat mai jos.
-2 3 4 -1 2
		3 -4 2 3 1

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