Submission #1230784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230784		Matthewwww	Bomb (IZhO17_bomb)	C++17	45 / 100	1095 ms	49576 KiB

bomb

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m;
	cin >> n >> m;
	vector<vector<int>> grid;
	if (n < m) {
		grid.resize(n, vector<int>(m));	
		for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			grid[i][j] = c == '0';
		}
	} else {
		grid.resize(m, vector<int>(n));
		for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			grid[j][i] = c == '0';
		}
		swap(n, m);
	}
	vector<vector<int>> psum(n+1, vector<int>(m+1, 0));
	for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) psum[i+1][j+1] = grid[i][j];
	for (int i = 0; i < n; i++) for (int j = 0; j <= m; j++) psum[i+1][j] += psum[i][j];
	for (int i = 0; i <= n; i++) for (int j = 0; j < m; j++) psum[i][j+1] += psum[i][j];
	int upt = 31-__builtin_clz(m);
	// proof by ac doesn't work :(
	if (n <= 450) {
		int ans = 0;
		for (int x = 1; x <= n; x++) {
			int y = 0;
			for (int l = upt; l--;) {
				int k = y+(1<<l);
				vector<vector<int>> psa(n+1, vector<int>(m+1, 0));
				for (int i = 0; i <= n-x; i++) {
					for (int j = 0; j <= m-k; j++) {
						if (psum[i+x][j+k]-psum[i+x][j]-psum[i][j+k]+psum[i][j] == 0) {
							psa[i+x][j+k]++;
							psa[i+x][j]--;
							psa[i][j+k]--;
							psa[i][j]++;
						}
					}
				}
				for (int i = 0; i < n; i++) for (int j = 0; j <= m; j++) psa[i+1][j] += psa[i][j];
				for (int i = 0; i <= n; i++) for (int j = 0; j < m; j++) psa[i][j+1] += psa[i][j];
				bool good = true;
				for (int i = 0; i < n && good; i++) for (int j = 0; j < m && good; j++) good = (!psa[i][j]) == grid[i][j];
				if (good) y += 1<<l;
			}
			ans = max(ans, x*y);
			err << x << " " << y << "\n";
		}
		cout << ans << "\n";
		return 0;
	}
	// lets try proof by ac!
	int mx = n, my = m;
	for (int i = 0; i < n; i++) {
		vector<pair<int, int>> ran;
		for (int j = 0; j < m; j++) {
			if (grid[i][j]) continue;
			if (!ran.size() || ran.back().s != j)
				ran.push_back({j, j+1});
			else
				ran.back().s++;
		}
		for (auto j: ran) my = min(my, j.s-j.f);
	}
	for (int i = 0; i < m; i++) {
		vector<pair<int, int>> ran;
		for (int j = 0; j < n; j++) {
			if (grid[j][i]) continue;
			if (!ran.size() || ran.back().s != j)
				ran.push_back({j, j+1});
			else
				ran.back().s++;
		}
		for (auto j: ran) mx = min(mx, j.s-j.f);
	}
	cout << mx*my << "\n";
}

• Subtask 1: 45 / 100