# PBinfo #1267 – plaja – Rezolvare C++

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

## Enunț

Cerința
O plajă poate fi văzută ca o matrice cu n linii și m coloane. Elementele matricei sunt codificate cu 0, însemnând o poziție liberă, și 1, însemnând o poziție ocupată. Să se afle aria celui mai mare dreptunghi liber din matricea dată. 

Date de intrare
Fișierul de intrare plaja.in conține pe prima linie numerele n și m, iar pe următoarele n linii câte m caractere reprezentând plaja. 

Date de ieșire
Fișierul de ieșire plaja.out va conține pe prima linie numărul S, reprezentând aria maximă a unui dreptunghi liber.

Restricții și precizări

1 ≤ n, m ≤ 1000

Exemplu:
plaja.in

5 5
11111
11000
11100
11100
11110
plaja.out

6
Explicație

1 1 1 1 1
1 1 0 0 0
1 1 1 0 0
1 1 1 0 0
1 1 1 1 0


Suprafața dreptunghiulară de arie maximă este cea îngroșată.

## Cod sursă C++

```cpp
#include <fstream>
#define MAX_N 1000
int hist[MAX_N + 1];
int st[MAX_N], s;
inline int MAX(const int &A, const int &B) {
  return A > B ? A : B;
}
inline int solveHist(int n) {
  int maxArea = 0;
  s = 0;
  hist[n] = 0;
  for (int i = 0; i <= n; i++) {
    while ((s > 0) && (hist[st[s - 1]] > hist[i])) {
      s--;
      maxArea = MAX(maxArea, hist[st[s]] * (!s ? i : i - 1 - st[s - 1]));
    }
    st[s++] = i;
  }
  return maxArea;
}
int main(void) {
  int n, m;
  int maxArea;
  std::fstream f("plaja.in", std::ios::in);
  f.tie(0);
  std::ios_base::sync_with_stdio(0);
  f >> n >> m;
  maxArea = 0;
  for (int i = 0; i < n; i++) {
    f.get();
    for (int j = 0; j < m; j++) {
      if (f.get() == '0') {
        hist[j]++;
      } else {
        hist[j] = 0;
      }
    }
    maxArea = MAX(maxArea, solveHist(m));
  }
  f.close();
  f.open("plaja.out", std::ios::out);
  f << maxArea << '\n';
  f.close();
  return 0;
}
```

## Resurse

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