== include(page="template/taskheader" task_id="dreptunghi1") ==
Poveste și cerință...
Dată o matrice dreptunghiulară cu elemente $0$ și [$1$], care este aria maximă a unui dreptunghi format numai din elemente [$1$]?
h2. Date de intrare
Fișierul de intrare $dreptunghi1.in$ ...
Pe prima linie a fișierului $dreptunghi1.in$ se vor găsi trei numere: numărul de linii, [$m$], al matricei, numărul de coloane, [$n$], precum și numărul $z$ al elementelor $0$ din matrice. Pe următoarele $z$ linii vom avea cîte o pereche de numere $lin$ și [$col$], separate printr-un spațiu, cu semnificația că elementul de la linia $lin$ și coloana $col$ este [$0$]. Restul elementelor matricei sînt [$1$]. Este posibil ca $z$ să fie [$0$], caz în care nu vom mai avea nici o linie extra. De asemenea este posibil ca anumite perechi $lin$ și $col$ să se repete.
h2. Date de ieșire
În fișierul de ieșire $dreptunghi1.out$ ...
Fișierul $dreptunghi1.out$ va conține un singur număr, aria celui mai mare dreptunghi plin cu [$1$].
h2. Restricții
* $... ≤ ... ≤ ...$
* $1 ≤ m, n ≤ 10000$
* $0 ≤ z ≤ 10000$
* perechile $lin$ și $col$ sînt coordonate corecte în matrice, nu neapărat unice
* pentru 20% din teste $1 ≤ m, n ≤ 30$
* pentru 40% din teste $1 ≤ m, n ≤ 100$
h2. Exemplu
table(example).
|_. dreptunghi1.in |_. dreptunghi1.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. dreptunghi1.in |_. dreptunghi1.out |_. Explicație |
| 6 6 3
4 1
4 5
3 3
| 12
| Matricea este:
111111
111111
110111
011101
111111
111111
cel mai mare dreptunghi are arie 12
|
| 5 8 4
5 2
1 5
2 5
5 7
| 16
| Matricea este:
11110111
11110111
11111111
11111111
10111101
sînt trei dreptunghiuri de arie maximă, unul 2x8 și două 4x4
|
== include(page="template/taskfooter" task_id="dreptunghi1") ==
== include(page="template/taskfooter" task_id="dreptunghi1") ==
