Cod sursa(job #3346667)

Utilizator filipdanieloanFilip-Daniel Oancea filipdanieloan Data 14 martie 2026 20:52:14
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.71 kb
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define top() back()
#define pop() pop_back()
#define push(x) push_back(x)

char a[205][205];
int h[205];
int max_area_orizontal[205], max_area_vertical[205];

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifndef LOCAL
    freopen("bmatrix.in", "r", stdin);
    freopen("bmatrix.out", "w", stdout);
#endif

    int m, n; cin >> m >> n;
    for(int i = 1; i <= m; ++i) {
        for(int j = 1; j <= n; ++j) {
            cin >> a[i][j];
        }
    }

    int last = 0;

    for(int bara = 1; bara <= m; ++bara) {
        for(int j = 1; j <= n; ++j) {
            if(a[bara][j] == '0')
                ++h[j];
            else h[j] = 0;
        }
        vector<pair<int, int>> bounds(n+1, {0, n+1});
        vector<int> st;
        for(int j = 1; j <= n; ++j) {
            while(!st.empty() && h[j] <= h[st.top()])
                st.pop();
            if(!st.empty())
                bounds[j].fi = st.top();
            st.push(j);
        }
        st.clear();
        for(int j = n; j >= 1; --j) {
            while(!st.empty() && h[j] <= h[st.top()])
                st.pop();
            if(!st.empty())
                bounds[j].se = st.top();
            st.push(j);
        }
        int aMax = 0;
        for(int j = 1; j <= n; ++j) {
            int calcul = h[j] * (bounds[j].se - bounds[j].fi - 1);
            aMax = max(aMax, calcul);
        }
        last = max(last, aMax);
        max_area_orizontal[bara] += last;
    }

    memset(h, 0, sizeof(h));
    last = 0;

    for(int bara = m; bara > 1; --bara) {
        for(int j = 1; j <= n; ++j) {
            if(a[bara][j] == '0')
                ++h[j];
            else h[j] = 0;
        }
        vector<pair<int, int>> bounds(n+1, {0, n+1});
        vector<int> st;
        for(int j = 1; j <= n; ++j) {
            while(!st.empty() && h[j] <= h[st.top()])
                st.pop();
            if(!st.empty())
                bounds[j].fi = st.top();
            st.push(j);
        }
        st.clear();
        for(int j = n; j >= 1; --j) {
            while(!st.empty() && h[j] <= h[st.top()])
                st.pop();
            if(!st.empty())
                bounds[j].se = st.top();
            st.push(j);
        }
        int aMax = 0;
        for(int j = 1; j <= n; ++j) {
            int calcul = h[j] * (bounds[j].se - bounds[j].fi - 1);
            aMax = max(aMax, calcul);
        }
        last = max(last, aMax);
        max_area_orizontal[bara-1] += last;
    }

    memset(h, 0, sizeof(h));
    last = 0;

    for(int bara = 1; bara <= n; ++bara) {
        for(int j = 1; j <= m; ++j) {
            if(a[j][bara] == '0')
                ++h[j];
            else h[j] = 0;
        }
        vector<pair<int, int>> bounds(m+1, {0, m+1});
        vector<int> st;
        for(int j = 1; j <= m; ++j) {
            while(!st.empty() && h[j] <= h[st.top()])
                st.pop();
            if(!st.empty())
                bounds[j].fi = st.top();
            st.push(j);
        }
        st.clear();
        for(int j = m; j >= 1; --j) {
            while(!st.empty() && h[j] <= h[st.top()])
                st.pop();
            if(!st.empty())
                bounds[j].se = st.top();
            st.push(j);
        }
        int aMax = 0;
        for(int j = 1; j <= m; ++j) {
            int calcul = h[j] * (bounds[j].se - bounds[j].fi - 1);
            aMax = max(aMax, calcul);
        }
        last = max(last, aMax);
        max_area_vertical[bara] += last;
    }

    memset(h, 0, sizeof(h));
    last = 0;

    for(int bara = n; bara > 1; --bara) {
        for(int j = 1; j <= m; ++j) {
            if(a[j][bara] == '0')
                ++h[j];
            else h[j] = 0;
        }
        vector<pair<int, int>> bounds(m+1, {0, m+1});
        vector<int> st;
        for(int j = 1; j <= m; ++j) {
            while(!st.empty() && h[j] <= h[st.top()])
                st.pop();
            if(!st.empty())
                bounds[j].fi = st.top();
            st.push(j);
        }
        st.clear();
        for(int j = m; j >= 1; --j) {
            while(!st.empty() && h[j] <= h[st.top()])
                st.pop();
            if(!st.empty())
                bounds[j].se = st.top();
            st.push(j);
        }
        int aMax = 0;
        for(int j = 1; j <= m; ++j) {
            int calcul = h[j] * (bounds[j].se - bounds[j].fi - 1);
            aMax = max(aMax, calcul);
        }
        last = max(last, aMax);
        max_area_vertical[bara-1] += last;
    }

    int maxx = 0;
    for(int i = 1; i <= m; ++i) {
        maxx = max(maxx, max_area_orizontal[i]);
    }
    for(int i = 1; i <= n; ++i) {
        maxx = max(maxx, max_area_vertical[i]);
    }

    cout << maxx;

    return 0;
}