Cod sursa(job #1346617)

Utilizator ade_tomiEnache Adelina ade_tomi Data 18 februarie 2015 14:14:57
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.15 kb
#include<stdio.h>
int l[202],r[202],st[202],nr,n,m,a[202][202],p[202],sol,i,j,sus[202],jos[202],aux[202][202];
char c;
int max(int a, int b)
{

    if(a>b)
        return a;
    return b;
}
void solve(int *d)
{
    for(i=1;i<=n;i++)
    {

        for(j=1;j<=m;j++)
            if(a[i][j]==0)
                p[j]++;
            else p[j]=0;
        nr=0;
        st[0]=0;
        for(j=1;j<=m;j++)
        {
            while(nr>0&&p[st[nr]]>=p[j])
                nr--;
            l[j]=st[nr];
            nr++;
            st[nr]=j;

        }
        nr=0;
        st[0]=m+1;
        p[m+1]=0;
        for(j=m;j>=1;j--)
        {
            while(nr>0&&p[st[nr]]>=p[j])
                nr--;
            r[j]=st[nr];
            nr++;
            st[nr]=j;

        }
        d[i]=d[i-1];
        for(j=1;j<=m;j++){
            d[i]=max(d[i],(r[j]-l[j]-1)*p[j]);

        }
        //8printf("%d ",d[i]);


    }
   // printf("\n");

}
int solve2()
{
    solve(sus);
    for(j=1;j<=m;j++)
        p[j]=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            aux[i][j]=a[n-i+1][j];

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            a[i][j]=aux[i][j];
    solve(jos);
    for(i=1,j=n;i<j;i++,j--)
    {
        int ax=jos[i];
        jos[i]=jos[j];
        jos[j]=ax;
    }
    for(i=1;i<m;i++)
        sol=max(sol,sus[i]+jos[i+1]);

}
int main()
{

    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    scanf("%d%d ",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            scanf("%c ",&c);
            a[i][j]=c-'0';

        }
    solve2();
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            aux[i][j]=a[n-i+1][j];

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            a[i][j]=aux[i][j];

    for(i=1;i<=m;i++)
        sus[i]=jos[i]=p[i]=0;

    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            aux[i][j]=a[j][i];
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            a[i][j]=aux[i][j];
//    swap(n,m);
    int ax=n;
    n=m;
    m=ax;
    solve2();
    printf("%d",sol);
    return 0;
}