Cod sursa(job #2709620)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 20 februarie 2021 17:29:36
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.39 kb
#include <bits/stdc++.h>

using namespace std;

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

const int N = 205;
int n, m, h[N][N], up[N], down[N], dr[N], st[N];
bool a[N][N];
int maxArea;
stack <int> s;

void Read()
{
    fin >> n >> m;

    char s[N];
    for (int i = 1; i <= n; i++)
    {
        fin >> s;
        for (int j = 1; j <= m; j++)
            a[i][j] = s[j - 1] - '0';
    }
}

void Rotate()
{
    int b[N][N];
    for (int j = 1; j <= m; j++)
        for (int i = 1; i <= n; i++)
            b[j][i] = a[i][j];
    swap(n, m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = b[i][j];
}

void Solve()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            h[i][j] = (a[i][j] ? 0 : h[i - 1][j] + 1);

    for (int i = 1; i <= n; i++)
    {
        up[i] = up[i - 1];
        ///calculez dr[]
        for (int j = 1; j <= m; j++)
        {
            if (s.empty())
                s.push(j);
            else
            {
                int top = s.top();
                if (h[i][j] < h[i][top])
                {
                    while (h[i][j] < h[i][top])
                    {
                        dr[top] = j;
                        s.pop();
                        if (s.empty())
                            break;
                        top = s.top();
                    }
                }
                s.push(j);
            }
        }
        while (!s.empty())
        {
            dr[s.top()] = m + 1;
            s.pop();
        }

        ///calculez st[]
        for (int j = m; j >= 1; j--)
        {
            if (s.empty())
                s.push(j);
            else
            {
                int top = s.top();
                if (h[i][j] < h[i][top])
                {
                    while (h[i][j] < h[i][top])
                    {
                        st[top] = j;
                        s.pop();
                        if (s.empty())
                            break;
                        top = s.top();
                    }
                }
                s.push(j);
            }
        }
        while (!s.empty())
        {
            st[s.top()] = 0;
            s.pop();
        }

        ///calculez aria
        for (int j = 1; j <= m; j++)
            up[i] = max(up[i], h[i][j] * (dr[j] - st[j] - 1));
    }

    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= m; j++)
            h[i][j] = (a[i][j] ? 0 : h[i + 1][j] + 1);
    for (int i = n; i >= 1; i--)
    {
        down[i] = down[i + 1];
        ///calculez dr[]
        for (int j = 1; j <= m; j++)
        {
            if (s.empty())
                s.push(j);
            else
            {
                int top = s.top();
                if (h[i][j] < h[i][top])
                {
                    while (h[i][j] < h[i][top])
                    {
                        dr[top] = j;
                        s.pop();
                        if (s.empty())
                            break;
                        top = s.top();
                    }
                }
                s.push(j);
            }
        }
        while (!s.empty())
        {
            dr[s.top()] = m + 1;
            s.pop();
        }

        ///calculez st[]
        for (int j = m; j >= 1; j--)
        {
            if (s.empty())
                s.push(j);
            else
            {
                int top = s.top();
                if (h[i][j] < h[i][top])
                {
                    while (h[i][j] < h[i][top])
                    {
                        st[top] = j;
                        s.pop();
                        if (s.empty())
                            break;
                        top = s.top();
                    }
                }
                s.push(j);
            }
        }
        while (!s.empty())
        {
            st[s.top()] = 0;
            s.pop();
        }

        ///calculez aria
        for (int j = 1; j <= m; j++)
            down[i] = max(down[i], h[i][j] * (dr[j] - st[j] - 1));
    }

    for (int i = 1; i < n; i++)
        maxArea = max(maxArea, up[i] + down[i + 1]);

}

int main()
{
    Read();
    Solve();
    Rotate();
    Solve();
    fout << maxArea;
    return 0;
}