# PBinfo #1973 – Hambar2 – Rezolvare C++

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

## Enunț

Enunț
Prințesa Gîrcella este foarte frumoasă. Fiindcă a venit momentul să se mărite, foarte mulți feciori au venit să îi ceară mâna. Printre aceștia se află și Cavalerul de Aur, marele algoritmician. Gîrcella îl dorește pe cel mai inteligent, așa că le va pune o provocare. Grădina sa este o matrice pătratică binară (cu valori 0 sau 1), valorile 0 reprezintă teren liber iar valorile 1 reprezintă pomi. Cel ce va găsi suprafața dreptunghică de arie maximă ce conține doar valori 0, pe care va construi un hambar, va câștiga mâna frumoasei Gîrcella.

Cerința
Ajutați-l pe Cavalerul de Aur să câștige această întrecere.

Date de intrare
Fișierul de intrare hambar2.in conține pe prima linie numerele N și M, reprezentând dimensinunea matricei respectiv numărul de pomi, iar pe următoarele M linii se vor găsi două numere x și y, separate printr-un spațiu, reprezentând indicele liniei, respectiv al coloanei pe care se află un pom.

Date de ieșire
Fișierul de ieșire hambar2.out va conține pe prima linie numărul S, reprezentând aria maximă a unei suprafețe dreptunghiulare.

Restricții și precizări

1 ≤ N, M ≤ 1000
Nu se vor afla 2 sau mai mulți pomi în același loc.

Exemplu:
hambar2.in

5 5
1 3
2 1
2 5
5 1
5 5
hambar2.out

12

## Cod sursă C++

```cpp
/*
    Popa Bogdan Ioan, Colegiul National Aurel Vlaicu
    clasa a 10-a
    Sume partiale, O(N^2)
*/
#include <bits/stdc++.h>
#define nmax 1002
using namespace std;
ifstream fin("hambar2.in");
ofstream fout("hambar2.out");
int n, M;
int i, j, k;
int L;
bitset<nmax>a[nmax];
short S[nmax][nmax];
int maxarie;
short ct[nmax];
int idx;
int main()
{
    fin >> n >> M;
    while(M--)
    {
        fin >> i >> j;
        a[i][j] = 1;
    }
    for(j = 1; j <= n; j++)
    {
        for(i = 1, k = 0; i <= n; i++)
        {
            if(a[i][j] == 0)
                S[i][j] = 1 + S[i][j - 1];
            while(k && S[ct[k]][j] > S[i][j])
            {
                idx = ct[k--];
                maxarie = max(maxarie, (i - ct[k] - 1) * S[idx][j]);
            }
            ct[++k] = i;
        }
        while(k)
        {
            idx = ct[k--];
            maxarie = max(maxarie, (n - ct[k]) * S[idx][j]);
        }
    }
    fout << maxarie << "\n";
    return 0;
}
```

## Resurse

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