Fişierul intrare/ieşire:dreptunghi1.in, dreptunghi1.outSursăCerc informatică Vianu
AutorDin FolclorAdăugată defrancuCristian Francu francu
Timp execuţie pe test5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Dreptunghi 1 (baraj gimnaziu)

Dată o matrice dreptunghiulară cu elemente 0 şi 1, care este aria maximă a unui dreptunghi format numai din elemente 1?

Date de intrare

Pe prima linie a fişierului dreptunghi1.in se vor găsi trei numere: numărul de linii, m, al matricei, numărul de coloane, n, precum şi numărul z al elementelor 0 din matrice. Pe următoarele z linii vom avea cîte o pereche de numere lin şi col, separate printr-un spaţiu, cu semnificaţia că elementul de la linia lin şi coloana col este 0. Restul elementelor matricei sînt 1. Este posibil ca z să fie 0, caz în care nu vom mai avea nici o linie extra. De asemenea este posibil ca anumite perechi lin şi col să se repete.

Date de ieşire

Fişierul dreptunghi1.out va conţine un singur număr, aria celui mai mare dreptunghi plin cu 1.

Restricţii

  • 1 ≤ m, n ≤ 10000
  • 0 ≤ z ≤ 10000
  • perechile lin şi col sînt coordonate corecte în matrice, nu neapărat unice
  • pentru 20% din teste 1 ≤ m, n ≤ 30
  • pentru 40% din teste 1 ≤ m, n ≤ 100

Exemplu

dreptunghi1.indreptunghi1.outExplicaţie
6 6 3
4 1
4 5
3 3
12
Matricea este:
111111
111111
110111
011101
111111
111111
cel mai mare dreptunghi are arie 12
5 8 4
5 2
1 5
2 5
5 7
16
Matricea este:
11110111
11110111
11111111
11111111
10111101
sînt trei dreptunghiuri de arie maximă, unul 2×8 şi două 4×4
Trebuie sa te autentifici pentru a trimite solutii. Click aici