Cod sursa(job #849458)

Utilizator assa98Andrei Stanciu assa98 Data 6 ianuarie 2013 23:15:54
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

char x[300][300];
int d[300][300];
int n,m;

int st[300];

void rotate()
{
    char b[300][300];
    memset(b,0,sizeof(b));

    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            b[j][n-i+1]=x[i][j];
    swap(n, m);

    memset(x, 0, sizeof(x));
    memcpy(x,b,sizeof(b));
}

void build_st(int l,int v[])
{
    memset(st,0,sizeof(st));
    memset(v,0,sizeof(int)*300);

    for(int j=1; j<=m; j++)
    {
        v[j]=j;
        st[++st[0]]=j;
        while(st[0]>1 && d[l][st[st[0]-1]]>=d[l][st[st[0]]])
        {
            v[j]=min(v[j],v[st[st[0]-1]]);
            st[st[0]-1]=st[st[0]];
            st[0]--;
        }
    }
}

void rl(int l)
{
    for(int j=1; j<=m/2; j++)
        swap(d[l][j],d[l][m-j+1]);
}

void drept(int sol[300])
{
    memset(sol,0,sizeof(sol));
    memset(d,0,sizeof(d));
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(x[i][j]=='0')
                d[i][j]=d[i-1][j]+1;

    int in_dr[300],in_st[300];


    for(int i=1; i<=n; i++)
    {
        memset(in_dr,0,sizeof(in_dr));
        memset(in_st,0,sizeof(in_st));
        build_st(i,in_st);
        rl(i);
        build_st(i,in_dr);

        for(int j=1; j<=m; j++)
            in_dr[j]=m-in_dr[j]+1;
        for(int j=1; j<=m/2; j++)
            swap(in_dr[j],in_dr[m-j+1]);
        rl(i);

        sol[i]=sol[i-1];
        for(int j=1; j<=m; j++)
        {
            if(x[i][j]=='0')
            {
                sol[i]=max(sol[i],(in_dr[j]-in_st[j]+1)*d[i][j]);
            }
        }
    }

}

int sol;

void get_sol(int c[300],int d[300])
{
    for(int i=1;i<n;i++)
        sol=max(sol,c[i]+d[i+1]);
}

int main()
{
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++)
    {
        scanf("%s", x[i] + 1);
        x[i][0]=' ';
    }

    int r[300],t[300];

    drept(r);
    rotate();
    rotate();
    drept(t);
    for(int i=1;i<=n/2;i++)
        swap(t[i],t[n-i+1]);
    get_sol(r,t);

    rotate();
    drept(r);
    rotate();
    rotate();
    drept(t);
    for(int i=1;i<=n/2;i++)
        swap(t[i],t[n-i+1]);
    get_sol(r,t);

    printf("%d",sol);

    return 0;
}