Submission #1258400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258400		TAhmed33	Bomb (IZhO17_bomb)	C++20	7 / 100	1100 ms	104976 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));
	vector <vector <int>> f(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]);
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			f[i][j] = up[i][j] + down[i][j] - 1;
		}
	}
	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;
		}
	}
	int ans = 0;
	for (int c = 1; c <= dx; c++) {
		vector <vector <int>> marked(n + 1, vector <int> (m + 1, 0));
		int mn = dy;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (a[i][j] == '0') {
					continue;
				}
				if (marked[i][j]) {
					continue;
				}
				int k = j;
				while (k + 1 <= m && down[i][k + 1] >= c) {
					k++;
				}
				mn = min(mn, k - j + 1);
				for (int l = j; l <= k; l++) {
					for (int m = i; m <= i + c - 1; m++) {
						marked[m][l] = 1;
					}
				}
			}
		}
		ans = max(ans, c * mn);
	}
	cout << ans << '\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: 7 / 100