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

#include <bits/stdc++.h>


using namespace std;

ifstream fin("hambar2.in");
ofstream fout("hambar2.out");

const int MaxN = 1001;

short h[MaxN][MaxN];
bool a[MaxN][MaxN];
short m, n;

int maxAreaInHist(short x[], short L)
{
    stack<short> st;

    short j = 0, tp;
    short amax = 0, area;

    while (j < n)
    {
        if (st.empty() || x[st.top()] <=  x[j])
            st.push(j++);
        else
        {
            tp = st.top();
            st.pop();
            area = x[tp] * (st.empty() ? j : j - st.top() - 1);
            amax = max(amax, area);
        }
    }

    while (!st.empty())
    {
        tp = st.top();
        st.pop();
        area = x[tp] * (st.empty() ? j : j - st.top() - 1);
        amax = max(amax, area);
    }

    return amax;
}

int main()
{
     // citire
    fin >> m >> n;
    for (int i = 0; i < n; ++i)
    {
        short x1, y1;
        fin >> x1 >> y1;
        a[x1-1][y1-1]=1;
    }

    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            a[i][j]=!a[i][j];

    int maxArea = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < m; j++)
            if (a[i][j] == 0)
                h[i][j] = 0;
            else
            {
                if ( i == 0 )
                    h[i][j] = 1;
                else
                    h[i][j] = h[i - 1][j] + 1;
            }

    short area;
    for (int i = 0; i < m; i++)
    {
        area = maxAreaInHist(h[i], i);
        if (area > maxArea)
            maxArea = area;
    }
    fout << maxArea;
}