Diferențe pentru problema/petrol între reviziile #1 si #2

petrol

Petrol

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

Poveste și cerință...

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.

h2. Date de intrare

Fișierul de intrare $petrol.in$ ...

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, reprezentand latura patratului pentru care se cere profitul maxim.

h2. Date de ieșire

În fișierul de ieșire $petrol.out$ ...

În fișierul de ieșire $petrol.out$ va contine q randuri. Pe fiecare dintre acestea se va afla raspunsul pentru intrebarea corespunzatoare, sub forma a trei numere intregi separate prin cate un spatiu: profitul maxim care poate fi obtinut, indicele liniei coltului stanga sus si respectiv indicele coloanei coltului stanga sus al patratului cu proit total maxim. Daca exista mai multe patrate care aduc profit maxim, se va alege cel cu indicele liniei cel mai mic si in caz de egalitate si pentru acesta, cel cu indicele coloanei cel mai mic.

h2. Restricții

* $... ≤ ... ≤ ...$

* $1 ≤ m ≤ 1000$
* $1 ≤ n ≤ 1000$
* $-1000 ≤ a[i][j] ≤ 1000, pentru orice 1 ≤ i ≤ m$, $1 ≤ j ≤ n$
 

h2. Exemplu