| Fişierul intrare/ieşire: | teren.in, teren.out | Sursă | preONI 2008 Runda 1 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Mircea Pasoi •domino |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Teren
Zaharel vrea sa-si construiasca o casa de vacanta undeva la munte. Intai trebuie sa-si aleaga locul unde isi va construi casa. El detine un teren de forma dreptunghiulara care are N metri lungime si M metri latime. Pentru fiecare bucata de 1×1 metri din teren se stie daca este buna sau nu pentru a construi pe ea.
Casa pe care vrea Zaharel sa o construiasca va fi de forma dreptunghiulara si va avea laturile paralele cu laturile terenului. Zaharel nu vrea sa aiba foarte mult bucati de teren stricate si in plus vrea o casa cat mai mare, asa ca trebuie sa determine o portiune dreptunghiulara din teren de arie maxima care nu contine mai mult de X bucati de 1×1 metri stricate.
Date de intrare
Fisierul de intrare teren.in va contine pe prima linie numerele naturale N M X. Urmatoarele N linii vor contine cate M valori separate prin spatii, care descriu starea fiecare bucati 1×1 din teren. O valoare de 0 inseamna ca pe acea bucata se poate construi, iar o valoare de 1 inseamna ca pe acea bucata nu se poate construi.
Date de iesire
In fisierul de iesire teren.out se va scrie un singur numar natural reprezentand aria maxima posibila a casei.
Restrictii
- 1 ≤ N, M ≤ 300
- 0 ≤ X ≤ N*M
Exemplu
| teren.in | teren.out |
|---|---|
| 3 5 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 | 9 |
Explicatie
Zona ingrosata reprezinta o solutie posibila:
0 0 0 0 1
0 1 0 0 0
0 0 0 1 0
