Cod sursa(job #1558784)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 29 decembrie 2015 16:23:53
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.73 kb
#include <cstdio>
#include <stack>
#define NMAX 223
using namespace std;
stack<int> s;
int n,m;
int h1[NMAX][NMAX],h2[NMAX][NMAX];
int in[NMAX];
bool apar[NMAX],a[NMAX][NMAX],b[NMAX][NMAX];
int doit(const int &p1,const int &p2)
{
    int maxim=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=p1;j<=p2;j++)
        {
            if(s.empty())
            {
                apar[h1[i][j]]=1;
                s.push(h1[i][j]);
            }
            else
            {
                while(1)
                {
                    if(s.empty()) break;
                    int nod=s.top();
                    if(nod>h1[i][j])
                    {
                        if(maxim<(j-in[nod])*nod) maxim=(j-in[nod])*nod;
                        if(in[h1[i][j]]==0||in[nod]<in[h1[i][j]]) in[h1[i][j]]=in[nod];
                        in[nod]=0;
                        apar[nod]=0;
                        s.pop();
                    }
                    else break;
                }
                if(apar[h1[i][j]]==0)
                {
                    apar[h1[i][j]]=1;
                    s.push(h1[i][j]);
                }
            }
            if(in[h1[i][j]]==0||j<in[h1[i][j]]) in[h1[i][j]]=j;
        }
        while(!s.empty())
        {
            int nod=s.top();
            if(maxim<(p2-in[nod]+1)*nod) maxim=(p2-in[nod]+1)*nod;
            in[nod]=0;
            apar[nod]=0;
            while(!s.empty()&&s.top()==nod) s.pop();
        }
    }
    return maxim;
}
int doit2(const int &p1,const int &p2)
{
    int maxim=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=p1;j<=p2;j++)
        {
            if(s.empty())
            {
                apar[h2[i][j]]=1;
                s.push(h2[i][j]);
            }
            else
            {
                while(1)
                {
                    if(s.empty()) break;
                    int nod=s.top();
                    if(nod>h2[i][j])
                    {
                        if(maxim<(j-in[nod])*nod) maxim=(j-in[nod])*nod;
                        if(in[h2[i][j]]==0||in[nod]<in[h2[i][j]]) in[h2[i][j]]=in[nod];
                        in[nod]=0;
                        apar[nod]=0;
                        s.pop();
                    }
                    else break;
                }
                if(apar[h2[i][j]]==0)
                {
                    apar[h2[i][j]]=1;
                    s.push(h2[i][j]);
                }
            }
            if(in[h2[i][j]]==0||j<in[h2[i][j]]) in[h2[i][j]]=j;
        }
        while(!s.empty())
        {
            int nod=s.top();
            if(maxim<(p2-in[nod]+1)*nod) maxim=(p2-in[nod]+1)*nod;
            in[nod]=0;
            apar[nod]=0;
            while(!s.empty()&&s.top()==nod) s.pop();
        }
    }
    return maxim;
}
int main()
{
    freopen ("bmatrix.in","r",stdin);
    freopen ("bmatrix.out","w",stdout);
    scanf("%d%d",&n,&m);
    char ch;
    for(int i=1;i<=n;i++)
    {
        scanf("%c",&ch);
        for(int j=1;j<=m;j++)
        {
            scanf("%c",&ch);
            a[i][j]=(ch-'0');
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++) b[i][j]=a[n-j+1][i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) if(a[i][j]==0) h1[i][j]=h1[i-1][j]+1;
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++) if(b[i][j]==0) h2[i][j]=h2[i-1][j]+1;
    }
    int maxim=0;
    for(int i=1;i<m;i++)
    {
        int sum=doit(1,i)+doit(i+1,m);
        if(maxim<sum) maxim=sum;
    }
    for(int i=1;i<n;i++)
    {
        int sum=doit2(1,i)+doit2(i+1,n);
        if(maxim<sum) maxim=sum;
    }
    printf("%d\n",maxim);
}