Cod sursa(job #1914694)

Utilizator andraSaceliAndra Saceli andraSaceli Data 8 martie 2017 18:08:16
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cstring>
using namespace std;
const int NMAX=205;
stack <int> stiva;
int v[NMAX],st[NMAX],dr[NMAX],up[205][205],up2[205],down2[205];
char mat[205][205],mat2[205][205];                                          /////////////////!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
char s[205];
int n,m,rez1,rez2;
void dreptunghi()
{
    int maxim=0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            if(mat[i][j]==1)
                up[i][j]=0;
            else
                up[i][j]=up[i-1][j]+1;
        }
    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=m; i++)
        {
            while(!stiva.empty() && up[k][i]<=up[k][stiva.top()])
                stiva.pop();
            if(stiva.empty())
                st[i]=0;
            else
                st[i]=stiva.top();
            stiva.push(i);

        }
        while(!stiva.empty())
            stiva.pop();
        for(int i=m; i>=1; i--)
        {
            while(!stiva.empty() && up[k][i]<=up[k][stiva.top()])
                stiva.pop();
            if(stiva.empty())
                dr[i]=m+1;
            else
                dr[i]=stiva.top();
            stiva.push(i);
        }
        maxim=0;
        for(int i=1; i<=m; i++)
        {
            if(up[k][i]*(dr[i]-st[i]-1)>maxim)
                maxim=up[k][i]*(dr[i]-st[i]-1);
            st[i]=dr[i]=0;
        }
        while(!stiva.empty())
            stiva.pop();
        down2[k]=max(down2[k-1],maxim);
    }
}
void rezultat()
{
    dreptunghi();
    for(int i=1; i<=n; i++)
        up2[i]=down2[i];
    for(int i=1; i<=n/2; i++)
        for(int j=1; j<=m; j++)
        {
            swap(mat[i][j],mat[n-i+1][j]);
        }
    dreptunghi();
    reverse(down2+1,down2+n+1);
    rez2=0;
    for(int i=1; i<n; i++)
        rez2=max(rez2,down2[i+1]+up2[i]);
}
int main()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    scanf("%d%d ",&n,&m);
    int nrch,rezmax;
    for(int i=1; i<=n; i++)
    {
        gets(s+1);
        for(int j=1; j<=m; j++)
            mat[i][j]=s[j]-'0';
    }
    rezultat();
    rez1=rez2;
    for(int i=1; i<=n; i++)
     for(int j=1; j<=m; j++)
        mat2[j][n-i+1]=mat[i][j];
    swap(n,m);
    for(int i=1; i<=n; i++)
      for(int j=1; j<=m; j++)
        mat[i][j]=mat2[i][j];
    rezultat();
    rez1=max(rez1,rez2);
    printf("%d",rez1);
    return 0;
}