Cod sursa(job #2125820)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 8 februarie 2018 19:20:10
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.99 kb
# include <fstream>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
char ch[205];
int d[205][205],v[205][205],nr[205][205],st[205][205],dr[205][205];
int ost[205],odr[205],vst[205],vdr[205],s[205],n,m,i,j,k,val,maxim;
void osol(int n,int m){
    int maxim=0,u;
    for(i=1;i<=n;i++){
        u=1;
        s[1]=0;
        nr[i][0]=-1;
        nr[i][m+1]=n+1;
        for(j=1;j<=m+1;j++){
            if(d[i][j]==0)
                nr[i][j]=nr[i-1][j]+1;
            else
                nr[i][j]=0;
            while(nr[i][j]<=nr[i][s[u]]){
                dr[i][s[u]]=j-1;
                maxim=max(maxim,nr[i][s[u]]*(dr[i][s[u]]-st[i][s[u]]+1));
                u--;
            }
            st[i][j]=s[u]+1;
            s[++u]=j;
        }
        ost[i]=maxim;
    }
    maxim=0;
    for(i=n;i>=1;i--){
        u=1;
        s[1]=0;
        nr[i][0]=-1;
        nr[i][m+1]=n+1;
        for(j=1;j<=m+1;j++){
            if(d[i][j]==0)
                nr[i][j]=nr[i+1][j]+1;
            else
                nr[i][j]=0;
            while(nr[i][j]<=nr[i][s[u]]){
                dr[i][s[u]]=j-1;
                maxim=max(maxim,nr[i][s[u]]*(dr[i][s[u]]-st[i][s[u]]+1));
                u--;
            }
            st[i][j]=s[u]+1;
            s[++u]=j;
        }
        odr[i]=maxim;
    }
}
void vsol(int n,int m){
    int maxim=0,u;
    for(i=1;i<=n;i++){
        u=1;
        s[1]=0;
        nr[i][0]=-1;
        nr[i][m+1]=n+1;
        for(j=1;j<=m+1;j++){
            if(d[i][j]==0)
                nr[i][j]=nr[i-1][j]+1;
            else
                nr[i][j]=0;
            while(nr[i][j]<=nr[i][s[u]]){
                dr[i][s[u]]=j-1;
                maxim=max(maxim,nr[i][s[u]]*(dr[i][s[u]]-st[i][s[u]]+1));
                u--;
            }
            st[i][j]=s[u]+1;
            s[++u]=j;
        }
        vst[i]=maxim;
    }
    maxim=0;
    for(i=n;i>=1;i--){
        u=1;
        s[1]=0;
        nr[i][0]=-1;
        nr[i][m+1]=n+1;
        for(j=1;j<=m+1;j++){
            if(d[i][j]==0)
                nr[i][j]=nr[i+1][j]+1;
            else
                nr[i][j]=0;
            while(nr[i][j]<=nr[i][s[u]]){
                dr[i][s[u]]=j-1;
                maxim=max(maxim,nr[i][s[u]]*(dr[i][s[u]]-st[i][s[u]]+1));
                u--;
            }
            st[i][j]=s[u]+1;
            s[++u]=j;
        }
        vdr[i]=maxim;
    }
}
int main () {
    fin>>n>>m;
    for(i=1;i<=n;i++){
        fin>>ch+1;
        for(j=1;j<=m;j++){
            v[i][j]=ch[j]-'0';
            d[i][j]=v[i][j];
        }
    }
    osol(n,m);
    for(i=0;i<=n+1;i++)
        for(j=0;j<=m+1;j++){
            d[j][i]=v[i][j];
            nr[j][i]=0;
            st[j][i]=0;
            dr[j][i]=0;
        }
    vsol(m,n);
    for(k=1;k<n;k++)
        maxim=max(maxim,ost[k]+odr[k+1]);
    for(k=1;k<m;k++)
        maxim=max(maxim,vst[k]+vdr[k+1]);
    fout<<maxim<<"\n";
    return 0;
}