trmax

Trmax

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

Poveste şi cerinţă...

Laura are o matrice de dimensiuni $N$ x $M$ 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 fiecare coloane este cu $2$ mai mare decat lungimea coloanei anterioare (mai putin prima coloana care are lungime $1$). De exemplu un triunghi de intaltime $5$ arata astfel:
 
# $....{**0**}....$
# $...{**000**}...$
# $..{**00000**}..$
# $.{**0000000**}.$
# ${**000000000**}$
 
Laura 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 triungi 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, 15 000)$
 

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 7 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:
 
* $1000001$
* $001{**0**}000$
* $00{**000**}10$
* $1{**00000**}0$
* ${**0000000**}$
* $0010000$
* $1000010$

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