Submission #1291204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291204		LIA	Bomb (IZhO17_bomb)	C++17	90 / 100	240 ms	74160 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));
  loop(i, 0, n) {
    string s;
    cin >> s;
    loop(j, 0, m) { grid[i][j] = (s[j] - '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 = 1e18, min_down = 1e18, k = j;
      while (k < m && grid[i][k]) {
        min_up = min(min_up, up[i][k]);
        min_down = min(min_down, dn[i][k]);
        ll w = k - L + 1;
        ans[w] = min(ans[w], min_up + min_down - 1);
        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 = 1e18, min_down = 1e18, k = j;
      while (k >= 0 && grid[i][k]) {
        min_up = min(min_up, up[i][k]);
        min_down = min(min_down, dn[i][k]);
        ll w = R + 1 - k;
        ans[w] = min(ans[w], min_up + min_down - 1);
        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;
}

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:47:26: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   47 |       ll L = j, min_up = 1e18, min_down = 1e18, k = j;
      |                          ^~~~
bomb.cpp:47:43: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   47 |       ll L = j, min_up = 1e18, min_down = 1e18, k = j;
      |                                           ^~~~
bomb.cpp:67:26: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   67 |       ll R = j, min_up = 1e18, min_down = 1e18, k = j;
      |                          ^~~~
bomb.cpp:67:43: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   67 |       ll R = j, min_up = 1e18, min_down = 1e18, k = j;
      |                                           ^~~~

• Subtask 1: 90 / 100