Submission #1258654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258654		TAhmed33	Bomb (IZhO17_bomb)	C++20	42 / 100	1101 ms	124296 KiB

bomb

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*
0011
0011
1110
1100
*/
vector <array <int, 3>> get (vector <int> c) {
	int n = c.size() - 1;
	vector <int> nxt(n + 1, n + 1), prv(n + 1, 0);
	vector <int> cur;
	for (int i = 1; i <= n; i++) {
		while (!cur.empty() && c[cur.back()] >= c[i]) {
			nxt[cur.back()] = i;
			cur.pop_back();
		}
		cur.push_back(i);
	}
	cur.clear();
	for (int i = n; i >= 1; i--) {
		while (!cur.empty() && c[cur.back()] > c[i]) {
			prv[cur.back()] = i;
			cur.pop_back();
		}
		cur.push_back(i);
	}
	vector <array <int, 3>> ret;
	for (int i = 1; i <= n; i++) {
		ret.push_back({prv[i] + 1, nxt[i] - 1, c[i]});
	}
	return ret;
}
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]);
		}
	}
	int mn = n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			f[i][j] = up[i][j] + down[i][j] - 1;
			if (a[i][j] == '1') {
				mn = min(mn, f[i][j]);
			}
		}
	}
	vector <array <int, 4>> rectangles;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i][j] == '0') {
				continue;
			}
			int k = j;
			while (k + 1 <= m && a[i][k + 1] == '1') {
				k++;
			}
			vector <int> c = {0};
			for (int l = j; l <= k; l++) {
				c.push_back(down[i][l]);
			}
			auto intervals = get(c);
			vector <int> pref = {0};
			for (int l = j; l <= k; l++) {
				pref.push_back(pref.back() + (up[i][l] == 1));
			}
			for (auto [l, r, x] : intervals) {
				if (pref[r] - pref[l - 1] == 0) {
					continue;
				}
				rectangles.push_back({i, i + x - 1, j - 1 + l, j - 1 + r});
			}
			j = k;
		}
	}	
/*	for (auto [l, r, a, b] : rectangles) {
		cout << l << " " << r << " " << a << " " << b << '\n';
	}*/
	//Choose (x, y) such that every 1 cell is covered by a rectangle with dx >= x and dy >= y
	//Iterate over rectangles in decreasing order of dx and maintain for each cell the maximum dy for it
	//Then you want minimum value for all cells
	//You want to do this update quickly for the rectangle
	//It is just a range set operation
	int ans = 0;
	vector <vector <int>> mx(n + 2, vector <int> (m + 2, 0));
	vector <int> nxt(n + 1, m);
	for (int j = 1; j <= m; j++) {
		vector <array <int, 3>> ee[n + 1];
		for (auto [l, r, a, b] : rectangles) {
			if (a <= j && j <= b) {
				ee[r - l + 1].push_back({l, r, b - a + 1});
			}
		}
		vector <int> cur(n + 1, 0);
		for (int x = n; x >= 1; x--) {
			for (auto [l, r, k] : ee[x]) {
				for (int i = l; i <= r; i++) {
					cur[i] = k;
				}
			}
			int mn = m;
			for (int i = 1; i <= n; i++) {
				if (a[i][j] == '1') {
					mn = min(mn, cur[i]);
				}
			}
			nxt[x] = min(nxt[x], mn);
		}
	}
	for (int i = 2; i <= n; i++) {
		nxt[i] = min(nxt[i - 1], nxt[i]);
	}
	for (int i = n; i >= 1; i--) {
		ans = max(ans, i * nxt[i]);
	}
	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: 42 / 100