Diferențe pentru problema/petrol între reviziile #7 si #8

== include(page="template/taskheader" task_id="petrol") ==

De curand, in Marea Alba au fost descoperite importante zacaminte de petrol. Desigur, exista numeroase firme dornice sa exploateze aceasta resursa. Harta intregii zone este o matrice cu m linii si n coloane. Fiecare element al acesteia este un numar intreg reprezentand diferenta intre cheltuielile necesare exploatarii si profitul estimat. Statul insa a impus anumite restrictii privind concesionarea zonelor petrolifere. Acestea trebuie sa fie patrate compacte. Firma VMO doreste (ca intotdeauna) sa obtina un profit cat mai mare. In acest scop va angajeaza sa scrieti un program care sa calculeze care e profitul maxim care poate fi obtinut pentru zone patrate de o anumita latura.

De curând, în Marea Albă au fost descoperite importante zăcăminte de petrol. Desigur, există numeroase firme dornice să exploateze această resursă. Harta întregii zone este o matrice cu $m$ linii si $n$ coloane. Fiecare element al acesteia este un număr întreg reprezentând diferența dintre cheltuielile necesare exploatării și venitul estimat. Statul însa a impus anumite restricții privind concesionarea zonelor petrolifere. Acestea trebuie să fie pătrate compacte. Firma VMO dorește (ca întotdeauna) să obțină un profit cât mai mare. În acest scop vă angajeaza să scrieți un program care să calculeze care e profitul maxim care poate fi obținut pentru zone pătrate de o anumită latură.

h2. Date de intrare

Fișierul de intrare $petrol.in$ contine pe prima linie numarul de linii, m, si numarul de coloane, n, separate printr-un spatiu, iar pe urmatoarele m linii cate n numere intregi a[i][j] (1 ≤ i ≤ m, 1 ≤ j ≤ n), separate prin cate un spatiu, reprezentand harta data. Pe cel de-al m+2 - rand se afla un numar natural q, reprezentand numarul de intrebari, iar pe urmatoarele q linii cate un numar natural nenul xi, reprezentand latura patratului pentru care se cere profitul maxim.

Fișierul de intrare $petrol.in$ conține pe prima linie numărul de linii, $m$, si numărul de coloane, $n$, separate printr-un spațiu, iar pe următoarele $m$ linii câte $n$ numere întregi $a[i][j]$ ($1 ≤ i ≤ m, 1 ≤ j ≤ n$), separate prin câte un spațiu, reprezentând harta dată. Pe cel de-al $m+2$ - lea rând se află un număr natural $q$, reprezentând numărul de întrebări, iar pe următoarele $q$ linii câte un număr natural nenul $xi$, reprezentând latura pătratului pentru care se cere profitul maxim.

h2. Date de ieșire

h2. Exemplu

table(example).

table(example).

|_. petrol.in |_. petrol.out |
| 2 3
1 -1 2