Cod sursa(job #2709608)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 20 februarie 2021 16:25:07
Problema BMatrix Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.28 kb
#include <bits/stdc++.h>

using namespace std;

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

const int N = 201;
int n, m, h[N][N], st[N], dr[N];
bool a[N][N], mat[N][N];
int area, maxArea;
int lin, col;
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';
    }

}

int largestArea()
{
    int candArea = 0;
    for (int i = 1; i <= lin; i++)
        for (int j = 1; j <= col; j++)
            h[i][j] = (mat[i][j] ? 0 : h[i - 1][j] + 1);

    for (int i = 1; i <= lin; i++)
    {
        ///calculez dr[]
        for (int j = 1; j <= col; 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()] = col + 1;
            s.pop();
        }

        ///calculez st[]
        for (int j = col; 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 <= col; j++)
            candArea = max(candArea, h[i][j] * (dr[j] - st[j] - 1));
    }

    return candArea;

}

void Solve()
{
    for (int lim = 1; lim < n; lim++)
    {
        for (int i = 1; i <= lim; i++)
            for (int j = 1; j <= m; j++)
                mat[i][j] = a[i][j];
        lin = lim; col = m;
        area = largestArea();

        for (int i = lim + 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                mat[i - lim][j] = a[i][j];
        lin = n - lim; col = m;
        area += largestArea();

        maxArea = max(area, maxArea);
    }

    for (int lim = 1; lim < m; lim++)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= lim; j++)
                mat[i][j] = a[i][j];
        lin = n; col = lim;
        area = largestArea();

        for (int i = 1; i <= n; i++)
            for (int j = lim + 1; j <= m; j++)
                mat[i][j - lim] = a[i][j];
        lin = n; col = m - lim;
        area += largestArea();

        maxArea = max(area, maxArea);
    }

}

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