Submission #524022

#	Time	Username	Problem	Language	Result	Execution time	Memory
524022		boykut	Bomb (IZhO17_bomb)	C++14	27 / 100	1105 ms	55408 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;
	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 ans = 0, Q = 2;
	for (int a = 1; a <= n; a++) {
		for (int b = 1; b <= m; b++) {
			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;
				}
			}
			if (ok) {
				ans = max(ans, a * b);
			}
			Q++;
		}
	}
	cout << ans << '\n';

	return 0;
}

• Subtask 1: 27 / 100