| Fişierul intrare/ieşire: | cladiri.in, cladiri.out | Sursă | Lot Suceava 2007 |
| Autor | Marinel Serban, Stefan Ciobaca | Adăugată de |  Bogdan-Cristian Tataroiu •bogdan2412 |
| Timp execuţie pe test | 0.225 sec | Limită de memorie | 24576 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | cladiri.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 |
