Cod sursa(job #1837753)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 30 decembrie 2016 13:41:55
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <bits/stdc++.h>
#define MAXN 201
char mat[MAXN+1][MAXN+1];
char cop[MAXN+1][MAXN+1];
inline int getmax(int a,int b){
   if(a<b) return b;
   return a;
}
int stiv[MAXN+1],high[MAXN+1],len[MAXN+1];
int sl[MAXN+1],sr[MAXN+1];
inline int solve(int n,int m){
   int ans,i,j,ist,l,p;
   memset(sl,0,sizeof(sl));
   memset(sr,0,sizeof(sr));
   memset(high,0,sizeof(high));
   for(i=1;i<=n;i++){
      ist=-1;
      for(j=1;j<=m;j++){
         if(mat[i][j]==1)
            high[j]=0;
         else
            high[j]++;
         l=0;
         while(ist>=0&&high[stiv[ist]]>=high[j]){
            l+=len[ist];
            if(sl[j]<l*high[stiv[ist]])
               sl[j]=l*high[stiv[ist]];
            ist--;
         }
         ist++;
         stiv[ist]=j;
         len[ist]=l+1;
         p=ist;
         l=0;
         while(p>=0){
            l+=len[p];
            if(l*high[stiv[p]]>sl[j])
              sl[j]=l*high[stiv[p]];
            p--;
         }
      }
   }
   for(j=1;j<=m;j++)
     sl[j]=getmax(sl[j-1],sl[j]);
   memset(high,0,sizeof(high));
   for(i=1;i<=n;i++){
      ist=-1;
      for(j=m;j>=1;j--){
         if(mat[i][j]==1)
            high[j]=0;
         else
            high[j]++;
         l=0;
         while(ist>=0&&high[stiv[ist]]>=high[j]){
            l+=len[ist];
            if(sr[j]<l*high[stiv[ist]])
               sr[j]=l*high[stiv[ist]];
            ist--;
         }
         ist++;
         stiv[ist]=j;
         len[ist]=l+1;
         p=ist;
         l=0;
         while(p>=0){
            l+=len[p];
            if(l*high[stiv[p]]>sr[j])
              sr[j]=l*high[stiv[p]];
            p--;
         }
      }
      l=0;
      while(ist>=0){
         l+=len[ist];
         if(sr[1]<l*high[stiv[ist]])
            sr[1]=l*high[stiv[ist]];
         ist--;
      }
   }
   for(j=m;j>=1;j--)
     sr[j]=getmax(sr[j+1],sr[j]);
   ans=0;
   for(i=1;i<m;i++)
     ans=getmax(ans,sl[i]+sr[i+1]);
   return ans;
}
int main(){
   FILE*fi,*fout;
   int i,j,n,m,ans;
   fi=fopen("bmatrix.in" ,"r");
   fout=fopen("bmatrix.out" ,"w");
   fscanf(fi,"%d %d " ,&n,&m);
   for(i=1;i<=n;i++){
      for(j=1;j<=m;j++){
        mat[i][j]=fgetc(fi)-'0';
        cop[i][j]=mat[i][j];
      }
      fgetc(fi);
   }
   ans=solve(n,m);
   for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
     mat[m-j+1][i]=cop[i][j];
   ans=getmax(ans,solve(m,n));
   fprintf(fout,"%d" ,ans);
   fclose(fi);
   fclose(fout);
   return 0;
}