Fişierul intrare/ieşire:petrol.in, petrol.outSursăOlimpiada pe Scoala 2012, Clasele 11-12
AutorVictor ManzAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inpetrol.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

Trebuie sa te autentifici pentru a trimite solutii. Click aici