Submission #573891

#	Time	Username	Problem	Language	Result	Execution time	Memory
573891		vovamr	Bomb (IZhO17_bomb)	C++17	86 / 100	628 ms	74776 KiB

bomb

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

inline void solve() {
	int n, m;
	cin >> n >> m;
	ve<ve<int>> a(n, ve<int>(m));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			char x;
			cin >> x;
			a[i][j] = x - '0';
		}
	}

	ve<int> mx(n + 2, iinf);
	for (int rep = 0; rep < 2; ++rep) {
		ve<ve<int>> dp1(n, ve<int> (m)), dp2(n, ve<int> (m));
		for (int j = 0; j < m; ++j) {
			for (int i = 0; i < n; ++i) {
				dp1[i][j] = a[i][j];
				if (i && a[i - 1][j] && a[i][j]) dp1[i][j] += dp1[i - 1][j];
			}
			for (int i = n - 1; ~i; --i) {
				dp2[i][j] = a[i][j];
				if (i + 1 < n && a[i + 1][j] && a[i][j]) dp2[i][j] += dp2[i + 1][j];
			}
		}

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ) {
				if (!a[i][j]) { ++j; continue; }

				int p = j;
				while (j < m && a[i][p]) ++p;

				int a = iinf, b = iinf;
				for (int k = j; k < p; ++k) {
					chmin(a, dp1[i][k]);
					chmin(b, dp2[i][k]);
					chmin(mx[k - j + 1], a + b - 1);
				}
				chmin(mx[p - j + 1], 0);

				j = p;
			}
		}

		for (int i = 0; i < n; ++i) reverse(all(a[i]));
	}

	ll ans = 0;
	for (int i = 1; i <= n; ++i) {
		chmin(mx[i], mx[i - 1]);
		chmax(ans, i * 1ll * mx[i]);
	}
	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

• Subtask 1: 86 / 100