Cod sursa(job #2990647)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 8 martie 2023 11:48:52
Problema BMatrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <bits/stdc++.h>

using namespace std;

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

const int kN = 200;
string a[1 + kN];
int v[1 + kN], stk[1 + kN], nextLeft[1 + kN], nextRight[1 + kN], up[1 + kN], down[1 + kN + 1], st[1 + kN], dr[1 + kN + 1];

void maxSelf(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

int solve(int n) {
  for (int i = 1; i <= n; ++i) {
    nextLeft[i] = 0;
    nextRight[i] = n + 1;
  }

  int vf = 0;

  for (int i = 1; i <= n; ++i) {
    while (vf && v[i] < v[stk[vf]]) {
      nextRight[stk[vf]] = i;
      vf -= 1;
    }

    stk[++vf] = i;
  }

  vf = 0;

  for (int i = n; i > 0; --i) {
    while (vf && v[i] < v[stk[vf]]) {
      nextLeft[stk[vf]] = i;
      vf -= 1;
    }

    stk[++vf] = i;
  }

  int best = 0;

  for (int i = 1; i <= n; ++i) {
    maxSelf(best, v[i] * (nextRight[i] - nextLeft[i] - 1));
  }

  return best;
}

int main() {
  int n, m;
  fin >> n >> m;

  for (int i = 1; i <= n; ++i) {
    fin >> a[i];
    a[i] = '$' + a[i];
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (a[i][j] == '0') {
        v[j] += 1;
      } else {
        v[j] = 0;
      }
    }

    up[i] = max(up[i - 1], solve(m));
  }

  for (int i = 1; i <= m; ++i) {
    v[i] = 0;
  }

  for (int i = n; i > 0; --i) {
    for (int j = 1; j <= m; ++j) {
      if (a[i][j] == '0') {
        v[j] += 1;
      } else {
        v[j] = 0;
      }
    }

    down[i] = max(down[i + 1], solve(m));
  }

  for (int i = 1; i <= n; ++i) {
    v[i] = 0;
  }

  for (int j = 1; j <= m; ++j) {
    for (int i = 1; i <= n; ++i) {
      if (a[i][j] == '0') {
        v[i] += 1;
      } else {
        v[i] = 0;
      }
    }

    st[j] = max(st[j - 1], solve(n));
  }

  for (int i = 1; i <= n; ++i) {
    v[i] = 0;
  }

  for (int j = m; j > 0; --j) {
    for (int i = 1; i <= n; ++i) {
      if (a[i][j] == '0') {
        v[i] += 1;
      } else {
        v[i] = 0;
      }
    }

    dr[j] = max(dr[j + 1], solve(n));
  }

  int best = 0;

  for (int i = 0; i <= n; ++i) {
    maxSelf(best, up[i] + down[i + 1]);
  }

  for (int i = 0; i <= m; ++i) {
    maxSelf(best, st[i] + dr[i + 1]);
  }

  fout << best << '\n';

  fin.close();
  fout.close();

  return 0;
}