Cod sursa(job #1542327)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 5 decembrie 2015 12:05:57
Problema BMatrix Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.71 kb
#include <cstdio>
#include <stack>
#define NMAX 450
using namespace std;
stack<int> s;
int n,m;
int a[NMAX][NMAX],b[NMAX][NMAX],h1[NMAX][NMAX],h2[NMAX][NMAX];
int in[223];
int doit(int p1,int p2)
{
    int maxim=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=p1;j<=p2;j++)
        {
            if(s.empty()) 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;
                        in[nod]=0;
                        while(!s.empty()&&s.top()==nod) s.pop();
                    }
                    else break;
                }
                s.push(h1[i][j]);
            }
            if(in[h1[i][j]]==0) 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;
            while(!s.empty()&&s.top()==nod) s.pop();
        }
    }
    return maxim;
}
int doit2(int p1,int p2)
{
    int maxim=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=p1;j<=p2;j++)
        {
            if(s.empty()) 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;
                        in[nod]=0;
                        while(!s.empty()&&s.top()==nod) s.pop();
                    }
                    else break;
                }
                s.push(h2[i][j]);
            }
            if(in[h2[i][j]]==0) 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;
            while(!s.empty()&&s.top()==nod) s.pop();
        }
    }
    //printf("%d %d %d\n",p1,p2,maxim);
    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]=1-(ch-'0');
        }
    }
    int maxim=0;
    for(int x=1;x<=2;x++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                h2[j][i]=0;
                if(x==1) b[j][i]=a[i][j];
                else if(x==2) b[j][n-i+1]=a[i][j];
            }
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++) if(b[i][j]==1) h2[i][j]=h2[i-1][j]+1;
        }
        for(int i=1;i<n;i++)
        {
            int sum=doit2(1,i)+doit2(i+1,n);
            if(maxim<sum) maxim=sum;
        }
    }
    for(int x=1;x<=2;x++)
    {
        if(x==2)
        {
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    h1[i][j]=0;
                    b[i][m-j+1]=a[i][j];
                }
            }
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++) a[i][j]=b[i][j];
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++) if(a[i][j]==1) h1[i][j]=h1[i-1][j]+1;
        }
    }
    for(int i=1;i<m;i++)
    {
        int sum=doit(1,i)+doit(i+1,m);
        if(maxim<sum) maxim=sum;
    }
    printf("%d\n",maxim);
}