Cod sursa(job #1729717)

Utilizator stefzahZaharia Stefan Tudor stefzah Data 15 iulie 2016 15:23:51
Problema BMatrix Scor 36
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.45 kb
#include <fstream>
#include <stack>
using namespace std;
ifstream fin("bmatrix.in");
ofstream fout("bmatrix.out");
int n,m,i,j,st[205],dr[205],a[205][205],q,mx1,mx2,k,s,b[205],MX,qe;
bool v[205][205];
char x;
stack <int>S;
int main()
{fin>>n>>m;
 for(i=1;i<=n;i++)
    {for(j=1;j<=m;j++)
        {fin>>x;
         v[i][j]=x-48;
         if(v[i][j]==0)a[i][j]=a[i-1][j]+1;
           else a[i][j]=0;
        }
    }
    st[0]=0;
    dr[0]=m+1;
 for(k=1;k<=n-1;k++)
    {mx1=0;mx2=0;
     for(i=1;i<=k;i++)
        {S.push(0);
         for(j=1;j<=m;j++)
            {st[j]=1;dr[j]=m;
             if(S.size()==0)S.push(j);
             else {while(S.size()>0&&a[i][j]<a[i][S.top()]){dr[S.top()]=j-1;S.pop();
                                                     }
                   if(a[i][j]==a[i][S.top()])st[j]=st[S.top()];
                     else st[j]=S.top()+1;
                   S.push(j);
                  }
            }
         while(S.size()>0)S.pop();
         for(j=1;j<=m;j++)
            {s=a[i][j]*(dr[j]-st[j]+1);
           //  fout<<s<<" ";
             if(s>mx1)mx1=s;
            }
          //  fout<<"\n";
        }
     for(i=k+1;i<=n;i++)
        {S.push(0);
         for(j=1;j<=m;j++)
            b[j]=a[i][j];
         for(j=1;j<=m;j++)
            {st[j]=1;dr[j]=m;
             if(a[i][j]>i-k)a[i][j]=i-k;
             if(S.size()==0)S.push(j);
             else {while(S.size()>0&&a[i][j]<a[i][S.top()]){dr[S.top()]=j-1;S.pop();
                                                     }
                   if(a[i][j]==a[i][S.top()])st[j]=st[S.top()];
                     else st[j]=S.top()+1;
                   S.push(j);
                  }
            }
         while(S.size()>0)S.pop();
         for(j=1;j<=m;j++)
            {s=a[i][j]*(dr[j]-st[j]+1);
             if(s>mx2)mx2=s;
            }
         for(j=1;j<=m;j++)
            a[i][j]=b[j];
        }
        if(mx1+mx2>MX&&mx1>0&&mx2>0)MX=mx1+mx2;
    }
 for(k=1;k<=m-1;k++)
    {mx1=0;mx2=0;
     for(i=1;i<=n;i++)
        {S.push(0);
         for(j=1;j<=k;j++)
            {st[j]=1;dr[j]=k;
             if(S.size()==0)S.push(j);
             else {while(S.size()>0&&a[i][j]<a[i][S.top()]){dr[S.top()]=j-1;S.pop();
                                                     }
                   if(a[i][j]==a[i][S.top()])st[j]=st[S.top()];
                     else st[j]=S.top()+1;
                   S.push(j);
                  }
            }
         while(S.size()>0)S.pop();
         for(j=1;j<=k;j++)
            {s=a[i][j]*(dr[j]-st[j]+1);
          //   fout<<s<<" ";
             if(s>mx1)mx1=s;
            }
        }
     for(i=1;i<=n;i++)
        {S.push(k);
         qe=a[i][k];
         a[i][k]=0;
         for(j=k+1;j<=m;j++)
            {st[j]=k+1;dr[j]=n;
             if(S.size()==0)S.push(j);
             else {while(S.size()>0&&a[i][j]<a[i][S.top()]){dr[S.top()]=j-1;S.pop();
                                                     }
                   if(a[i][j]==a[i][S.top()])st[j]=st[S.top()];
                     else st[j]=S.top()+1;
                   S.push(j);
                  }
            }
         while(S.size()>0)S.pop();
         for(j=k+1;j<=m;j++)
            {s=a[i][j]*(dr[j]-st[j]+1);
           //  fout<<s<<"* ";
             if(s>mx2)mx2=s;
            }
         a[i][k]=qe;
        }
         //fout<<"\n";
        if(mx1+mx2>MX&&mx1>0&&mx2>0)MX=mx1+mx2;
    }
 fout<<MX;

}