Cerința

O plajă poate fi văzută ca o matrice cu n linii și m coloane. Elementele matricii 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

Suprafata dreptunghiulara de aria maxima este cea ingrosata.

#include <bits/stdc++.h>


using namespace std;

ifstream cin("plaja.in");
ofstream cout("plaja.out");

int n , m , x , maxx , v1[10001];
char v[10001];

int get(int vec[], int k)
{
    stack<int> s;
    int maxa = 0, toop , a , i = 0;
    while(i < k)
    {
        if(s.empty() || vec[s.top()] <= vec[i])s.push(i++);
        else
        {
            toop = s.top();
            s.pop();
            a = vec[toop] * (s.empty() ? i : i - s.top() - 1);
            maxa = max(maxa , a);
        }
    }
    while(!s.empty())
    {
        toop = s.top();
        s.pop();
        a = vec[toop] * (s.empty() ? i : i - s.top() - 1);
        maxa = max(maxa , a);
    }
    return maxa;
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i <= n; ++i)
    {
        cin.getline(v , 10001);
        for(int j = 0; j < (int)strlen(v); ++j)
        {
            if((v[j] - '0') == 1) v1[j] = 0;
            else if((v[j] - '0') == 0) v1[j] += 1;
        }
        x = get(v1 , m);
        maxx = max(maxx , x);
    }
    cout << maxx;
    return 0;
}