Revizia anterioară Revizia următoare
| Fișierul intrare/ieșire | petrol.in, petrol.out | Sursă | Olimpiada pe Scoala 2012, Clasele 11-12 |
|---|---|---|---|
| Autor | Victor Manz | Adăugată de |
Victor Manz
•
vmanz
|
| Timp de execuție pe test | 0.25 sec | Limită de memorie | 16384 KB |
| Scorul tău | N/A | Dificultate |
  0.75
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Petrol
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ă.
Date de intrare
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 \( x_{i} \), reprezentând latura pătratului pentru care se cere profitul maxim.
Date de ieșire
Fișierul de ieșire petrol.out va conține q rânduri. Pe fiecare dintre acestea se va afla răspunsul pentru întrebarea corespunzătoare, sub forma a trei numere întregi separate prin câte un spațiu: profitul maxim care poate fi obținut, indicele liniei colțului stânga sus și respectiv indicele coloanei colțului stânga sus al pătratului cu profit total maxim. Dacă există mai multe pătrate care aduc profit maxim, se va alege cel cu indicele liniei cel mai mic și în caz de egalitate și pentru acesta, cel cu indicele coloanei cel mai mic.
Restricții
- 1 ≤ m ≤ 500
- 1 ≤ n ≤ 500
- -1000 ≤ a[i][j] ≤ 1000, pentru orice 1 ≤ i ≤ m, 1 ≤ j ≤ n
- 1 ≤ q ≤ 500
- 1 ≤ xi ≤ 1000
Exemplu
| petrol.in | petrol.out |
|---|---|
| 2 3 1 -1 2 2 1 1 2 2 1 |
3 1 1 2 1 3 |
Explicație
Există două submatrici pătrate de latură 2, cu suma 3. Va fi afișată cea cu colțul stânga sus (1,1).
