Submission #404582

#	Time	Username	Problem	Language	Result	Execution time	Memory
404582		rama_pang	Bomb (IZhO17_bomb)	C++17	90 / 100	479 ms	80068 KiB

bomb

#include <bits/stdc++.h>
using namespace std;

int N, M;
int A[2505][2505];

int up[2505][2505];
int dn[2505][2505];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N >> M;

  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      char c;
      cin >> c;
      A[i][j] = c - '0';
    }
  }

  // Solution:
  //
  // The upper bound on height and width is the minimum length
  // vertical and horizontal strip. Now, for a fixed width Y,
  // we want to determine the maximum height X. Note that,
  // if we have width Y, then for every maximal horizontal
  // strip, height is bounded by the minimum (top - bottom)
  // of the prefix and suffix of size Y.
  //
  // We only need to consider the prefix and suffix. Why?
  // For, after a prefix of size Y, let's move it to the right.
  // If the (top - bottom) decreased, that means that there is
  // a vertical strip which is shifted downwards, which means
  // it will occcupy a maximal horizontal strip -> we will compute
  // it later.
  //
  // Time complexity: O(N M).

  for (int j = 1; j <= M; j++) {
    for (int i = 1; i <= N; i++) {
      if (A[i][j]) {
        up[i][j] = 1 + up[i - 1][j];
      }
    }
    for (int i = N; i >= 1; i--) {
      if (A[i][j]) {
        dn[i][j] = 1 + dn[i + 1][j];
      }
    }
  }

  vector<int> ans(M + 2, 1e9);
  for (int rep = 0; rep < 2; rep++) { // for prefix, then suffix
    for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= M; j++) if (A[i][j]) {
        int jj = j;
        while (jj + 1 <= M && A[i][jj]) jj += 1;

        int len = jj - j + 1;
        int minUp = 1e9;
        int minDn = 1e9;
        for (int k = 1; k <= len; k++) {
          minUp = min(minUp, up[i][j + k - 1]);
          minDn = min(minDn, dn[i][j + k - 1]);
          ans[k] = min(ans[k], minUp + minDn - 1);
        }

        ans[0] = min(ans[0], up[i][j] + dn[i][j] - 1);
        ans[len + 1] = 0;
        j = jj;
      }
    }
    for (int i = 1; i <= N; i++) {
      for (int j = 1; 2 * j <= M; j++) {
        swap(A[i][j], A[i][M - j + 1]);
        swap(up[i][j], up[i][M - j + 1]);
        swap(dn[i][j], dn[i][M - j + 1]);
      }
    }
  }

  int answer = 0;
  for (int i = 1; i <= M; i++) {
    ans[i] = min(ans[i], ans[i - 1]);
    answer = max(answer, i * ans[i]);
  }

  cout << answer << '\n';
  return 0;
}

• Subtask 1: 90 / 100