Fişierul intrare/ieşire:trmax.in, trmax.outSursăAlgoritmiada 2009, Runda Finala
AutorCosmin GheorgheAdăugată degcosminGheorghe Cosmin gcosmin
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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 li, ci reprezentand faptul ca pe linia li si coloana ci 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, 105)
  • Triunghiul nu poate fi rotit

Exemplu

trmax.intrmax.out
7 9 8
1 1
2 3
4 1
6 3
7 1
1 7
3 6
7 6
16

Explicaţie

Matricea si solutia reprezentata prin elementele ingrosate:

  • 100000100
  • 001000000
  • 000001000
  • 100000000
  • 000000000
  • 001000000
  • 100001000
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content