Cod sursa(job #2923756)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 18 septembrie 2022 18:23:11
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
//
// Created by mihai145 on 18.09.2022.
//

#include <fstream>
#include <vector>
#include <string>
#include <stack>

using namespace std;

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

int max_area_histogram(const vector<int>& h) {
    int max_area = 0;

    stack<int> stk;

    auto update_max_area = [&](int i) {
        int width, height = h[stk.top()];
        stk.pop();

        if(stk.empty()) {
            width = i;
        } else {
            width = i - 1 - stk.top();
        }

        max_area = max(max_area, width * height);
    };

    for(int i = 0; i < (int)h.size(); i++) {
        while(!stk.empty() && h[stk.top()] >= h[i]) {
            update_max_area(i);
        }

        stk.push(i);
    }

    while(!stk.empty()) {
        update_max_area((int)h.size());
    }

    return max_area;
}

int calculate_ans(const vector<string>& mat) {
    int n = (int)mat.size(), m = (int)mat[0].size();
    int ans = 0;

    vector<int> dp_up(n, 0), dp_down(n, 0);

    vector<int> h(m, 0);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(mat[i][j] == '1') {
                h[j] = 0;
            } else {
                h[j]++;
            }
        }

        int mx = max_area_histogram(h);
        dp_up[i] = (i >= 1) ? max(dp_up[i - 1], mx) : mx;
    }

    for(int i = 0; i < m; i++) {
        h[i] = 0;
    }
    for(int i = n - 1; i >= 0; i--) {
        for(int j = 0; j < m; j++) {
            if(mat[i][j] == '1') {
                h[j] = 0;
            } else {
                h[j]++;
            }
        }

        int mx = max_area_histogram(h);
        dp_down[i] = (i < n - 1) ? max(dp_down[i + 1], mx) : mx;
    }

    ans = dp_up[n - 1];
    for(int i = 0; i < n - 1; i++) {
        ans = max(ans, dp_up[i] + dp_down[i + 1]);
    }

    return ans;
}

int main() {
    int n, m, ans = 0;
    cin >> n >> m;

    vector<string> mat(n);
    for(int i = 0; i < n; i++) {
        cin >> mat[i];
    }

    ans = calculate_ans(mat);

    vector<string> mat2(m);
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            mat2[i] += mat[j][i];
        }
    }

    ans = max(ans, calculate_ans(mat2));

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