== include(page="template/taskheader" task_id="cladiri") ==
Poveste si cerinta...
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.
h2. Cerinta
Ajutati-l pe primar sa amplaseze noua cladire.
h2. 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.
h2. 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.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 1000$
* $1 ≤ H ≤ N$
* $1 ≤ W ≤ M$
* Pentru datele de test exista intodeauna solutie.
h2. Exemplu
table(example). |_. cladiri.in |_. cladiri.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
...
| 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 |
== include(page="template/taskfooter" task_id="cladiri") ==
