== include(page="template/taskheader" task_id="fence") ==
Poveste şi cerinţă...
Un proprietar vinde un teren de formă dreptunghiulară împărţit în $M × N$ parcele de formă pătrată cu lungimea laturii de o unitate. Fiecare parcelă costă $V$ lei. Vlad s-a interesat şi a aflat pentru fiecare din parcelele terenului care este valoarea de revânzare. El constată că unele parcele i-ar putea aduce profit, iar altele i-ar aduce pierdere. Fiind isteţ, negociază cu proprietarul să cumpere atâtea parcele de teren câte pot fi împrejmuite cu un singur gard de lungime egală cu $2M + 2N$ unităţi. Terenul are pe fiecare din cele patru laturi acces la drumul exterior, pe o porţiune de lungime egală cu o unitate. Vlad negociază astfel încât terenul achiziţionat să conţină şi cele patru parcele de acces la exterior.
h2. Cerinţă
Cunoscând $M$ şi $N$ (dimensiunile terenului), $V$ (preţul de cumpărare al fiecărei parcele), $x_nord$, $x_sud$, $y_vest$ şi $y_est$ (poziţiile parcelelor cu acces la drumul exterior) şi $A[i][j], 1 ≤ i ≤ M şi 1 ≤ j ≤ N$ (valorile de revânzare pentru fiecare parcelă), să se determine:
* Profitul **$P_arie_minimă$** pe care-l poate obţine Vlad după cumpărarea şi apoi revânzarea suprafeţei de teren de arie minimă, împrejmuită conform condiţiilor negociate.
* Profitul maxim **$P_max$** pe care-l poate obţine Vlad după cumpărarea şi apoi revânzarea unei suprafeţe de teren împrejmuită conform condiţiilor negociate.
h2. Date de intrare
Fişierul de intrare $fence.in$ ...
Fişierul de intrare $fence.in$ conţine pe prima linie numărul $t$. Pentru toate testele de intrare numărul $t$ poate avea doar valoarea $1$ sau valoarea $2$.
Pe linia a doua se găsesc numerele $M$, $N$, $V$, $x_nord$, $x_sud$, $y_vest$ şi $y_est$ separate prin câte un spaţiu, iar pe următoarele $M$ linii se află câte $N$ numere naturale separate prin câte un spaţiu, reprezentând valorile de revânzare ale celor $M × N$ parcele de teren.
h2. Date de ieşire
În fişierul de ieşire $fence.out$ ...
Dacă valoarea lui $t$ este $1$, atunci se va rezolva numai primul punct din cerinţă.
În acest caz în fişierul de ieşire $fence.out$ se va scrie pe prima linie numărul **$P_arie_minimă$**.
Dacă valoarea lui $t$ este $2$, atunci se va rezolva numai al doilea punct din cerinţă.
În acest caz în fişierul de ieşire $fence.out$ se va scrie pe prima linie numărul **$P_max$**.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $3 ≤ M ≤ 1 000$
* $3 ≤ N ≤ 1 000$
* $1 000 ≤ V ≤ 10 000$
* $1 ≤ A[i][j] ≤ 20 000$
* $2 ≤ x_nord, x_sud ≤ N-1$
* $2 ≤ y_vest, y_est ≤ M-1$
* $(x_nord - x_sud) × (y_est - y_vest) ≥ 0$
* Prin profit se înţelege suma valorilor de revânzare corespunzătoare parcelelor din suprafaţa împrejmuită din care se scade produsul dintre preţul de cumpărare $V$ şi numărul parcelelor împrejmuite, care poate fi şi negativ.
* Pentru rezolvarea corectă a primei cerinţe se va obţine $20%$ din punctaj.
* Pentru $33%$ din testele corespunzătoare celei de-a doua cerinţe va fi îndeplinită condiţia $M, N ≤ 15$.
h2. Exemplu
table(example). |_. fence.in |_. fence.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 1
5 7 6 3 5 3 2
3 5 8 4 9 8 7
9 3 7 6 4 5 9
6 6 8 2 5 4 8
3 3 4 7 7 2 1
8 7 9 2 8 4 2 | 3 |
| 2
5 7 6 3 5 3 2
3 5 8 4 9 8 7
9 3 7 6 4 5 9
6 6 8 2 5 4 8
3 3 4 7 7 2 1
8 7 9 2 8 4 2 | 8 |
h3. Explicaţie
...
$M=5, N=7, V=6, x_nord=3, x_sud=5, y_vest=3, y_est=2$
* În primul exemplu: $**P_arie_minimă** = (8+7+6+4+5+9+6+6+8+2+5+7+8) - 6*13 = 81-78 = 3$
!problema/fence?fence1.png!
* În al doilea exemplu: $**P_max** = (8+4+9+8+7+7+6+4+5+9+6+6+8+2+5+7+7+8) - 6*18 = 116-108 = 8$
!problema/fence?fence2.png!
== include(page="template/taskfooter" task_id="fence") ==
