Submission #1291205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291205		LIA	Bomb (IZhO17_bomb)	C++17	90 / 100	226 ms	74168 KiB

bomb

//
// Created by liasa on 15/11/2025.
//
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define vll vector<ll>

#define loop(i, s, e) for (ll i = s; i < e; ++i)

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ll n, m;
  cin >> n >> m;
  vector<vll> grid(n, vll(m));
  bool cnt = 0;
  loop(i, 0, n) {
    string s;
    cin >> s;
    loop(j, 0, m) {
      grid[i][j] = (s[j] - '0');
      if (grid[i][j])
        cnt = 1;
    }
  }
  if (!cnt) {
    cout << 0;
    return 0;
  }

  vector<vll> up(n, vll(m)), dn(n, vll(m));
  loop(j, 0, m) {
    loop(i, 0, n) {
      if (grid[i][j])
        up[i][j] = (i ? up[i - 1][j] : 0) + 1;
      else
        up[i][j] = 0;
    }
    for (ll i = n - 1; i >= 0; --i) {
      if (grid[i][j])
        dn[i][j] = (i + 1 < n ? dn[i + 1][j] : 0) + 1;
      else
        dn[i][j] = 0;
    }
  }
  vll ans(m + 1, n);
  loop(i, 0, n) {
    for (ll j = 0; j < m;) {
      if (!grid[i][j]) {
        j++;
        continue;
      }
      ll L = j, min_up = -1e9, min_down = 1e9, k = j;
      while (k < m && grid[i][k]) {
        min_up = max(min_up, i - up[i][k] + 1);
        min_down = min(min_down, i + dn[i][k] - 1);
        ll w = k - L + 1;
        ll cap = min_down - min_up + 1;
        if (cap < 0)
          cap = 0;
        ans[w] = min(ans[w], cap);
        k++;
      }
      ll len = k - L;
      if (len + 1 <= m)
        ans[len + 1] = 0;
      j = k;
    }
  }
  loop(i, 0, n) {
    for (ll j = m - 1; j >= 0;) {
      if (!grid[i][j]) {
        j--;
        continue;
      }
      ll R = j, min_up = -1e9, min_down = 1e9, k = j;
      while (k >= 0 && grid[i][k]) {
        min_up = max(min_up, i - up[i][k] + 1);
        min_down = min(min_down, i + dn[i][k] - 1);
        ll w = R + 1 - k;
        ll B = min_down - min_up + 1;
        if (B < 0)
          B = 0;
        ans[w] = min(ans[w], B);
        k--;
      }
      ll len = R - k;
      if (len + 1 <= m)
        ans[len + 1] = 0;
      j = k;
    }
  }

  for (ll w = 1; w <= m; ++w)
    ans[w] = min(ans[w], ans[w - 1]);

  ll res = 0;
  for (ll w = 1; w <= m; ++w)
    res = max(res, w * ans[w]);
  cout << res;
}

• Subtask 1: 90 / 100