Fișierul intrare/ieșire dreptunghi1.in, dreptunghi1.out Sursă Cerc informatică Vianu
Autor din folclor Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 5 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip full
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in dreptunghi1.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii