Cod sursa(job #3317848)

Utilizator Maria_MihailescuMihailescu Maria Maria_Mihailescu Data 25 octombrie 2025 17:25:28
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.57 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMAX = 2e2;
int ma[NMAX + 1][NMAX + 1], h[NMAX + 1][NMAX + 1], st[NMAX + 1], sus[NMAX + 1], jos[NMAX + 1];
int stg[NMAX + 1], dr[NMAX + 1];
int m, n, vf;

int skyline(int l){
    int maxa = 0;
    vf = 0;
    st[0] = 0;
    for(int i = 1; i <= n; i++){
        while(vf > 0 && h[l][st[vf]] >= h[l][i]){
            int j = st[vf--];
            int L = i - st[vf] - 1;
            int a = h[l][j] * L;
            maxa = max(maxa, a);
        }
        st[++vf] = i;
    }
    while(vf > 0){
        int j = st[vf--];
        int L = n - st[vf];
        int a = h[l][j] * L;
        maxa = max(maxa, a);
    }
    return maxa;
}

int main(){
    fin >> m >> n;
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            char c;
            fin >> c;
            ma[i][j] = c - '0';
        }
    }
    for(int j = 1; j <= n; j++){
        h[0][j] = 0;
        for(int i = 1; i <= m; i++){
            if(ma[i][j] == 0)
            h[i][j] = h[i - 1][j] + 1;
            else
            h[i][j] = 0;
        }
    }
    sus[0] = 0;
    for(int i = 1; i <= m; i++){
        sus[i] = max(sus[i - 1], skyline(i));
    }
    for(int j = 1; j <= n; j++){
        h[m + 1][j] = 0;
        for(int i = m; i >= 1; i--){
            if(ma[i][j] == 0)
                h[i][j] = h[i + 1][j] + 1;
            else
                h[i][j] = 0;
        }
    }
    jos[m + 1] = 0;
    for(int i = m; i >= 1; i--){
        jos[i] = max(jos[i + 1], skyline(i));
    }
    int ago = 0;
    for(int i = 1; i < m; i++){
        ago = max(ago, sus[i] + jos[i + 1]);
    }

    for(int i = 1; i <= m; i++){
        h[i][0] = 0;
        for(int j = 1; j <= n; j++){
            if(ma[i][j] == 0)
            h[i][j] = h[i][j - 1] + 1;
            else
            h[i][j] = 0;
        }
    }
    stg[0] = 0;
    for(int j = 1; j <= n; j++){
        int maxa = 0;
        vf = 0;
        st[0] = 0;
        for(int i = 1; i <= m; i++){
            while(vf > 0 && h[st[vf]][j] >= h[i][j]){
                int k = st[vf--];
                int he = i - st[vf] - 1;
                int a = h[k][j] * he;
                maxa = max(maxa, a);
            }
            st[++vf] = i;
        }
        while(vf > 0){
            int k = st[vf--];
            int he = m - st[vf];
            int a = h[k][j] * he;
            maxa = max(maxa, a);
        }
        stg[j] = max(stg[j - 1], maxa);
    }
    for(int i = 1; i <= m; i++){
        h[i][n + 1] = 0;
        for(int j = n; j >= 1; j--){
            if(ma[i][j] == 0)
                h[i][j] = h[i][j + 1] + 1;
            else
                h[i][j] = 0;
        }
    }
    dr[n + 1] = 0;
    for(int j = n; j >= 1; j--){
        int maxa = 0;
        vf = 0;
        st[0] = 0;
        for(int i = 1; i <= m; i++){
            while(vf > 0 && h[st[vf]][j] >= h[i][j]){
                int k = st[vf--];
                int he = i - st[vf] - 1;
                int a = h[k][j] * he;
                maxa = max(maxa, a);
            }
            st[++vf] = i;
        }
        while(vf > 0){
            int k = st[vf--];
            int he = m - st[vf];
            int a = h[k][j] * he;
            maxa = max(maxa, a);
        }
        dr[j] = max(dr[j + 1], maxa);
    }
    int agv = 0;
    for(int j = 1; j < n; j++){
        agv = max(agv, stg[j] + dr[j + 1]);
    }
    fout << max(ago, agv);
    return 0;
}