Cod sursa(job #2711262)

Utilizator euyoTukanul euyo Data 23 februarie 2021 20:42:52
Problema BMatrix Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <fstream>
#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 x1, _y1, x2, y2, line;

inline void getLR() {
  for ( int i = _y1; i <= y2; ++i ) {
	l[i] = _y1 - 1;
	r[i] = 0;
  }
  for ( int i = _y1; i <= y2; ++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 = y2; i >= _y1; --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 = _y1; i <= y2; ++i ) {
    if ( !r[i] ) {
      r[i] = y2 + 1;
    }
  }
}

inline int MaxArea() {
  for ( int i = x1; i <= x2; ++i ) {
    for ( int j = _y1; j <= y2; ++j ) {
      if ( M[i][j] == 0 ) {
        if ( i != x1 ) {
          d[i][j] = d[i - 1][j] + 1;
        } else {
          d[i][j] = 1;
        }
      }
    }
  }
  int maxa = 0;
  for ( int i = x1; i <= x2; ++i ) {
	line = i;
	getLR();
    for ( int j = _y1; j <= y2; ++j ) {
      if ( (r[j] - l[j] - 1) * d[i][j] > maxa ) {
        maxa = (r[j] - l[j] - 1) * d[i][j];
	  }
    }
  }
  return maxa;
}

char str[Lim];

int main() {
  int n, m, mx, res1, res2;
 
  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;
  for ( int i = 1; i < n; ++i ) {
    x1 = 1, x2 = i, _y1 = 1, y2 = m;
	res1 = MaxArea();
    x1 = i + 1, x2 = n, _y1 = 1, y2 = m;
	res2 = MaxArea();
	mx = mx < (res1 + res2) ? (res1 + res2) : mx;
  }
  for ( int i = 1; i <= n; ++i ) {
	for ( int j = 1; j <= m; ++j ) {
	  d[i][j] = l[j] = r[j] = 0;
	}
  }
  for ( int j = 1; j < m; ++j ) {
    x1 = 1, x2 = n, _y1 = 1, y2 = j;
	res1 = MaxArea();
    x1 = 1, x2 = n, _y1 = j + 1, y2 = m;
	res2 = MaxArea();
	mx = mx < (res1 + res2) ? (res1 + res2) : mx;
  }
  fout << mx;
  fin.close();
  fout.close();
  return 0;
}