Submission #1258580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258580		TAhmed33	Bomb (IZhO17_bomb)	C++20	30 / 100	1103 ms	196608 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);
			for (auto [l, r, x] : intervals) {
				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
	int mx = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			vector <vector <int>> marked(n + 2, vector <int> (m + 2, 0));
			for (auto [l, r, a, b] : rectangles) {
				if (r - l + 1 < i || b - a + 1 < j) {
					continue;
				}
				marked[l][a]++;
				marked[l][b + 1]--;
				marked[r + 1][a]--;
				marked[r + 1][b + 1]++;
			}
			for (int x = 1; x <= n; x++) {
				for (int y = 1; y <= m; y++) {
					marked[x][y] += marked[x - 1][y] + marked[x][y - 1] - marked[x - 1][y - 1];
				}
			}
			bool flag = 1;
			for (int x = 1; x <= n; x++) {
				for (int y = 1; y <= m; y++) {
					if (a[x][y] == '1') {
						flag &= marked[x][y] != 0;
					}
				}
			}
			if (flag) {
				mx = max(mx, i * j);
			}
		}
	}
	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: 30 / 100