Fişierul intrare/ieşire:cladiri.in, cladiri.outSursăLot Suceava 2007
AutorMarinel Serban, Stefan CiobacaAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.45 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cladiri

Harta orasului Avaecus este reprezentata ca o matrice cu N linii si M coloane. Un element al matricei are valoarea 1, daca el corespunde unei zone ocupate sau 0, daca zona respectiva este libera.
Primarul vrea sa construiasca o cladire, care va fi reprezentata in matrice sub forma unui dreptunghi cu W coloane si H linii. Evident, inainte de amplasarea cladirii, dreptunghiul din matrice acoperit de ea trebuie sa contina doar elemente libere (cu valoarea 0).
Deoarece primarul vrea sa pastreze deschise si alte oportunitati de constructie, vrea sa aseze noua cladire astfel incat, dupa amplasare, sa ramana libera o zona dreptunghiulara de dimensiune cat mai mare.

Cerinta

Ajutati-l pe primar sa amplaseze noua cladire.

Date de intrare

Fisierul de intrare cladiri.in contine pe prima linie numerele naturale nenule N si M, separate printr-un spatiu, reprezentand numarul de linii, respectiv numarul de coloane ale matricei. Pe cea de-a doua linie se gasesc, separate printr-un spatiu, numerele naturale nenule W si H, cu semnificatia din enunt. Pe urmatoarele N linii se gasesc cate M valori 0 sau 1, separate prin cate un spatiu, reprezentand matricea.

Date de iesire

Pe singura linie a fisierului de iesire cladiri.out afisati dimensiunea maxima a unei zone dreptunghiulare ramase libera dupa constructia noii cladiri. Dimensiunea unei zone este egala cu numarul de elemente ale matricei din care este formata.

Restrictii

  • 1 ≤ N, M ≤ 1000
  • 1 ≤ H ≤ N
  • 1 ≤ W ≤ M
  • Pentru datele de test exista intodeauna solutie.

Exemplu

cladiri.incladiri.out
4 5
2 2
0 1 1 1 1
1 1 1 0 0
0 0 0 0 0
0 0 1 1 0
4
6 5
3 2
0 1 1 1 1
0 0 0 0 0
0 0 0 0 0
0 1 1 0 0
1 1 1 0 0
1 1 1 0 0
10
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content