Rezolvare PBinfo #2665

Dată fiind o matrice dreptunghiulară cu elemente 0 şi 1, care este aria maximă a unui dreptunghi format numai din elemente egale cu 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 cate 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 sunt considerate 1. 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 numai cu 1.

Restricții și precizări

• 1 ≤ m, n, z ≤ 10.000;
• Perechile lin şi col sunt coordonate corecte în matrice, nu neapărat unice.

Punctaje parțiale

• Pentru 20% din teste: 1 ≤ m, n ≤ 30;
• Pentru 40% din teste: 1 ≤ m, n ≤ 100.

Exemplul 1:

dreptunghi1.in

6 6 3
4 1
4 5
3 3

dreptunghi1.out

12

Explicație

Matricea este:
111111
111111
110111
011101
111111
111111
Cel mai mare dreptunghi are arie 12.

Exemplul 2:

dreptunghi1.in

5 8 4
5 2
1 5
2 5
5 7

dreptunghi1.out

16

Explicație

Matricea este:
11110111
11110111
11111111
11111111
10111101
Sunt trei dreptunghiuri de arie maximă, unul 2×8 şi două 4×4.

Notă

Această problemă este foarte înrudită cu problema fadema