Cod sursa(job #3181682)

Utilizator divadddDavid Curca divaddd Data 7 decembrie 2023 17:45:50
Problema BMatrix Scor 56
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 202;
int n,m,v[NMAX][NMAX],stv[NMAX],st[NMAX],dr[NMAX],h[NMAX],vf;

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

int solve(int l, int r){
    int ans = 0;
    memset(h, 0, sizeof(h));
    int len = r-l+1;
    for(int i = l; i <= r; i++){
        vf = 0;
        h[0] = -1;
        stv[vf] = 0;
        for(int j = 1; j <= m; j++){
            h[j] = (v[i][j] == 0 ? (h[j]+1) : 0);
            while(vf > 0 && h[j] <= h[stv[vf]]){
                vf--;
            }
            st[j] = stv[vf]+1;
            stv[++vf] = j;
        }
        vf = 0;
        h[m+1] = -1;
        stv[vf] = m+1;
        for(int j = m; j >= 1; j--){
            while(vf > 0 && h[j] <= h[stv[vf]]){
                vf--;
            }
            dr[j] = stv[vf]-1;
            if(h[j]){
                ans = max(ans, (dr[j]-st[j]+1)*h[j]);
            }
            stv[++vf] = j;
        }
    }

    memset(h, 0, sizeof(h));
    for(int i = 1; i <= m; i++){
        vf = 0;
        h[l-1] = -1;
        stv[vf] = l-1;
        for(int j = l; j <= r; j++){
            h[j] = (v[j][i] == 0 ? (h[j]+1) : 0);
            while(vf > 0 && h[j] <= h[stv[vf]]){
                vf--;
            }
            st[j] = stv[vf]+1;
            stv[++vf] = j;
        }
        vf = 0;
        h[r+1] = -1;
        stv[vf] = r+1;
        for(int j = r; j >= l; j--){
            while(vf > 0 && h[j] <= h[stv[vf]]){
                vf--;
            }
            dr[j] = stv[vf]-1;
            if(h[j]){
                ans = max(ans, (dr[j]-st[j]+1)*h[j]);
            }
            stv[++vf] = j;
        }
    }

    return ans;
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            char ch;
            fin >> ch;
            v[i][j] = (ch-'0');
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans, solve(1, i) + solve(i+1, n));
    }
    fout << ans;
    return 0;
}