Cod sursa(job #2715750)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 4 martie 2021 10:14:23
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <fstream>
#include <string>
#include <stack>

using namespace std;

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

const int NMAX = 200;

int N, M;

string s[NMAX + 2];
int h[NMAX + 2];

int maxUp[NMAX + 2], maxDown[NMAX + 2], maxLeft[NMAX + 2], maxRight[NMAX + 2];

int Solve(int l) {
    int maxArea = 0;

    stack <int> st;
    st.push(0);

    for(int i = 1; i <= l + 1; i++) {
        while((int)st.size() > 1 && h[i] <= h[st.top()]) {
            int H = h[st.top()];
            st.pop();

            maxArea = max(maxArea, H * (i - st.top() - 1));
        }

        st.push(i);
    }

    return maxArea;
}

void ClearH(int l) {
    for(int i = 1; i <= l; i++) {
        h[i] = 0;
    }
}

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

    for(int i = 1; i <= N; i++) {
        cin >> s[i];
    }

    for(int i = 1; i <= N; i++) {
        for(int j = 0; j < M; j++) {
            if(s[i][j] == '1') {
                h[j + 1] = 0;
            } else {
                h[j + 1]++;
            }
        }

        if(i == 3)
            i++, i--;

        maxUp[i] = max(maxUp[i - 1], Solve(M));
    }
    ClearH(M);

    for(int i = N; i >= 1; i--) {
        for(int j = 0; j < M; j++) {
            if(s[i][j] == '1') {
                h[j + 1] = 0;
            } else {
                h[j + 1]++;
            }
        }

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

    for(int j = 1; j <= M; j++) {
        for(int i = 1; i <= N; i++) {
            if(s[i][j - 1] == '1') {
                h[i] = 0;
            } else {
                h[i]++;
            }
        }

        maxLeft[j] = max(maxLeft[j - 1], Solve(N));
    }
    ClearH(N);

    for(int j = M; j >= 1; j--) {
        for(int i = 1; i <= N; i++) {
            if(s[i][j - 1] == '1') {
                h[i] = 0;
            } else {
                h[i]++;
            }
        }

        maxRight[j] = max(maxRight[j + 1], Solve(N));
    }

    int maxArea = 0;

    for(int i = 1; i <= N; i++) {
        maxArea = max(maxArea, maxUp[i] + maxDown[i + 1]);
    }

    for(int j = 1; j <= M; j++) {
        maxArea = max(maxArea, maxLeft[j] + maxRight[j + 1]);
    }

    cout << maxArea << '\n';
    return 0;
}