Cod sursa(job #1837727)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 30 decembrie 2016 13:08:58
Problema BMatrix Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
#include <bits/stdc++.h>
#define MAXN 200
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];
inline int Skyline(int n,int col1,int col2){
   int i,j,ans,ist,l;
   memset(high,0,sizeof(high));
   ans=0;
   for(i=1;i<=n;i++){
     ist=-1;
     for(j=col1;j<=col2;j++){
        if(mat[i][j]==0)
          high[j]++;
        else
          high[j]=0;
        l=0;
        while(ist>=0&&high[stiv[ist]]>=high[j]){
           l+=len[ist];
           if(ans<l*high[stiv[ist]])
             ans=l*high[stiv[ist]];
           ist--;
        }
        ist++;
        stiv[ist]=j;
        len[ist]=l+1;
     }
     l=0;
     while(ist>=0){
         l+=len[ist];
         if(ans<l*high[stiv[ist]])
            ans=l*high[stiv[ist]];
         ist--;
     }
   }
   return ans;
}
inline int solve(int n,int m){
   int ans,col;
   ans=0;
   for(col=1;col<m;col++)
     ans=getmax(ans,Skyline(n,1,col)+Skyline(n,col+1,m));
   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;
}