Cod sursa(job #2332430)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 30 ianuarie 2019 18:59:08
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

ifstream f ("bmatrix.in");
ofstream g ("bmatrix.out");

const int NMAX = 205;

int n, m;
char a[NMAX][NMAX], b[NMAX][NMAX];
int h[NMAX];
int max_area_top[NMAX];
int max_area_bot[NMAX];

inline void maxi (int &a, int b) {
  a = max (a, b);
}

inline int defaultVal1 (int pas, int n) {
  return (pas == 1) ? 0 : n;
}

inline int defaultVal2 (int pas) {
  return (pas == 1) ? 0 : -1;
}

void getArea (int pas, vi &v, int h[], int n) {
  int st = 1;
  if (pas == -1) st = n;
  stack <int> stk;
  for (int i = st; 1 <= i && i <= n; i += pas) {
    while (!stk.empty() && h[stk.top()] >= h[i]) {
      stk.pop();
    }
    v[i] = stk.empty() ? defaultVal1 (pas, n) : (stk.top() + defaultVal2 (pas));
    stk.push (i);
  }
  while (!stk.empty()) stk.pop();
}

int getMaxArea (int h[], int n) {
  stack <int> stk;
  vi lft (n + 2, 0), rgt (n + 2, 0);

  getArea  (1, lft, h, n);
  getArea (-1, rgt, h, n);

  int ret = 0;
  for (int i = 1; i <= n; ++i) {
    maxi (ret, (rgt[i] - lft[i]) * h[i]);
  }
  return ret;
}

void calcMaxAreas (int pas, int max_area[]) {
  int st = 1;
  if (pas == -1) st = n;

  memset (h, 0, sizeof (h));
  for (int i = st; 1 <= i && i <= n; i += pas) {
    for (int j = 1; j <= m; ++j) {
      h[j] = a[i][j] == '0' ? h[j] + 1 : 0;
    }
    max_area[i] = max (max_area[i - pas], getMaxArea (h, m));
  }
}

void rotateMatrix() {
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      b[j][n - i + 1] = a[i][j];
    }
  }
  swap (n, m);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      a[i][j] = b[i][j];
    }
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL_DEFINE
  freopen (".in", "r", stdin);
#endif

  f >> n >> m;
  f.get();
  for (int i = 1; i <= n; ++i) {
    f.getline (a[i] + 1, NMAX);
  }

  int ans = 0;
  for (int it = 1; it <= 2; ++it) {
    memset (max_area_top, 0, sizeof (max_area_top));
    memset (max_area_bot, 0, sizeof (max_area_bot));
    calcMaxAreas (1, max_area_top);
    calcMaxAreas (-1, max_area_bot);

    for (int i = 1; i <= n; ++i) {
      maxi (ans, max_area_top[i] + max_area_bot[i + 1]);
    }
    rotateMatrix();
  }

  g << ans << '\n';

  f.close();
  g.close();

#ifdef LOCAL_DEFINE
  fprintf (stderr, "Time elapsed: %lf s.\n", 1.0 * clock() / CLOCKS_PER_SEC);
#endif
  return 0;
}