Submission #711555

#	Time	Username	Problem	Language	Result	Execution time	Memory
711555		pavement	Bomb (IZhO17_bomb)	C++17	100 / 100	215 ms	104748 KiB

bomb

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, M, ans[2505], top[2505][2505], down[2505][2505];
char A[2505][2505];

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		ans[i] = (int)1e16;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> A[i][j];
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (A[i][j] == '1') {
				top[i][j] = (top[i - 1][j] ? top[i - 1][j] : i);
			}
		}
	}
	for (int i = N; i >= 1; i--) {
		for (int j = 1; j <= M; j++) {
			if (A[i][j] == '1') {
				down[i][j] = (down[i + 1][j] ? down[i + 1][j] : i);
				ans[1] = min(ans[1], down[i][j] - top[i][j] + 1);
			}
		}
	}
	for (int iter = 0; iter < 2; iter++) {
		for (int i = 1; i <= N; i++) {
			for (int l = 1, r = 1; l <= M; ) {
				while (r <= M && A[i][r] == '1') r++;
				if (l == r) {
					l++;
					r++;
					continue;
				}
				ans[r - l + 1] = 0;
				int min_top = (int)1e16, min_down = (int)1e16;
				for (int j = l; j < r; j++) {
					assert(A[i][j] == '1');
					min_top = min(min_top, i - top[i][j] + 1);
					min_down = min(min_down, down[i][j] - i + 1);
					ans[j - l + 1] = min(ans[j - l + 1], min_top + min_down - 1);
				}
				l = r;
			}
		}
		for (int i = 1; i <= N; i++) {
			reverse(A[i] + 1, A[i] + 1 + M);
			reverse(top[i] + 1, top[i] + 1 + M);
			reverse(down[i] + 1, down[i] + 1 + M);
		}
	}
	int ret = 0;
	for (int i = 1; i <= M; i++) {
		if (i > 1) ans[i] = min(ans[i], ans[i - 1]);
		assert(ans[i] != (int)1e16);
		ret = max(ret, i * ans[i]);
	}
	cout << ret << '\n';
}

Compilation message (stderr)

bomb.cpp:29:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   29 | main() {
      | ^~~~

• Subtask 1: 100 / 100