Cod sursa(job #2837264)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 22 ianuarie 2022 00:15:38
Problema BMatrix Scor 56
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
const int NMAX=205;

int N, M, s1[NMAX][NMAX], s2[NMAX][NMAX], d1[NMAX], d2[NMAX];
char mat[NMAX][NMAX];
stack<int> st1, st2;
int left_smaller[NMAX], right_smaller[NMAX], h[NMAX];

int largetHistogramArea(int L)
{
    while(!st1.empty()) st1.pop();
    while(!st2.empty()) st2.pop();
    ///find the first smallest from left
    st1.push(0);
    h[0]=-1;
    for(int i=1;i<=L;i++){
        while(h[i]<=h[st1.top()])
            st1.pop();
        left_smaller[i]=st1.top();
        st1.push(i);
    }
    ///find the first smallest from right
    st2.push(L+1);
    h[L+1]=-1;
    for(int i=L;i>=1;i--){
        while(h[i]<=h[st2.top()])
            st2.pop();
        right_smaller[i]=st2.top();
        st2.push(i);
    }

    int mx=0;
    for(int i=1;i<=L;i++)
        mx=max(mx,(right_smaller[i]-left_smaller[i]-1)*h[i]);
    return mx;

}

int solve()
{
    for(int i=0;i<=N+1;i++){
        for(int j=0;j<=M+1;j++){
            s1[i][j]=0;
            s2[i][j]=0;
            d1[i]=d1[j]=0;
            d2[i]=d2[j]=0;
        }
    }
    ///from the line i to the top
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            if(mat[i][j]=='0')
                s1[i][j]=s1[i-1][j]+1;
            else
                s1[i][j]=0;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++)
            h[j]=s1[i][j];
        d1[i]=max(d1[i-1],largetHistogramArea(M));
    }


    ///from the line i to the bottom
    for(int i=N;i>=1;i--)
        for(int j=1;j<=M;j++)
            if(mat[i][j]=='0')
                s2[i][j]=s2[i+1][j]+1;
            else
                s2[i][j]=0;
    for(int i=N;i>=1;i--){
        for(int j=1;j<=M;j++)
            h[j]=s2[i][j];
        d2[i]=max(d2[i+1],largetHistogramArea(M));
    }

    int sol=0;
    for(int i=1;i<N;i++)
        sol=max(sol,d1[i]+d2[i+1]);
    return sol;
}

int main()
{
    fin>>N>>M;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            fin>>mat[i][j];

    int sol=0;
    sol=max(sol,solve());

    fout<<sol<<'\n';

    fin.close();
    fout.close();
    return 0;
}