답안 #573890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
573890	2022-06-07T11:28:50 Z	vovamr	Bomb (IZhO17_bomb)	C++17	86 / 100	624 ms	75736 KB

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 (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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1 ms	468 KB	Execution killed with signal 6
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	724 KB	Output is correct
4	Correct	1 ms	724 KB	Output is correct
5	Runtime error	1 ms	468 KB	Execution killed with signal 11
6	Runtime error	1 ms	468 KB	Execution killed with signal 11
7	Incorrect	1 ms	212 KB	Output isn't correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	216 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	1 ms	328 KB	Output is correct
19	Correct	1 ms	328 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	324 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Incorrect	1 ms	464 KB	Output isn't correct
27	Incorrect	4 ms	1364 KB	Output isn't correct
28	Correct	4 ms	1748 KB	Output is correct
29	Correct	6 ms	1892 KB	Output is correct
30	Correct	8 ms	2708 KB	Output is correct
31	Correct	6 ms	2260 KB	Output is correct
32	Correct	6 ms	2284 KB	Output is correct
33	Correct	11 ms	2880 KB	Output is correct
34	Correct	3 ms	1416 KB	Output is correct
35	Correct	8 ms	2900 KB	Output is correct
36	Incorrect	9 ms	2900 KB	Output isn't correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	504 ms	75588 KB	Output is correct
39	Correct	1 ms	212 KB	Output is correct
40	Runtime error	55 ms	19736 KB	Execution killed with signal 11
41	Correct	1 ms	212 KB	Output is correct
42	Correct	1 ms	340 KB	Output is correct
43	Correct	529 ms	75636 KB	Output is correct
44	Correct	10 ms	2952 KB	Output is correct
45	Correct	530 ms	75736 KB	Output is correct
46	Correct	530 ms	75524 KB	Output is correct
47	Correct	554 ms	75536 KB	Output is correct
48	Correct	569 ms	75584 KB	Output is correct
49	Incorrect	559 ms	75536 KB	Output isn't correct
50	Correct	617 ms	75560 KB	Output is correct
51	Correct	578 ms	75540 KB	Output is correct
52	Correct	568 ms	75536 KB	Output is correct
53	Correct	553 ms	75632 KB	Output is correct
54	Correct	550 ms	75548 KB	Output is correct
55	Correct	565 ms	75544 KB	Output is correct
56	Correct	576 ms	75576 KB	Output is correct
57	Correct	546 ms	75540 KB	Output is correct
58	Correct	576 ms	75448 KB	Output is correct
59	Correct	571 ms	75528 KB	Output is correct
60	Incorrect	553 ms	75544 KB	Output isn't correct
61	Incorrect	591 ms	75560 KB	Output isn't correct
62	Incorrect	600 ms	75596 KB	Output isn't correct
63	Incorrect	581 ms	75540 KB	Output isn't correct
64	Incorrect	594 ms	75476 KB	Output isn't correct
65	Correct	604 ms	75436 KB	Output is correct
66	Correct	603 ms	75412 KB	Output is correct
67	Correct	580 ms	75412 KB	Output is correct
68	Correct	583 ms	75484 KB	Output is correct
69	Correct	577 ms	75472 KB	Output is correct
70	Correct	341 ms	48992 KB	Output is correct
71	Correct	566 ms	75524 KB	Output is correct
72	Correct	576 ms	75516 KB	Output is correct
73	Correct	579 ms	75468 KB	Output is correct
74	Correct	569 ms	75408 KB	Output is correct
75	Correct	577 ms	75416 KB	Output is correct
76	Correct	572 ms	75448 KB	Output is correct
77	Correct	587 ms	75412 KB	Output is correct
78	Correct	585 ms	75448 KB	Output is correct
79	Correct	593 ms	75456 KB	Output is correct
80	Correct	588 ms	75420 KB	Output is correct
81	Correct	588 ms	75440 KB	Output is correct
82	Correct	591 ms	75460 KB	Output is correct
83	Correct	613 ms	75444 KB	Output is correct
84	Correct	594 ms	75428 KB	Output is correct
85	Correct	601 ms	75412 KB	Output is correct
86	Correct	624 ms	75428 KB	Output is correct
87	Correct	586 ms	75572 KB	Output is correct
88	Correct	565 ms	75448 KB	Output is correct
89	Correct	589 ms	75420 KB	Output is correct
90	Correct	368 ms	48940 KB	Output is correct
91	Correct	596 ms	75436 KB	Output is correct
92	Correct	579 ms	75464 KB	Output is correct
93	Correct	613 ms	75272 KB	Output is correct
94	Correct	601 ms	75320 KB	Output is correct
95	Correct	586 ms	75268 KB	Output is correct
96	Correct	582 ms	75356 KB	Output is correct
97	Correct	597 ms	75328 KB	Output is correct
98	Correct	591 ms	75336 KB	Output is correct
99	Correct	584 ms	75200 KB	Output is correct
100	Correct	588 ms	75304 KB	Output is correct