trmax

Trmax

== include(page="template/taskheader" task_id="trmax") ==

Poveste şi cerinţă...

Ligia are o matrice de $N$ linii pe $M$ coloane plina cu valori $0$ si $1$. Ea se intreaba care este cel mai mare triunghi ce poate fi plasat in matrice doar pe elemente egale cu $0$. Un triunghi de inaltime $L$ este format din $L$ linii si lungimea fiecarei linii este cu $2$ mai mare decat lungimea liniei anterioare (mai putin prima linie care are lungime $1$). De exemplu un triunghi de inaltime $5$ arata astfel:
 
# $....{**0**}....$
# $...{**000**}...$
# $..{**00000**}..$
# $.{**0000000**}.$
# ${**000000000**}$
 
Ligia vrea sa stie aria maxima a unui triunghi ce poate fi plasat in matrice, astfel incat sa acopere doar elemente egale cu $0$. Aria unui triunghi este egala cu numarul de pozitii ocupate de acel triunghi.

h2. Date de intrare

Fişierul de intrare $trmax.in$ ...

Fişierul de intrare $trmax.in$ va contine pe prima linie trei numere $N$, $M$, si $K$. Urmatoarele $K$ linii vor contine fiecare cate doua numere $l{~i~}$, $c{~i~}$ reprezentand faptul ca pe linia $l{~i~}$ si coloana $c{~i~}$ se afla un element de valoare $1$. Toate celelalte elemente ale matricei vor fi egale cu $0$.

h2. Date de ieşire

În fişierul de ieşire $trmax.out$ ...

În fişierul de ieşire $trmax.out$ veti afisa un singur numar si anume aria maxima a unui triunghi ce respecta conditiile din cerinta.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N, M ≤ 2 000$
* $1 ≤ K ≤ min(N * M, 10^5^)$
* Triunghiul nu poate fi rotit
 

h2. Exemplu
table(example). |_. trmax.in |_. trmax.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 7 9 8
1 1
2 3
4 1
6 3
7 1
1 7
3 6
7 6
| 16

|
h3. Explicaţie

...

Matricea si solutia reprezentata prin elementele ingrosate:
 
* $100000100$
* $001{**0**}00000$
* $00{**000**}1000$
* $1{**00000**}000$
* ${**0000000**}00$
* $001000000$
* $100001000$

== include(page="template/taskfooter" task_id="trmax") ==

3886