Cod sursa(job #1315612)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 12 ianuarie 2015 22:26:44
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.05 kb
#include<cstdio>
int n,m,i,j,smax,x[210][210],sus[210],jos[210];
char s[210][210],t[210][210];
struct st{
    int h;
    int p;
}st[210];
FILE *f,*g;
int maxim(int a,int b){
    if(a>b)
        return a;
    return b;
}
void calc(){
    int i,j,nr,a,p,aux;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++)
            if(s[i][j]=='0')
                x[i][j]=x[i-1][j]+1;
            else
                x[i][j]=0;
        sus[i]=jos[i]=0;
    }
    for(i=1;i<=n;i++){
        nr=0;
        for(j=1;j<=m+1;j++){
            if(x[i][j]>st[nr].h){
                nr++;
                st[nr].h=x[i][j];
                st[nr].p=j;
            }
            else{
                while(x[i][j]<=st[nr].h&&nr) {
                    a=(j-st[nr].p)*st[nr].h;
                    sus[i]=maxim(sus[i],a);
                    p=st[nr].p;
                    nr--;
                }
                if(x[i][j]>0){
                    nr++;
                    st[nr].p=p;
                    st[nr].h=x[i][j];
                }
            }
        }
    }
    for(i=2;i<=n;i++){
        sus[i]=maxim(sus[i],sus[i-1]);
    }
    for(i=1;i<=n/2;i++)
        for(j=1;j<=m;j++){
            aux=s[i][j];
            s[i][j]=s[n-i+1][j];
            s[n-i+1][j]=aux;
        }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++)
            if(s[i][j]=='0')
                x[i][j]=x[i-1][j]+1;
            else
                x[i][j]=0;
    }
    for(i=1;i<=n;i++){
        nr=0;
        for(j=1;j<=m+1;j++){
            if(x[i][j]>st[nr].h){
                nr++;
                st[nr].h=x[i][j];
                st[nr].p=j;
            }
            else{
                while(x[i][j]<=st[nr].h&&nr) {
                    a=(j-st[nr].p)*st[nr].h;
                    jos[i]=maxim(jos[i],a);
                    p=st[nr].p;
                    nr--;
                }
                if(x[i][j]>0){
                    nr++;
                    st[nr].p=p;
                    st[nr].h=x[i][j];
                }
            }
        }
    }
    for(i=2;i<=n;i++){
        jos[i]=maxim(jos[i],jos[i-1]);
    }
    for(i=1;i<=n/2;i++){
        aux=jos[i];
        jos[i]=jos[n-i+1];
        jos[n-i+1]=aux;
    }
    for(i=1;i<=n/2;i++){
        for(j=1;j<=m;j++){
            aux=s[i][j];
            s[i][j]=s[n-i+1][j];
            s[n-i+1][j]=aux;
        }
    }
}
int main(){
    f=fopen("bmatrix.in","r");
    g=fopen("bmatrix.out","w");
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=n;i++){
        fscanf(f,"%s",s[i]+1);
    }
    calc();
    for(i=1;i<=n;i++){
        smax=maxim(smax,sus[i]+jos[i+1]);
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            t[j][n-i+1]=s[i][j];
        }
    }
    for(i=1;i<=m;i++){
        for(j=1;j<=n;j++){
            s[i][j]=t[i][j];
        }
    }
    int aux=n;
    n=m;
    m=aux;
    calc();
    for(i=1;i<=n;i++){
        smax=maxim(smax,sus[i]+jos[i+1]);
    }
    fprintf(g,"%d",smax);
    fclose(f);
    fclose(g);
    return 0;
}