Cod sursa(job #2812921)

Utilizator VladutzPredoiVlad Predoi VladutzPredoi Data 5 decembrie 2021 14:27:58
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;


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


stack <pair <int, int> >st;
int n,m,ans;
char a[205][205];
char b[205][205];
int s1[205][205];
int s2[205][205];
int v[205];
int lft[205];
int rgt[205];
int dp1[205],dp2[205];


void read()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            fin>>a[i][j];
            b[j][i]=a[i][j];
        }
    }
}


void partiale(char a[205][205])
{
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[j][i]=='0')
            {
                s1[j][i]=s1[j-1][i]+1;
            }
            else
            {
                s1[j][i]=0;
            }
        }
        for(int j=n;j>=1;j--)
        {
            if(a[j][i]=='0')
            {
                s2[j][i]=s2[j+1][i]+1;
            }
            else
            {
                s2[j][i]=0;
            }
        }
    }
}

int getMaxVal()
{
    while(!st.empty())
    {
        st.pop();
    }
    st.push(make_pair(-1,0));
    for(int i=1;i<=m;i++)
    {
        while(!st.empty() && v[i]<=st.top().first)
            st.pop();
        lft[i]=i-st.top().second-1;
        st.push(make_pair(v[i],i));
    }
    while(!st.empty())
    {
        st.pop();
    }
    st.push(make_pair(-1,m+1));
    for(int i=m;i>=1;i--)
    {
        while(!st.empty() && v[i]<=st.top().first)
            st.pop();
        rgt[i]=st.top().second-i-1;
        st.push(make_pair(v[i],i));
    }
    int maxim=0;
    for(int i=1;i<=m;i++)
    {
        maxim=max(maxim,(lft[i]+rgt[i]+1)*v[i]);
    }
    return maxim;
}


void solve()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            v[j]=s1[i][j];
        }
        dp1[i]=max(dp1[i-1],getMaxVal());
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=m;j++)
        {
            v[j]=s2[i][j];
        }
        dp2[i]=max(dp2[i+1],getMaxVal());
    }
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,dp1[i]+dp2[i+1]);
    }
    for(int i=1;i<=n;i++)
    {
        dp1[i]=dp2[i]=0;
    }
}


int main()
{
    read();
    partiale(a);
    solve();
    swap(n,m);
    partiale(b);
    solve();
    fout<<ans;
    return 0;
}