Cod sursa(job #2504845)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 5 decembrie 2019 17:37:16
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <bits/stdc++.h>

using namespace std;

const int nmax=205;

bool v[nmax][nmax],aux[nmax][nmax];
int h[nmax][nmax],val[nmax],st[nmax],dr[nmax],sols[nmax],solj[nmax];
int n,m;
stack<int>sta;

void build_height()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(v[i][j]==0)
                h[i][j]=h[i-1][j]+1;
            else
                h[i][j]=0;
}

void rotate90()
{
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
            aux[i][j]=v[n-j+1][i];
    swap(n,m);
    memcpy(v,aux,sizeof(aux));
}

void rotate180()
{
    rotate90();
    rotate90();
}

void reset_stiva()
{
    while(!sta.empty())
        sta.pop();
}

void build_val(int l)
{
    for(int i=1; i<=m; i++)
        val[i]=h[l][i];
}

void build_st()
{
    reset_stiva();
    sta.push(1);
    st[1]=0;
    for(int i=2; i<=m; i++)
    {
        while(!sta.empty() && val[i] <= val[sta.top()])
            sta.pop();
        if(sta.empty())
            st[i] = 0;
        else
            st[i] = sta.top();
        sta.push(i);
    }
}

void build_dr()
{
    reset_stiva();
    sta.push(m);
    dr[m]=m+1;
    for(int i=m-1; i>=1; i--)
    {
        while(!sta.empty() && val[i] <= val[sta.top()])
            sta.pop();
        if(sta.empty())
            dr[i]=m+1;
        else
            dr[i]=sta.top();
        sta.push(i);
    }
}

int solve(int l)
{
    build_val(l);
    build_st();
    build_dr();
    int ans=0;
    for(int i=1; i<=m; i++)
        ans=max(ans,val[i]*(dr[i]-st[i]-1));
    return ans;
}

int main()
{
    ifstream cin("bmatrix.in");
    ofstream cout("bmatrix.out");
    char c;
    int ans=0;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            cin>>c;
            v[i][j]=c-'0';
        }
    build_height();
    for(int r=1; r<=n; r++)
        sols[r]=max(sols[r-1],solve(r));
    rotate180();
    build_height();
    for(int r=1; r<=n; r++)
        solj[r]=max(solj[r-1],solve(r));
    for(int i=1; i<n; i++)
        ans=max(ans,sols[n-i]+solj[i]);
    rotate90();
    build_height();
    for(int r=1; r<=n; r++)
        sols[r]=max(sols[r-1],solve(r));
    rotate180();
    build_height();
    for(int r=1; r<=n; r++)
        solj[r]=max(solj[r-1],solve(r));
    for(int i=1; i<n; i++)
        ans=max(ans,sols[n-i]+solj[i]);
    cout<<ans;
    return 0;
}