Cod sursa(job #2370024)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 6 martie 2019 10:20:59
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <fstream>
#include <cstring>
#include <stack>

using namespace std;

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

const int NMAX = 205;

int N, M, ans;
char s[NMAX][NMAX];

int heights[NMAX];

int bestUp[NMAX]; ///cel mai bun dreptunghi care e peste linia i
int bestDown[NMAX]; ///cel mai bun dreptunghi care e pe si sub linia i
int bestLeft[NMAX]; ///cel mai bun dreptunghi care e inaintea coloanei i
int bestRight[NMAX]; ///cel mai bun dreptunghi care e pe si dupa coloana i

int Solve(int D)
{
    stack <int> st;
    st.push(0);

    int maxAreaRect = 0;

    for(int i = 1; i <= D + 1; i++)
    {
        while(st.size() > 1 && heights[i] <= heights[st.top()])
        {
            int currentHeight = heights[st.top()];
            st.pop();
            maxAreaRect = max(maxAreaRect, currentHeight * (i - st.top() - 1));
        }

        st.push(i);
    }

    return maxAreaRect;
}

int main()
{
    fin >> N >> M;

    for(int i = 1; i <= N; i++)
        fin >> (s[i] + 1);

    ///bestUp
    memset(heights, 0, sizeof(heights));
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= M; j++)
            if(s[i][j] == '0')
                heights[j]++;
            else
                heights[j] = 0;

        bestUp[i + 1] = max(bestUp[i], Solve(M));
    }

    ///bestDown
    memset(heights, 0, sizeof(heights));
    for(int i = N; i >= 1; i--)
    {
        for(int j = 1; j <= M; j++)
            if(s[i][j] == '0')
                heights[j]++;
            else
                heights[j] = 0;

        bestDown[i] = max(bestDown[i + 1], Solve(M));
    }

    ///bestLeft
    memset(heights, 0, sizeof(heights));
    for(int i = 1; i <= M; i++)
    {
        for(int j = 1; j <= N; j++)
            if(s[j][i] == '0')
                heights[j]++;
            else
                heights[j] = 0;

        bestLeft[i + 1] = max(bestLeft[i], Solve(N));
    }

    ///bestRight
    memset(heights, 0, sizeof(heights));
    for(int i = M; i >= 1; i--)
    {
        for(int j = 1; j <= N; j++)
            if(s[j][i] == '0')
                heights[j]++;
            else
                heights[j] = 0;

        bestRight[i] = max(bestRight[i + 1], Solve(N));
    }

    ///Up-Down
    for(int i = 1; i <= N; i++)
        ans = max(ans, bestUp[i] + bestDown[i]);

    ///Left-Right
    for(int i = 1; i <= M; i++)
        ans = max(ans, bestLeft[i] + bestRight[i]);

    fout << ans << '\n';

    return 0;
}