Submission #1258386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258386		TAhmed33	Bomb (IZhO17_bomb)	C++20	0 / 100	1093 ms	196608 KiB

bomb

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
0011
0011
1110
1100
*/
void solve (int X) {
	int n, m; cin >> n >> m;
	vector <vector <char>> a(n + 1, vector <char> (m + 1));
	vector <vector <int>> up(n + 1, vector <int> (m + 1, 0));
	vector <vector <int>> down(n + 2, vector <int> (m + 1, 0));
	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++) {
			up[i][j] = (a[i][j] == '0' ? 0 : 1 + up[i - 1][j]);
		}
	}
	for (int i = n; i >= 1; i--) {
		for (int j = 1; j <= m; j++) {
			down[i][j] = (a[i][j] == '0' ? 0 : 1 + down[i + 1][j]);
		}
	}
	int dx = n, dy = m;
	for (int i = 1; i <= n; i++) {
		int cnt = 0;
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == '1') {
				cnt++;
			} else if (cnt > 0) {
				dy = min(dy, cnt);
				cnt = 0;
			}
		}
		if (cnt > 0) {
			dy = min(dy, cnt);
			cnt = 0;
		}
	}
	for (int j = 1; j <= m; j++) {
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i][j] == '1') {
				cnt++;
			} else if (cnt > 0) {
				dx = min(dx, cnt);
				cnt = 0;
			}
		}
		if (cnt > 0) {
			dx = min(dx, cnt);
			cnt = 0;
		}
	}
	vector <int> ee(dx + 1, dy);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == '0') {
				continue;
			}
			int cur = dx;
			for (int k = j; k >= 1; k--) {
				if (a[i][k] == '0') {
					break;
				}
				cur = min(cur, down[i][k] + up[i][k] - 1);
				int p = j;
				while (p + 1 <= m && down[i][p + 1] + up[i][p + 1] - 1 >= cur) {
					p++;
				}
				while (k - 1 >= 1 && down[i][k - 1] + up[i][k - 1] - 1 >= cur) {
					k--;
				}
				ee[cur] = min(ee[cur], p - k + 1);
				//cout << i << " " << j << " " << p << " " << k << ": " << cur << " " << p - k + 1 << '\n';
			}
		}
	}
	int mx = 0;
	for (int i = 1; i <= dx; i++) {
		//cout << i << ": " << ee[i] << '\n';
		mx = max(mx, i * ee[i]);
	}
	cout << mx << '\n';
}	
signed main () {
	#ifndef ONLINE_JUDGE 
		//freopen("input_file", "r", stdin);
		//freopen("output_file", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; cin >> tc;
	for (int i = 1; i <= tc; i++) solve(i);
}

• Subtask 1: 0 / 100