Cod sursa(job #1401281)

Utilizator andreey_047Andrei Maxim andreey_047 Data 25 martie 2015 19:11:06
Problema BMatrix Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <iostream>
#include <fstream>
#include <stack>
#define nmax 205
using namespace std;
ifstream f("bmatrix.in");
ofstream g("bmatrix.out");
int n,m,dp[nmax][nmax],dp2[nmax][nmax];
struct Coord{
 int h,poz;
};
int big,dx,dy,px,py;
int bigg,dxx,dyy,pxx,pyy;
stack<Coord>up,bot;
char a[nmax][nmax],t[nmax][nmax];
inline int FINDMAX(int lin,int dp[nmax][nmax]){
 int i,j,best,p,thebest;
 Coord b;
 best=thebest=0;
 for(i=1;i<=m;i++)
    if(dp[lin][i]){
        j=i;
        while(dp[lin][j]){
            if(up.empty() || dp[lin][j] > up.top().h){
                b.h = dp[lin][j];
                b.poz = j;
                up.push(b);
            }
            else{
                p=up.top().poz;
              while(!up.empty() && up.top().h > dp[lin][j]){
                 b = up.top();
                 up.pop();
                  best=max(best,b.h*(p-b.poz+1));
              }
              b.h = dp[lin][j]; b.poz = j;
              up.push(b);
            }
          j++;
        }
         p=up.top().poz;
              while(!up.empty()){
                 b = up.top();

                 up.pop();
                  best=max(best,b.h*(p-b.poz+1));
              }
              thebest=max(thebest,best);
            best=0;
      i=j;
    }
    return thebest;
}
inline void ROTATE(){
 int i,j;
 for(i=1;i<=n;i++)
    for(j=1;j<=m;j++){
      dp[i][j]=dp2[i][j]=dp[j][i]=dp2[j][i]=0;
      t[j][i]= a[i][j];
 }
 swap(n,m);
 for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
     if(t[i][j]=='0')dp[i][j]=dp[i-1][j]+1;
   for(i=n;i>0;i--)
    for(j=1;j<=m;j++)
     if(t[i][j]=='0') dp2[i][j]=dp2[i+1][j]+1;
}
inline void BMATRIX(){
  int i,j,best,best2,thebest;
  best=best2=thebest=0;
  for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
     if(a[i][j]=='0')dp[i][j]=dp[i-1][j]+1;
   for(i=n;i>0;i--)
    for(j=1;j<=m;j++)
     if(a[i][j]=='0') dp2[i][j]=dp2[i+1][j]+1;

  for(i=1;i<=n;i++){
      best=best2=0;
   for(j=1;j<=i;j++)
    best=max(best,FINDMAX(j,dp));
   for(j=i+1;j<=n;j++)
    best2=max(best2,FINDMAX(j,dp2));
   thebest=max(thebest,best+best2);
  }
   ROTATE();
  for(i=1;i<=n;i++){
      best=best2=0;
   for(j=1;j<=i;j++)
    best=max(best,FINDMAX(j,dp));
   for(j=i+1;j<=n;j++)
    best2=max(best2,FINDMAX(j,dp2));
   thebest=max(thebest,best+best2);
  }
   g << thebest<<'\n';
}
int main(){
    int i;
    f >> n >> m;
    i=1;
    while(f >> (a[i]+1))i++;
    f.close();
    BMATRIX();
    g.close();
    return 0;
}