Cod sursa(job #1542159)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 5 decembrie 2015 02:05:25
Problema BMatrix Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <cstdio>
#include <stack>
#define NMAX 213
using namespace std;
stack<int> s;
int n,m;
int a[NMAX][NMAX],b[NMAX][NMAX],h1[NMAX][NMAX],h2[NMAX][NMAX];
int in[NMAX];
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
            {
                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();
                }
                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
            {
                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();
                }
                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();
        }
    }
    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');
            b[j][i]=a[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++)
    {
        for(int j=1;j<=n;j++) if(b[i][j]==1) 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);
}