Cod sursa(job #1471802)

Utilizator andrettiAndretti Naiden andretti Data 15 august 2015 11:40:18
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.25 kb
#include<stdio.h>
#include<algorithm>
#include<stack>
#define mp make_pair
#define maxn 205
using namespace std;

int n,m,sol;
char a[maxn][maxn];
int up[maxn][maxn],dw[maxn][maxn],dp_up[maxn],dp_dw[maxn];
int left[maxn][maxn],right[maxn][maxn],dp_left[maxn],dp_right[maxn];
int L[2][maxn],R[2][maxn];
stack< pair<int,int> > s[2];

void read()
{
    scanf("%d %d\n",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s\n",a[i]+1);
}

void DP_vertical()
{
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++) if(a[i][j]=='0')
      up[i][j]=up[i-1][j]+1;

    for(int i=n;i;i--)
     for(int j=1;j<=m;j++) if(a[i][j]=='0')
      dw[i][j]=dw[i+1][j]+1;

    for(int i=1;i<=n;i++)
    {
        dp_up[i]=dp_dw[i]=0;

        //from left to right
        for(int j=1;j<=m;j++)
        {
           while(!s[0].empty() && up[i][j]<s[0].top().first)
            R[0][s[0].top().second]=j,s[0].pop();

           s[0].push(mp(up[i][j],j));

           while(!s[1].empty() && dw[i][j]<s[1].top().first)
            R[1][s[1].top().second]=j,s[1].pop();

           s[1].push(mp(dw[i][j],j));
        }

        for(;!s[0].empty();s[0].pop()) R[0][s[0].top().second]=m+1;
        for(;!s[1].empty();s[1].pop()) R[1][s[1].top().second]=m+1;

        //from right to left
        for(int j=m;j;j--)
        {
            while(!s[0].empty() && up[i][j]<s[0].top().first)
            L[0][s[0].top().second]=j,s[0].pop();

           s[0].push(mp(up[i][j],j));

           while(!s[1].empty() && dw[i][j]<s[1].top().first)
            L[1][s[1].top().second]=j,s[1].pop();

           s[1].push(mp(dw[i][j],j));
        }

        for(;!s[0].empty();s[0].pop()) L[0][s[0].top().second]=0;
        for(;!s[1].empty();s[1].pop()) L[1][s[1].top().second]=0;

        //result on a line
        for(int j=1;j<=m;j++)
        {
            dp_up[i]=max(dp_up[i],up[i][j]*(R[0][j]-L[0][j]-1));
            dp_dw[i]=max(dp_dw[i],dw[i][j]*(R[1][j]-L[1][j]-1));
        }
    }

    int UP,DW;
    for(int i=1;i<n;i++)
    {
        UP=DW=0;
        for(int j=1;j<=i;j++) UP=max(UP,dp_up[j]);
        for(int j=i+1;j<=n;j++) DW=max(DW,dp_dw[j]);

        sol=max(sol,UP+DW);
    }
}

void DP_horizontal()
{
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++) if(a[i][j]=='0')
       left[i][j]=left[i][j-1]+1;

    for(int i=1;i<=n;i++)
     for(int j=m;j;j--) if(a[i][j]=='0')
      right[i][j]=right[i][j+1]+1;

    for(int i=1;i<=m;i++)
    {
        dp_left[i]=dp_right[i]=0;

        //from top to bottom
        for(int j=1;j<=n;j++)
        {
           while(!s[0].empty() && left[j][i]<s[0].top().first)
            R[0][s[0].top().second]=j,s[0].pop();

           s[0].push(mp(left[j][i],j));

           while(!s[1].empty() && right[j][i]<s[1].top().first)
            R[1][s[1].top().second]=j,s[1].pop();

           s[1].push(mp(right[j][i],j));
        }

        for(;!s[0].empty();s[0].pop()) R[0][s[0].top().second]=n+1;
        for(;!s[1].empty();s[1].pop()) R[1][s[1].top().second]=n+1;

        //down - up
        for(int j=n;j;j--)
        {
            while(!s[0].empty() && left[j][i]<s[0].top().first)
            L[0][s[0].top().second]=j,s[0].pop();

           s[0].push(mp(left[j][i],j));

           while(!s[1].empty() && right[j][i]<s[1].top().first)
            L[1][s[1].top().second]=j,s[1].pop();

           s[1].push(mp(right[j][i],j));
        }

        for(;!s[0].empty();s[0].pop()) L[0][s[0].top().second]=0;
        for(;!s[1].empty();s[1].pop()) L[1][s[1].top().second]=0;

        //result on a column
        for(int j=1;j<=n;j++)
        {
            dp_left[i]=max(dp_left[i],left[j][i]*(R[0][j]-L[0][j]-1));
            dp_right[i]=max(dp_right[i],right[j][i]*(R[1][j]-L[1][j]-1));
        }
    }

    int LEFT,RIGHT;
    for(int i=1;i<m;i++)
    {
        LEFT=RIGHT=0;
        for(int j=1;j<=i;j++) LEFT=max(LEFT,dp_left[j]);
        for(int j=i+1;j<=m;j++) RIGHT=max(RIGHT,dp_right[j]);

        sol=max(sol,LEFT+RIGHT);
    }
}

int main()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);

    read();
    DP_vertical();
    DP_horizontal();
    printf("%d",sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}