Cod sursa(job #352009)

Utilizator perticas_catalinperticas catalin perticas_catalin Data 30 septembrie 2009 00:47:20
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
//O(n^3)

#include<iostream>
#include<string>

using namespace std;

#define nm 205
#define inf 1000000
#define min(a,b)((a)<(b)?(a):(b))
#define max(a,b)((a)>(b)?(a):(b))

char s[nm];
int a[nm][nm],n,m,amaxl[nm][2],amaxc[nm][2],cat[nm];

int main()
{
    int i,j,jj,ans=0,minh;
    
    freopen("bmatrix.in","r",stdin);
    freopen("bmatrix.out","w",stdout);
    
    scanf("%d %d\n",&n,&m);
    
    for(i=1;i<=n;i++)
    {
      scanf("%s\n",&s);
      
      for(j=1;j<=m;j++)
        a[i][j]=s[j-1]-'0';
    }  
    
    //aria maxima pana la o anumita linie
    
    for(i=1;i<=n;i++)
    {
      int amax=0;
      for(j=1;j<=m;j++)
      {
        if(!a[i][j]) cat[j]++;
        else cat[j]=0;
        
        jj=j,minh=inf;
        
        while(jj && minh)
        {
          minh=min(minh,cat[jj]);
          amax=max(amax,(j-jj+1)*minh);
          --jj;
        }
      }  
      amaxl[i][0]=max(amaxl[i-1][0],amax);
    }
    
    memset(cat,0,sizeof(cat));
    
    for(i=n;i>=1;i--)
    {
      int amax=0;
      for(j=1;j<=m;j++)
      {
        if(!a[i][j]) cat[j]++;
        else cat[j]=0;
        
        jj=j,minh=inf;
        
        while(jj && minh)
        {
          minh=min(minh,cat[jj]);
          amax=max(amax,(j-jj+1)*minh);
          --jj;
        }
      }  
      amaxl[i][1]=max(amaxl[i+1][1],amax);
    }
    
    //aria maxima pana la o anumita coloana
    
    memset(cat,0,sizeof(cat));
    
    for(i=1;i<=m;i++)
    {
      int amax=0;
      for(j=1;j<=n;j++)
      {
        if(!a[j][i]) cat[j]++;
        else cat[j]=0;
        
        jj=j,minh=inf;
        
        while(jj && minh)
        {
          minh=min(minh,cat[jj]);
          amax=max(amax,(j-jj+1)*minh);
          --jj;
        }
        
        amaxc[i][0]=max(amaxc[i-1][0],amax);
      }
    }
    
    memset(cat,0,sizeof(cat));
    
    for(i=m;i>=1;i--)
    {
      int amax=0;
      for(j=1;j<=n;j++)
      {
        if(!a[j][i]) cat[j]++;
        else cat[j]=0;
        
        jj=j,minh=inf;
        
        while(jj && minh)
        {
          minh=min(minh,cat[jj]);
          amax=max(amax,(j-jj+1)*minh);
          --jj;
        }
        
        amaxc[i][1]=max(amaxc[i+1][1],amax);
      }
    }
    
    for(i=1;i<=n;i++)
      ans=max(ans,amaxl[i][0]+amaxl[i+1][1]);
    
    for(i=1;i<=m;i++)
      ans=max(ans,amaxc[i][0]+amaxc[i+1][1]);
      
    
    printf("%d",ans);
    
    return 0;
}