Fişierul intrare/ieşire:	trmax.in, trmax.out	Sursă	Algoritmiada 2009, Runda Finala
Autor	Cosmin Gheorghe	Adăugată de	Gheorghe Cosmin •gcosmin
Timp execuţie pe test	0.075 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Trmax

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:

1. ....0....
2. ...000...
3. ..00000..
4. .0000000.
5. 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.

Date de intrare

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.

Date de ieşire

Î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.

Restricţii

• 1 ≤ N, M ≤ 2 000
• 1 ≤ K ≤ min(N * M, 10⁵)
• Triunghiul nu poate fi rotit

Exemplu

Explicaţie

Matricea si solutia reprezentata prin elementele ingrosate:

• 100000100
• 001000000
• 000001000
• 100000000
• 000000000
• 001000000
• 100001000

Cum se trimit solutii?