Cod sursa(job #2125776)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 8 februarie 2018 18:33:17
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 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];
int dr[205][205],s[205],n,m,i,j,k,ii,jj,val,maxim;
int sol(int n,int m){
    int maxim=0,u;
    for(i=1;i<=n;i++){
        u=1;
        s[1]=0;
        nr[i][0]=-1;
        for(j=1;j<=m;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]])
                u--;
            st[i][j]=s[u]+1;
            s[++u]=j;
        }
        u=1;
        s[1]=m+1;
        nr[i][m+1]=-1;
        for(j=m;j>=1;j--){
            while(nr[i][j]<=nr[i][s[u]])
                u--;
            dr[i][j]=s[u]-1;
            maxim=max(maxim,nr[i][j]*(dr[i][j]-st[i][j]+1));
            s[++u]=j;
        }
    }
    return 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';
    }
    for(k=1;k<n;k++){
        for(i=1;i<=k;i++)
            for(j=1;j<=m;j++)
                d[i][j]=v[i][j];
        val=sol(k,m);
        for(i=k+1;i<=n;i++)
            for(j=1;j<=m;j++)
                d[i-k][j]=v[i][j];
        val+=sol(n-k,m);
        maxim=max(maxim,val);
    }
    for(k=1;k<m;k++){
        for(i=1;i<=n;i++)
            for(j=1;j<=k;j++)
                d[i][j]=v[i][j];
        val=sol(n,k);
        for(i=1;i<=n;i++)
            for(j=k+1;j<=m;j++)
                d[i][j-k]=v[i][j];
        val+=sol(n,m-k);
        maxim=max(maxim,val);
    }
    fout<<maxim<<"\n";
    return 0;
}