Cod sursa(job #993882)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 4 septembrie 2013 16:50:30
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.12 kb
#include <fstream>
#include <cstring>
#include <stack>

using namespace std;

stack<int> stiva;
int v[205];
int st[205];
int dr[205];

inline void clear(int k)
{
   int i;
   for(i=0;i<k;i++)
      v[i]=0;     
}

inline int maxim(int a,int b)
{
   if(a>b)
      return a;
   return b;       
}

int calc(int k)
{
    int i;
    while(!stiva.empty())
        stiva.pop();
        
    int varf;
    for(i=0;i<k;i++)
    {
        while(!stiva.empty())
           if(v[stiva.top()]>=v[i])
              stiva.pop();
           else
              break;
        if(stiva.empty())
           varf=-1;
        else
           varf=stiva.top();
        st[i]=i-varf;    
        stiva.push(i);         
    }
    
    /////////////////////////////
    while(!stiva.empty())
        stiva.pop();
        
    for(i=k-1;i>=0;i--)
    {
        while(!stiva.empty())
           if(v[stiva.top()]>=v[i])
              stiva.pop();
           else
              break;
        if(stiva.empty())
           varf=k;
        else
           varf=stiva.top();
        dr[i]=varf-i; 
        stiva.push(i);            
    }
    
    int maxim=-1;   
    for(i=0;i<k;i++)
    {
       st[i]+=dr[i],st[i]--,st[i]*=v[i];
       if(st[i]>maxim)
          maxim=st[i];
    }
    return maxim;
}

int main()
{
    ifstream cin("bmatrix.in");
    ofstream cout("bmatrix.out");
    int n=0,m=0,i,j,mat[205][205];
    cin>>n>>m;
    cin.get();
    char sir[205];
    
    for(i=0;i<n;i++)
    {
       cin.get(sir,205);
       cin.get();
       for(j=0;j<m;j++)
       {
          mat[i][j]=1-(sir[j]-'0');                
       }  
    }
    
    int sus[205],jos[205],st[205],dr[205];
    
    for(i=0;i<n;i++)
    {
        for(j=0;j<m;j++)
           v[j]=(mat[i][j])?(v[j]+1):0;
        sus[i]=maxim(calc(m),((i>0)?(sus[i-1]):(0)));    
    }
    clear(m);
    for(i=n-1;i>=0;i--)
    {
        for(j=0;j<m;j++)
           v[j]=(mat[i][j])?(v[j]+1):0;
        jos[i]=maxim(calc(m),((i<(n-1))?(jos[i+1]):(0)));   
    }
    
    int global=-1,aux;
    for(i=1;i<n;i++)
    {
        aux=sus[i-1]+jos[i];
        if(aux>global)
           global=aux;            
    }
    
    clear(m);
    /////////////////////////////////////////
    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
           v[j]=(mat[j][i])?(v[j]+1):0;
        st[i]=calc(n);
        st[i]=maxim(calc(n),((i>0)?(st[i-1]):(0)));        
    }
    clear(n);
    for(i=m-1;i>=0;i--)
    {
        for(j=0;j<n;j++)
           v[j]=(mat[j][i])?(v[j]+1):0;
        dr[i]=calc(n);    
        dr[i]=maxim(calc(n),((i<(m-1))?(dr[i+1]):(0)));   
    }
    
    for(i=1;i<m;i++)
    {
        aux=st[i-1]+dr[i];
        if(aux>global)
           global=aux;            
    }
    cout<<global<<'\n';
   // for(i=0;i<n;i++)
   // {
   //    cout<<sus[i]<<' '<<jos[i]<<endl;                
   // }
   // cout<<"stop"<<m<<endl;
    //for(j=0;j<m;j++)
    //{
    //  cout<<st[j]<<' '<<dr[j]<<endl;     
   // }
    
    
    //system("PAUSE");
    cin.close();
    cout.close();
    return 0;
}