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

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:

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

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, 15 000)

Exemplu

Explicaţie

Matricea si solutia reprezentata prin elementele ingrosate:

• 1000001
• 0010000
• 0000010
• 1000000
• 0000000
• 0010000
• 1000010

Cum se trimit solutii?