Cod sursa(job #852840)

Utilizator dariusdariusMarian Darius dariusdarius Data 11 ianuarie 2013 20:16:40
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m,final_ans;char ss[205][205];
int a[205][205],aux[205][205];
int sus[205][205],jos[205][205];
int st[205],dr[205],stack[205];
int max_up[205],max_down[205];
void rotate()
{
    memset(aux,0,sizeof(aux));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            aux[j][n+1-i]=a[i][j];
    swap(n,m);
    memcpy(a,aux,sizeof(aux));
}
void calc_ans()
{
    memset(max_up,0,sizeof(max_up));
    memset(max_down,0,sizeof(max_down));
    
    memset(sus,0,sizeof(sus));
    int i,j,top;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            sus[i][j]=(a[i][j]==0)?(sus[i-1][j]+1):0;
    for(i=1;i<=n;i++)
    {
        memset(st,0,sizeof(st));
        memset(dr,0,sizeof(dr));
        memset(stack,0,sizeof(stack));top=0;
        for(j=1;j<=m;j++)
        {
            while(top>0 && sus[i][stack[top]]>=sus[i][j]){stack[top]=0;top--;}
            st[j]=stack[top]+1;
            stack[++top]=j;
        }
        memset(stack,0,sizeof(stack));top=0;stack[0]=m+1;
        for(j=m;j>=1;j--)
        {
            while(top>0 && sus[i][stack[top]]>=sus[i][j]){stack[top]=0;top--;}
            dr[j]=stack[top]-1;
            stack[++top]=j;
        }
        for(j=1;j<=m;j++)
            max_up[i]=max(max_up[i],(dr[j]-st[j]+1)*sus[i][j]);
        max_up[i]=max(max_up[i],max_up[i-1]);
    }
    memset(jos,0,sizeof(jos));
    for(i=n;i>=1;i--)
        for(j=m;j>=1;j--)
            jos[i][j]=(a[i][j]==0)?(jos[i+1][j]+1):0;
    for(i=n;i>=1;i--)
    {
        memset(st,0,sizeof(st));
        memset(dr,0,sizeof(dr));
        memset(stack,0,sizeof(stack));top=0;
        for(j=1;j<=m;j++)
        {
            while(top>0 && jos[i][stack[top]]>=jos[i][j]){stack[top]=0;top--;}
            st[j]=stack[top]+1;
            stack[++top]=j;
        }
        memset(stack,0,sizeof(stack));top=0;stack[0]=m+1;
        for(j=m;j>=1;j--)
        {
            while(top>0 && jos[i][stack[top]]>=jos[i][j]){stack[top]=0;top--;}
            dr[j]=stack[top]-1;
            stack[++top]=j;
        }
        for(j=1;j<=m;j++)
            max_down[i]=max(max_down[i],(dr[j]-st[j]+1)*jos[i][j]);
        max_down[i]=max(max_down[i],max_down[i-1]);
    }
    for(i=1;i<n;i++)
        final_ans=max(final_ans,max_up[i]+max_down[i+1]);
}
int main()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    int i;
    scanf("%d %d",&n,&m);getchar();
    for(i=1;i<=n;i++)
        gets(ss[i]+1);
    for(i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=ss[i][j]-'0';
    calc_ans();
    rotate();
    calc_ans();
    printf("%d\n",final_ans);
    return 0;
}