Cod sursa(job #2200033)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 30 aprilie 2018 08:46:37
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int a[205][205], b[205][205];
int sp[205], sus[205], st[205], l[205], r[205];

int solve1(int h[], int m) {
  int top = 0;
  st[top] = 0;
  for (int j = 1; j <= m; ++j) {
    while (top > 0 && h[j] <= h[st[top]])
      top--;
    l[j] = st[top];
    st[++top] = j;
  }
  top = 0;
  st[top] = m + 1;
  for (int j = m; j >= 1; --j) {
    while (top > 0 && h[j] <= h[st[top]])
      top--;
    r[j] = st[top];
    st[++top] = j;
  }
  int ans = 0;
  for (int j = 1; j <= m; ++j)
    ans = max(ans, sp[j] * (r[j] - l[j] - 1));
  return ans;
}

int solve(int x[205][205], int n, int m) {
  for (int j = 1; j <= m; ++j)
    sp[j] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j)
      if (x[i][j] == 0)
        sp[j]++;
      else
        sp[j] = 0;
    sus[i] = max(sus[i - 1], solve1(sp, m));
  }
  int ans = 0;
  for (int j = 1; j <= m; ++j)
    sp[j] = 0;
  int aux = 0;
  for (int i = n; i >= 1; --i) {
    for (int j = 1; j <= m; ++j)
      if (x[i][j] == 0)
        sp[j]++;
      else
        sp[j] = 0;
    aux = max(aux, solve1(sp, m));
    ans = max(ans, aux + sus[i - 1]);
  }
  return ans;
}

int main() {
  freopen("bmatrix.in", "r", stdin);
  freopen("bmatrix.out", "w", stdout);

  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      scanf("%1d", &a[i][j]);
      b[m - j + 1][i] = a[i][j];
    }

  printf("%d\n", max(solve(a, n, m), solve(b, m, n)));

  return 0;
}