== include(page="template/taskheader" task_id="rama") ==
Poveste şi cerinţă...
Marian, mergand linistit pe strada, a gasit o bancnota de $100$ RON pe care era scrisa o matrice binara. Pentru a putea cumpara ceva cu respectiva bancnota, Marian trebuie sa gaseasca dreptunghiul de arie maxima continut in intregime in matrice, care are pe laturi numai elemente egale cu $1$ (indiferent ce ar contine strict in interior). Marian nu stie, insa va roaga pe voi sa-l ajutati!
h2. Date de intrare
Fişierul de intrare $rama.in$ ...
Fişierul de intrare $rama.in$ contine pe prima linie doua numere naturale $N$ si $M$, separate printr-un spatiu, reprezentand numarul de linii, respectiv numarul de coloane ale matricei binare. Pe urmatoarele $N$ linii se gasesc cate $M$ caractere egale cu $1$ sau $0$, reprezentand matricea binara gasita de Marian.
h2. Date de ieşire
În fişierul de ieşire $rama.out$ ...
În fişierul de ieşire $rama.out$ trebuie sa afisati pe prima linie un singur numar natural: aria maxima a unui dreptunghi care are pe laturi numai elemente egale cu $1$.
h2. Restricţii
h2. Restricţii si precizari
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 700$
* $2 ≤ M ≤ 700$
* O matrice binara este o matrice care contine numai elemente de $1$ si $0$.
* Dreptunghiul format dintr-un singur element de $1$ se considera valid.
h2. Exemplu
table(example). |_. rama.in |_. rama.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 5
10101
10111
10101
10111
01111
| 12
|
h3. Explicaţie
...
Dreptunghiul de arie maxima are coltul stanga-sus in pozitia $(2, 3)$, iar coltul dreapta-jos in pozitia $(5, 5)$. Existau si alte posibilitati, dar de arie mai mica: $(1, 1) -> (1, 4)$ sau $(4, 3) -> (5, 4)$.
== include(page="template/taskfooter" task_id="rama") ==
