Cod sursa(job #3354530)

Utilizator serbanbBrindescu Serban serbanb Data 18 mai 2026 19:41:12
Problema BMatrix Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <fstream>
#include <stack>

using namespace std;

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

int n,m;
int A[205][205];
int up[205][205], l[205][205], r[205][205];

void read()
{
    fin >> n >> m;
    for(int i = 0; i < n; ++i){
        string s;
        fin >> s;
        for(int j = 0; j < m; ++j){
            A[i][j] = s[j] - '0';
        }
    }
}

void buildUp(int r1, int r2, int c1, int c2)
{
    for(int j = c1; j <= c2; ++j){
        for(int i = r1; i <= r2; ++i){
            if(A[i][j] == 0){
                if(i == r1){
                    up[i][j] = 1;
                }
                else{
                    up[i][j] = up[i - 1][j] + 1;
                }
            }
            else{
                up[i][j] = 0;
            }
        }
    }
}

void buildLeftRight(int r1, int r2, int c1, int c2)
{
    for(int i = r1; i <= r2; ++i){
        stack<int> st;
        st.push(c1);
        l[i][c1] = c1 - 1;
        for(int j = c1 + 1; j <= c2; ++ j){
            while(!st.empty() && up[i][j] <= up[i][st.top()]){
                st.pop();
            }
            if(st.empty()){
                l[i][j] = c1 - 1;
            }
            else{
                l[i][j] = st.top();
            }
            st.push(j);
        }
    }
    for(int i = r1; i <= r2; ++i){
        stack<int> st;
        st.push(c2);
        r[i][c2] = c2 + 1;
        for(int j = c2 - 1; j >= c1; --j){
            while(!st.empty() && up[i][j] <= up[i][st.top()]){
                st.pop();
            }
            if(st.empty()){
                r[i][j] = c2 + 1;
            }
            else{
                r[i][j] = st.top();
            }
            st.push(j);
        }
    }
}

int maxArea(int r1, int r2, int c1, int c2)
{
    buildUp(r1, r2, c1, c2);
    buildLeftRight(r1, r2, c1, c2);
    int maxA = 0;
    for(int i = r1; i <= r2; ++i){
        for(int j = c1; j <= c2; ++j){
            int a = (r[i][j] - l[i][j] - 1) * up[i][j];
            if(a > maxA){
                maxA = a;
            }
        }
    }
    return maxA;
}

void solve()
{
    int maxA = 0;
    for(int i = 0; i < n - 1; ++i){
        int a = maxArea(0, i, 0, m - 1) + maxArea(i + 1, n - 1, 0, m - 1);
        if(a > maxA){
            maxA = a;
        }
    }
    for(int j = 0; j < m - 1; ++j){
        int a = maxArea(0, n - 1, 0, j) + maxArea(0, n - 1, j + 1, m - 1);
        if(a > maxA){
            maxA = a;
        }
    }
    fout << maxA;
}

int main()
{
    read();
    solve();
    return 0;
}