Cod sursa(job #1393619)

Utilizator heracleRadu Muntean heracle Data 19 martie 2015 17:12:57
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <cstdio>
#include <cstring>

FILE* in=fopen("bmatrix.in","r");
FILE* out=fopen("bmatrix.out","w");

const int Q=205;

char v[Q][Q];

int aux[Q][Q];

int r[5][Q];

int up[Q][Q];

int st[Q],dr[Q];

int stv[Q],nr;

void cerere(int v[Q][Q], int l, int c, int rez[Q])
{
    memset(up,0,sizeof up);

    for(int j=1; j<=c; j++)
    {
        for(int i=1; i<=l; i++)
        {
            if(v[i][j]==0)
                up[i][j]=up[i-1][j]+1;
        }
    }

    for(int i=1; i<=l; i++)
    {
        for(int j=1; j<=c; j++)
        {
            while(nr && up[i][stv[nr]] > up[i][j])
            {
                dr[stv[nr]]=j-1;
                nr--;
            }
            if(v[i][j]==0)
                stv[++nr]=j;
        }
        while(nr)
        {
            dr[stv[nr]]=c;
            nr--;
        }

        for(int j=c; j>0; j--)
        {
            while(nr && up[i][stv[nr]] > up[i][j])
            {
                st[stv[nr]]=j+1;
                nr--;
            }

            if(v[i][j]==0)
                stv[++nr]=j;
        }
        while(nr)
        {
            st[stv[nr]]=1;
            nr--;
        }


        for(int j=1; j<=c; j++)
        {
            if(v[i][j]==1)
                continue;

            if((dr[j]-st[j]+1)*up[i][j] > rez[i])
                rez[i]=(dr[j]-st[j]+1)*up[i][j];
        }
    }

    int max=0;

    for(int i=1; i<=l; i++)
    {
        if(max<rez[i])
            max=rez[i];
        rez[i]=max;
    }

}

int main()
{
    int l,c;

    fscanf(in,"%d%d\n",&l,&c);

    for(int i=1; i<=l; i++)
    {
        fgets(v[i]+1,Q,in);
    }

    for(int i=1; i<=l; i++)
    {
        for(int j=1; j<=c; j++)
        {
            aux[i][j]=v[i][j]-'0';
        }
    }

    cerere(aux,l,c,r[1]);

    for(int i=l; i>0; i--)
    {
        for(int j=1; j<=c; j++)
        {
            aux[i][j]=v[l-i+1][j]-'0';
        }
    }

    cerere(aux,l,c,r[2]);

    int answer=0;

    for(int i=1; i<l; i++)
    {
        if(r[1][i]+r[2][l-i] >answer)
            answer=r[1][i]+r[2][l-i];
    }


    for(int i=1; i<=l; i++)
    {
        for(int j=1; j<=c; j++)
        {
            aux[j][i]=v[i][j]-'0';
        }
    }

    cerere(aux,c,l,r[3]);

    for(int i=1; i<=l; i++)
    {
        for(int j=1; j<=c; j++)
        {
            aux[c-j+1][i]=v[i][j]-'0';
        }
    }

    cerere(aux,c,l,r[4]);

    for(int i=1; i<c; i++)
    {
        if(r[3][i]+r[4][c-i] >answer)
            answer=r[3][i]+r[4][c-i];
    }


    fprintf(out,"%d",answer);

    return 0;
}