Cod sursa(job #3181690)

Utilizator divadddDavid Curca divaddd Data 7 decembrie 2023 17:54:29
Problema BMatrix Scor 56
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 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 x, int y){
    int ans = 0;
    memset(h, 0, sizeof(h));
    int len = r-l+1;
    for(int i = l; i <= r; i++){
        vf = 0;
        h[x-1] = -1;
        stv[vf] = x-1;
        for(int j = x; j <= y; 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[y+1] = -1;
        stv[vf] = y+1;
        for(int j = y; j >= x; j--){
            while(vf > 0 && h[j] <= h[stv[vf]]){
                vf--;
            }
            dr[j] = j;
            if(h[j]){
                ans = max(ans, (dr[j]-st[j]+1)*h[j]);
            }
            stv[++vf] = j;
        }
    }
    memset(h, 0, sizeof(h));
    for(int i = x; i <= y; 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] = j;
            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, 1, m) + solve(i+1, n, 1, m));
    }
    for(int i = 1; i <= m; i++){
        ans = max(ans, solve(1, n, 1, i) + solve(1, n, i+1, m));
    }
    fout << ans;
    return 0;
}