Cod sursa(job #1401115)

Utilizator andreey_047Andrei Maxim andreey_047 Data 25 martie 2015 17:38:32
Problema BMatrix Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.03 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;
};
stack<Coord>up,bot;
char a[nmax][nmax],t[nmax][nmax];
inline int FINDMAX(int lin){
 int i,j,best,p,best2,thebest;
 Coord b;
 best=best2=thebest=0;
 for(i=1;i<=m;i++)
    if(dp[lin][i]){
        j=i;
        while(dp[lin][j]){ //top
            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);
            }
                // bot
            if(bot.empty() || dp2[lin+1][j] >= bot.top().h){
                b.h = dp2[lin+1][j];
                b.poz = j;
                bot.push(b);
            }
            else{

                p=bot.top().poz;
              while(!bot.empty() && bot.top().h > dp[lin+1][j]){
                 b = bot.top();

                 bot.pop();
                 best2=max(best2,b.h*(p-b.poz+1));
              }
              b.h = dp2[lin+1][j]; b.poz = j;
              bot.push(b);
            }
          j++;
        }
        // top

         p=up.top().poz;
              while(!up.empty()){
                 b = up.top();

                 up.pop();
                 best=max(best,b.h*(p-b.poz+1));
              }

            // bot
         p=bot.top().poz;
              while(!bot.empty()){
                 b = bot.top();
                 bot.pop();
                 best2=max(best2,b.h*(p-b.poz+1));
              }
              //g << best2<<' ';
            thebest=max(thebest,best+best2);
            best=best2=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);
 //g << n << ' '<< m<<'\n';
 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=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=max(best,FINDMAX(i));
   ROTATE();
   for(i=1;i<=n;i++)
   best=max(best,FINDMAX(i));
//   for(i=1;i<=n;i++){
//      for(j=1;j<=m;j++)
//        g<<t[i][j]<<' ';
//    g <<'\n';
//   }
   g << best<<'\n';
}
int main(){
    int i;
    f >> n >> m;
    i=1;
    while(f >> (a[i]+1))i++;
    f.close();
    BMATRIX();
    g.close();
    return 0;
}