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 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.
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.
Date de ieșire
Î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.
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
Exista doua submatrice patrate de latura 2, cu suma 3. Va fi afisata cea cu coltul stanga sus (1,1).
Cea mai mare
