Submission #1134335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134335		stdfloat	Bomb (IZhO17_bomb)	C++20	100 / 100	116 ms	56296 KiB

bomb

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define all(v)	(v).begin(), (v).end()

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

	int n, m;
	cin >> n >> m;

	vector<string> a(n);
	for (auto &i : a)
		cin >> i;

	int w = INT_MAX;
	for (int i = 0; i < n; i++) {
		int cnt = 0;
		for (int j = 0; j <= m; j++) {
			if (j == m || a[i][j] == '0') {
				if (cnt) w = min(w, cnt);
				cnt = 0;
			}
			else cnt++;
		}
	}

	if (w == INT_MAX) return cout << 0, 0;

	int h = INT_MAX;
	for (int i = 0; i < m; i++) {
		int cnt = 0;
		for (int j = 0; j <= n; j++) {
			if (j == n || a[j][i] == '0') {
				if (cnt) h = min(h, cnt);
				cnt = 0;
			}
			else cnt++;
		}
	}

	vector<int> ans(m, h);
	for (int z = 0; z < 2; z++) {
		vector<vector<int>> u(n, vector<int>(m)), d = u;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++)
				u[i][j] = (a[i][j] == '0' ? 0 : (i ? u[i - 1][j] + 1 : 1));
		}
		for (int i = n - 1; i >= 0; i--) {
			for (int j = 0; j < m; j++)
				d[i][j] = (a[i][j] == '0' ? 0 : (i + 1 != n ? d[i + 1][j] + 1 : 1));
		}

		for (int i = 0; i < n; i++) {
			int l = -1, mn1 = INT_MAX, mn2 = mn1;
			for (int j = 0; j < m; j++) {
				if (a[i][j] == '0') {
					l = -1;
					mn1 = mn2 = INT_MAX;
					continue;
				}
			
				if (!~l) l = j;

				mn1 = min(mn1, u[i][j]);
				mn2 = min(mn2, d[i][j]);
			
				ans[j - l] = min(ans[j - l], mn1 + mn2 - 1);
			}
		}

		for (auto &i : a)
			reverse(all(i));
	}


	int mx = 0;
	for (int i = 0; i < w; i++)
		mx = max(mx, (i + 1) * ans[i]);

	cout << mx;
}

• Subtask 1: 100 / 100