Cod sursa(job #2712839)

Utilizator euyoTukanul euyo Data 26 februarie 2021 17:18:37
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <fstream>
#include <algorithm>
#include <stack>
 
using namespace std;
 
ifstream fin( "bmatrix.in" );
ofstream fout( "bmatrix.out" );
 
const int Lim = 202;
 
int M[Lim][Lim];
int d[Lim][Lim];
int l[Lim], r[Lim];
stack<int> s;
 
int n, m, line;
 
inline void getLR() {
  for ( int i = 1; i <= m; ++i ) {
	l[i] = 0;
	r[i] = 0;
  }
  for ( int i = 1; i <= m; ++i ) {
    while ( s.size() && d[line][s.top()] > d[line][i] ) {
      r[s.top()] = i;
      s.pop();
    }
    s.push( i );
  }
  while ( s.size() ) s.pop();
  for ( int i = m; i >= 1; --i ) {
    while ( s.size() && d[line][s.top()] > d[line][i] ) {
      l[s.top()] = i;
      s.pop();
    }
    s.push( i );
  }
  while ( s.size() ) s.pop();
  for ( int i = 1; i <= m; ++i ) {
    if ( !r[i] ) {
      r[i] = m + 1;
    }
  }
}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////

inline void MaxAreas( int mx[] ) {
  for ( int i = 1; i <= n; ++i ) {
	for (int j = 1; j <= m; ++j ) {
	  d[i][j] = 0;
	}
  }
  for ( int i = 1; i <= n; ++i ) {
    for ( int j = 1; j <= m; ++j ) {
      if ( M[i][j] == 0 ) {
        if ( i != 1 ) {
          d[i][j] = d[i - 1][j] + 1;
        } else {
          d[i][j] = 1;
        }
      }
    }
  }
  for ( int i = 1; i <= n; ++i ) {
	mx[i] = 0;
  }
  for ( int i = 1; i <= n; ++i ) {
	line = i;
    getLR();
	mx[i] = mx[i - 1];
    for ( int j = 1; j <= m; ++j ) {
      mx[i] = max( mx[i], (r[j] - l[j] - 1) * d[i][j] );
    }
  }
}
 
char str[Lim];
int aux[Lim][Lim]; 

inline void rotateRight() {
  for ( int i = 1; i <= n; ++i ) {
    for ( int j = 1; j <= m; ++j ) {
      aux[j][n - i + 1] = M[i][j];
    }
  }
  swap( m, n );
  for ( int i = 1; i <= n; ++i ) {
	for ( int j = 1; j <= m; ++j ) {
      M[i][j] = aux[i][j];
	}
  }
}

int line_best_left[Lim];
int line_best_right[Lim]; 
int col_best_left[Lim]; 
int col_best_right[Lim]; 

int main() {
  int mx;
 
  fin >> n >> m;
  for ( int i = 1; i <= n; ++i ) {
	fin >> str;
	for ( int j = 1; j <= m; ++j ) {
	  M[i][j] = str[j - 1] - '0'; 
	}
  }
  mx = 0;
  
  MaxAreas( line_best_left );
  rotateRight(), rotateRight();
  MaxAreas( line_best_right );
  
  rotateRight();
  
  MaxAreas( col_best_left );
  rotateRight(), rotateRight();
  MaxAreas( col_best_right );
  rotateRight(), rotateRight(), rotateRight();
  
  for ( int i = 1; i < n; ++i ) {
	if ( mx < line_best_left[i] + line_best_right[n - i] ) {
	  mx = line_best_left[i] + line_best_right[n - i];
	}
  }
  for ( int i = 1; i < m; ++i ) {
	if ( mx < col_best_left[i] + col_best_right[m - i] ) {
	  mx = col_best_left[i] + col_best_right[m - i]; 
	}
  }
  fout << mx;
  fin.close();
  fout.close();
  return 0;
}