Submission #524041

#	Time	Username	Problem	Language	Result	Execution time	Memory
524041		boykut	Bomb (IZhO17_bomb)	C++14	31 / 100	1107 ms	52764 KiB

bomb

#include <bits/stdc++.h>

using namespace std;

const int N = 2500;
int arr[N][N];
int pref[N][N];

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

	int n, m;
	cin >> n >> m;
	//if (n * n * n * m * m * m > 1e8) return 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char x; cin >> x;
			arr[i][j] = x - '0';
			pref[i][j] = x - '0';
			pref[i][j] += (i ? pref[i - 1][j] : 0);
			pref[i][j] += (j ? pref[i][j - 1] : 0);
			pref[i][j] -= (i && j ? pref[i - 1][j - 1] : 0);
		}
	}

	auto get = [&](int a, int b, int c, int d) ->int {
		int s = pref[c][d];
		s -= (a ? pref[a - 1][d] : 0);
		s -= (b ? pref[c][b - 1] : 0);
		s += (a && b ? pref[a - 1][b - 1] : 0);
		return s;
	};

	// brute force

	int Q = 2;
	auto check = [&](int a, int b) ->int {
		for (int i = 0; i + a - 1 < n; i++) {
			for (int j = 0; j + b - 1 < m; j++) {
				int g = get(i, j, i + a - 1, j + b - 1);
				if (g == a * b) {
					for (int i2 = i; i2 <= i + a - 1; i2++) {
						for (int j2 = j; j2 <= j + b - 1; j2++)
							arr[i2][j2] = Q;
					}
				}
			}
		}
		int ok = 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] != 0 && arr[i][j] != Q) ok = 0;
			}
		}
		Q++;
		return ok;
	};

	int ans = 0;
	for (int a = 1; a <= n; a++) {
		int l = 1, r = m;
		while (l < r) {
			int b = (l + r + 1) / 2;
			if (check(a, b))
				l = b;
			else
				r = b - 1;
		}
		if (check(a, l))
			ans = max(ans, a * l);
		// for (int b = l; b <= r; b++) {
		// 	if (check(a, b)) {
		// 		ans = max(ans, a * b);
		// 	}
		// }
	}
	cout << ans << '\n';

	return 0;
}

• Subtask 1: 31 / 100