Cod sursa(job #1340664)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 11 februarie 2015 22:49:53
Problema BMatrix Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 8.86 kb
#include <fstream>
#include <cstring>
#define DIM  210
using namespace std;

ifstream fin ("bmatrix.in" );
ofstream fout("bmatrix.out");

int n, m, i, j, k, ok, minim, maxim, x, y;
int a[DIM][DIM], b[DIM][DIM], c[DIM][DIM];
int d[DIM][DIM],  e[DIM][DIM],  nord[DIM];
int f[3][DIM],sud[DIM],est[DIM],vest[DIM];

char s[DIM];

void Read(){
     fin >> n >> m;
     for(i = 1; i <= n; i ++){
          fin >> s + 1;
          for(j = 1; j <= m; j ++)
               a[i][j] = s[j] - '0';
     }
     return;
}

void SumeNS(){
     for(i = 1; i <= n; i ++)
          for(j = 1; j <= m; j ++)
               if(a[i][j] == 1) b[i][j] = 0;
               else b[i][j] = b[i-1][j] + 1;
     for(i = n; i >= 1; i --)
          for(j = 1; j <= m; j ++)
               if(a[i][j] == 1) c[i][j] = 0;
               else c[i][j] = c[i+1][j] + 1;
     return;
}

void SumeVE(){
     for(j = 1; j <= m; j ++)
          for(i = 1; i <= n; i ++)
               if(a[i][j] == 1) d[i][j] = 0;
               else d[i][j] = d[i][j-1] + 1;
     for(j = m; j >= 1; j --)
          for(i = 1; i <= n; i ++)
               if(a[i][j] == 1) e[i][j] = 0;
               else e[i][j] = e[i][j+1] + 1;
     return;
}

void TundeNS(){
     for(i = 1; i <= n; i ++){
          k = 0;
          for(j = 1; j <= m + 1; j ++){
               if(b[i][j] >= f[1][k] && b[i][j] != 0){
                    k ++;
                    f[1][k] = b[i][j];
                    f[2][k] = j;
               }
               else{
                    maxim = 0;
                    while(f[1][k] > b[i][j] && k != 0){
                         if(f[1][k] == f[1][k-1]){
                              f[1][k] = 0;
                              f[2][k] = 0;
                              k --;
                         }
                         else{
                              if(maxim < b[i][f[2][k]]   * (j-f[2][k]))
                                   maxim = b[i][f[2][k]] * (j-f[2][k]);
                              if(k > 1){
                                   f[1][k] = 0;
                                   f[2][k] = 0;
                                   k --;
                              }
                              else{
                                   f[1][k] = b[i][j];
                                   b[i][f[2][k]] = b[i][j];
                              }
                         }
                    }
                    if(nord[i] < maxim) nord[i] = maxim;
                    if(b[i][j] != 0){
                         k ++;
                         f[1][k] = b[i][j];
                         f[2][k] = j;
                    }
               }
          }
     }
     /*
     maxim = 0;
     for(i = 1; i <= n; i ++)
          if(nord[i] > maxim)
               maxim = nord[i];
     fout << maxim << "\n";
     */
     return;
}

void TundeSN(){
     for(i = n; i >= 1; i --){
          k = 0;
          for(j = 1; j <= m + 1; j ++){
               if(c[i][j] >= f[1][k] && c[i][j] != 0){
                    k ++;
                    f[1][k] = c[i][j];
                    f[2][k] = j;
               }
               else{
                    maxim = 0;
                    while(f[1][k] > c[i][j] && k != 0){
                         if(f[1][k] == f[1][k-1]){
                              f[1][k] = 0;
                              f[2][k] = 0;
                              k --;
                         }
                         else{
                              if(maxim < c[i][f[2][k]]   * (j-f[2][k]))
                                   maxim = c[i][f[2][k]] * (j-f[2][k]);
                              if(k > 1){
                                   f[1][k] = 0;
                                   f[2][k] = 0;
                                   k --;
                              }
                              else{
                                   f[1][k] = c[i][j];
                                   c[i][f[2][k]] = c[i][j];
                              }
                         }
                    }
                    if(sud[i] < maxim) sud[i] = maxim;
                    if(c[i][j] != 0){
                         k ++;
                         f[1][k] = c[i][j];
                         f[2][k] = j;
                    }
               }
          }
     }
     /*
     maxim = 0;
     for(i = 1; i <= n; i ++)
          if(sud[i] > maxim)
               maxim = sud[i];
     fout << maxim << "\n";
     */
     return;
}

void TundeVE(){
     for(j = 1; j <= m; j ++){
          k = 0;
          for(i = 1; i <= n + 1; i ++){
               if(d[i][j] >= f[1][k] && d[i][j] != 0){
                    k ++;
                    f[1][k] = d[i][j];
                    f[2][k] = i;
               }
               else{
                    maxim = 0;
                    while(f[1][k] > d[i][j] && k != 0){
                         if(f[1][k] == f[1][k-1]){
                              f[1][k] = 0;
                              f[2][k] = 0;
                              k --;
                         }
                         else{
                              if(maxim < d[f[2][k]][j] * (i-f[2][k]))
                                   maxim = d[f[2][k]][j] * (i-f[2][k]);
                              if(k > 1){
                                   f[1][k] = 0;
                                   f[2][k] = 0;
                                   k --;
                              }
                              else{
                                   f[1][k] = d[i][j];
                                   d[f[2][k]][j] = d[i][j];
                              }
                         }
                    }
                    if(vest[j] < maxim) vest[j] = maxim;
                    if(d[i][j] != 0){
                         k ++;
                         f[1][k] = d[i][j];
                         f[2][k] = i;
                    }
               }
          }
     }
     /*
     maxim = 0;
     for(i = 1; i <= m; i ++)
          if(vest[i] > maxim)
               maxim = vest[i];
     fout << maxim << "\n";
     */
     return;
}

void TundeEV(){
     for(j = m; j >= 1; j --){
          k = 0;
          for(i = 1; i <= n + 1; i ++){
               if(e[i][j] >= f[1][k] && e[i][j] != 0){
                    k ++;
                    f[1][k] = e[i][j];
                    f[2][k] = i;
               }
               else{
                    maxim = 0;
                    while(f[1][k] > e[i][j] && k != 0){
                         if(f[1][k] == f[1][k-1]){
                              f[1][k] = 0;
                              f[2][k] = 0;
                              k --;
                         }
                         else{
                              if(maxim < e[f[2][k]][j]   * (i-f[2][k]))
                                   maxim = e[f[2][k]][j] * (i-f[2][k]);
                              if(k > 1){
                                   f[1][k] = 0;
                                   f[2][k] = 0;
                                   k --;
                              }
                              else{
                                   f[1][k] = e[i][j];
                                   e[f[2][k]][j] = e[i][j];
                              }
                         }
                    }
                    if(est[j] < maxim) est[j] = maxim;
                    if(e[i][j] != 0){
                         k ++;
                         f[1][k] = e[i][j];
                         f[2][k] = i;
                    }
               }
          }
     }
     /*
     maxim = 0;
     for(i = 1; i <= m; i ++)
          if(est[i] > maxim)
               maxim = est[i];
     fout << maxim << "\n";
     */
     return;
}

void Remake_Vectors(){
     maxim = 0;
     for(i = 1; i <= n; i ++){
          if(maxim < nord[i])
               maxim = nord[i];
          nord[i] = maxim;
     }
     maxim = 0;
     for(i = n; i >= 1; i --){
          if(maxim < sud[i])
               maxim = sud[i];
          sud[i] = maxim;
     }
     maxim = 0;
     for(i = 1; i <= m; i ++){
          if(maxim < vest[i])
               maxim = vest[i];
          vest[i] = maxim;
     }
     maxim = 0;
     for(i = m; i >= 1; i --){
          if(maxim < est[i])
               maxim = est[i];
          est[i] = maxim;
     }
     return;
}

void Max_Array(){
     maxim = 0;
     for(i = 1; i < n; i ++)
          if(nord[i] + sud[i+1] > maxim)
               maxim = nord[i] + sud[i+1];
     for(i = 1; i < m; i ++)
          if(vest[i] + est[i+1] > maxim)
               maxim = vest[i] + est[i+1];
     fout << maxim;
     return;
}

int main(){
     Read();
     SumeNS(); SumeVE();
     TundeNS(); TundeSN();
     TundeVE(); TundeEV();
     Remake_Vectors();
     Max_Array();
     return 0;
}