# PBinfo #2665 – Dreptunghi1 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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

## Cod sursă C++

```cpp
/* *********************
Solutie oficiala (100p)
Autor: Vintila Valentin Ioan
********************* */
#include <bits/stdc++.h>
#define N 20005
using namespace std;
int S[N], D[N];
int main()
{
    ifstream fin("dreptunghi1.in");
    ofstream fout("dreptunghi1.out");
    int n, m, i, pc = 0, j, k, h[N], stiva[N], vf, maxarea = 0;
    fin >> m >> n >> pc;
    pair<short, short> v[N];
    for(i = 0; i < pc; ++i)
        fin >> v[i].first >> v[i].second;
    sort(v, v+pc);
    k = 0;
    for(i = 1; i <= m; ++i)
    {
        for(j = 1; j <= n; ++j)
        {
            if(v[k].first == i && v[k].second == j) {
                h[j] = 0;
                while(k < pc && v[k].first == i && v[k].second == j)
                    ++k;
                h[j] = 0;
            } else {
                ++h[j];
            }
        }
        vf = 0; stiva[vf] = n + 1;
        for(j = n; j >= 1; --j) {
            while(vf > 0 && h[j] <= h[stiva[vf]]) --vf;
            D[j] = stiva[vf];
            stiva[++vf] = j;
        }
        vf = 0; stiva[vf] = 0;
        for(j = 1; j <= n; ++j) {
            while(vf > 0 && h[j] <= h[stiva[vf]]) --vf;
            S[j] = stiva[vf];
            stiva[++vf] = j;
        }
        for(j = 1; j <= n; ++j)
            maxarea = max(maxarea, h[j] * (D[j] - 1 - S[j]));
    }
    fout << maxarea;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2665)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2665/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2665/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)