Submission #404483

#	Time	Username	Problem	Language	Result	Execution time	Memory
404483		rama_pang	Bomb (IZhO17_bomb)	C++17	24 / 100	349 ms	129308 KiB

bomb

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

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

  int N, M;
  cin >> N >> M;

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

  const auto Solve = [&](const vector<vector<int>> &A) {
    vector<vector<int>> H, V;
    H.assign(N, vector<int>(M, 0));
    V.assign(N, vector<int>(M, 0));

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) if (A[i][j] == 1) {
        int jj = j;
        while (jj + 1 < M && A[i][jj + 1] == 1) jj += 1;
        for (int k = j; k <= jj; k++) {
          H[i][k] = jj - j + 1;
        }
        j = jj;
      }
    }

    for (int j = 0; j < M; j++) {
      for (int i = 0; i < N; i++) if (A[i][j] == 1) {
        int ii = i;
        while (ii + 1 < N && A[ii + 1][j] == 1) ii += 1;
        for (int k = i; k <= ii; k++) {
          V[k][j] = ii - i + 1;
        }
        i = ii;
      }
    }

    return pair(H, V);
  };

  auto [H, V] = Solve(A);

  int ansN = N;
  int ansM = M;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) if (A[i][j] != 0) {
      ansN = min(ansN, V[i][j]);
      ansM = min(ansM, H[i][j]);
    }
  }

  cout << ansN * ansM << '\n';
  return 0;
}

• Subtask 1: 24 / 100