# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
495928 | 2021-12-20T08:07:34 Z | ntabc05101 | Bali Sculptures (APIO15_sculpture) | C++14 | 12 ms | 368 KB |
#include<bits/stdc++.h> using namespace std; #define taskname "" const int lgN = 41; int main() { if (fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } else { if (fopen(taskname".in", "r")) { freopen(taskname".in", "r", stdin); freopen(taskname".out", "w", stdout); } } cin.tie(0)->sync_with_stdio(0); int n, a, b; cin >> n >> a >> b; long long y[n + 1]; y[0] = 0; for (int i = 1; i <= n; i++) { cin >> y[i]; y[i] += y[i - 1]; } long long res = 0; if (n > 100) { pair<bool, int> dp[n + 1]; for (int x = lgN - 1; ~x; x--) { dp[0] = {1, 0}; for (int i = 1; i <= n; i++) { dp[i] = {0, 0}; for (int j = i - 1; ~j; j--) { if ((res >> x) == (((y[i] - y[j]) | res) >> x)) { dp[i] = max(dp[i], dp[j]); } } dp[i].second--; } if (!dp[n].first || -dp[n].second > b) { res |= 1 << x; } } cout << res << "\n"; } else { bool dp[n + 1][n + 1]; for (int x = lgN - 1; ~x; x--) { memset(dp, 0, sizeof(dp)); dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int k = i - 1; ~k; k--) { if ((res >> x) == (((y[i] - y[k]) | res) >> x)) { for (int j = 1; j <= i; j++) { dp[i][j] |= dp[k][j - 1]; } } } } int chk = 1; for (int j = a; j <= b; j++) { if (dp[n][j]) { chk = 0; break; } } res |= chk << x; } cout << res << "\n"; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 0 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 316 KB | Output is correct |
6 | Correct | 1 ms | 320 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 1 ms | 316 KB | Output is correct |
9 | Correct | 1 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 216 KB | Output is correct |
11 | Correct | 1 ms | 216 KB | Output is correct |
12 | Correct | 1 ms | 328 KB | Output is correct |
13 | Correct | 1 ms | 204 KB | Output is correct |
14 | Correct | 1 ms | 316 KB | Output is correct |
15 | Correct | 1 ms | 204 KB | Output is correct |
16 | Correct | 1 ms | 220 KB | Output is correct |
17 | Correct | 1 ms | 368 KB | Output is correct |
18 | Correct | 1 ms | 208 KB | Output is correct |
19 | Correct | 1 ms | 208 KB | Output is correct |
20 | Correct | 1 ms | 208 KB | Output is correct |
21 | Correct | 1 ms | 208 KB | Output is correct |
22 | Correct | 1 ms | 208 KB | Output is correct |
23 | Correct | 1 ms | 220 KB | Output is correct |
24 | Correct | 1 ms | 220 KB | Output is correct |
25 | Correct | 1 ms | 324 KB | Output is correct |
26 | Correct | 1 ms | 220 KB | Output is correct |
27 | Correct | 1 ms | 220 KB | Output is correct |
28 | Correct | 1 ms | 324 KB | Output is correct |
29 | Correct | 1 ms | 328 KB | Output is correct |
30 | Incorrect | 1 ms | 328 KB | Output isn't correct |
31 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 216 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 316 KB | Output is correct |
4 | Correct | 1 ms | 312 KB | Output is correct |
5 | Correct | 1 ms | 316 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 1 ms | 204 KB | Output is correct |
9 | Correct | 1 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 204 KB | Output is correct |
11 | Correct | 1 ms | 216 KB | Output is correct |
12 | Correct | 1 ms | 216 KB | Output is correct |
13 | Correct | 1 ms | 316 KB | Output is correct |
14 | Correct | 1 ms | 316 KB | Output is correct |
15 | Correct | 1 ms | 316 KB | Output is correct |
16 | Correct | 1 ms | 312 KB | Output is correct |
17 | Correct | 1 ms | 204 KB | Output is correct |
18 | Correct | 1 ms | 204 KB | Output is correct |
19 | Correct | 1 ms | 312 KB | Output is correct |
20 | Correct | 1 ms | 204 KB | Output is correct |
21 | Correct | 1 ms | 204 KB | Output is correct |
22 | Correct | 1 ms | 204 KB | Output is correct |
23 | Correct | 1 ms | 204 KB | Output is correct |
24 | Correct | 1 ms | 332 KB | Output is correct |
25 | Correct | 2 ms | 204 KB | Output is correct |
26 | Correct | 1 ms | 204 KB | Output is correct |
27 | Correct | 1 ms | 312 KB | Output is correct |
28 | Correct | 1 ms | 312 KB | Output is correct |
29 | Correct | 1 ms | 204 KB | Output is correct |
30 | Correct | 2 ms | 312 KB | Output is correct |
31 | Correct | 2 ms | 316 KB | Output is correct |
32 | Correct | 2 ms | 204 KB | Output is correct |
33 | Correct | 2 ms | 204 KB | Output is correct |
34 | Correct | 2 ms | 204 KB | Output is correct |
35 | Correct | 2 ms | 204 KB | Output is correct |
36 | Correct | 2 ms | 204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 284 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Correct | 1 ms | 204 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 2 ms | 204 KB | Output is correct |
9 | Correct | 1 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 316 KB | Output is correct |
11 | Correct | 1 ms | 204 KB | Output is correct |
12 | Correct | 1 ms | 204 KB | Output is correct |
13 | Correct | 1 ms | 204 KB | Output is correct |
14 | Correct | 1 ms | 316 KB | Output is correct |
15 | Correct | 1 ms | 204 KB | Output is correct |
16 | Correct | 1 ms | 204 KB | Output is correct |
17 | Correct | 2 ms | 324 KB | Output is correct |
18 | Correct | 3 ms | 204 KB | Output is correct |
19 | Correct | 2 ms | 316 KB | Output is correct |
20 | Correct | 2 ms | 204 KB | Output is correct |
21 | Correct | 2 ms | 204 KB | Output is correct |
22 | Correct | 2 ms | 204 KB | Output is correct |
23 | Correct | 2 ms | 204 KB | Output is correct |
24 | Correct | 2 ms | 316 KB | Output is correct |
25 | Correct | 3 ms | 312 KB | Output is correct |
26 | Correct | 5 ms | 316 KB | Output is correct |
27 | Correct | 7 ms | 204 KB | Output is correct |
28 | Correct | 12 ms | 204 KB | Output is correct |
29 | Correct | 10 ms | 328 KB | Output is correct |
30 | Correct | 12 ms | 324 KB | Output is correct |
31 | Correct | 10 ms | 324 KB | Output is correct |
32 | Correct | 11 ms | 328 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 216 KB | Output is correct |
2 | Correct | 1 ms | 208 KB | Output is correct |
3 | Correct | 0 ms | 208 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 208 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 216 KB | Output is correct |
8 | Correct | 1 ms | 216 KB | Output is correct |
9 | Correct | 1 ms | 220 KB | Output is correct |
10 | Correct | 1 ms | 216 KB | Output is correct |
11 | Correct | 1 ms | 216 KB | Output is correct |
12 | Correct | 1 ms | 216 KB | Output is correct |
13 | Correct | 1 ms | 216 KB | Output is correct |
14 | Correct | 1 ms | 216 KB | Output is correct |
15 | Correct | 1 ms | 244 KB | Output is correct |
16 | Correct | 1 ms | 328 KB | Output is correct |
17 | Correct | 1 ms | 220 KB | Output is correct |
18 | Correct | 1 ms | 220 KB | Output is correct |
19 | Correct | 1 ms | 328 KB | Output is correct |
20 | Correct | 1 ms | 316 KB | Output is correct |
21 | Correct | 1 ms | 288 KB | Output is correct |
22 | Correct | 1 ms | 208 KB | Output is correct |
23 | Correct | 1 ms | 208 KB | Output is correct |
24 | Correct | 1 ms | 208 KB | Output is correct |
25 | Correct | 1 ms | 208 KB | Output is correct |
26 | Correct | 1 ms | 316 KB | Output is correct |
27 | Correct | 1 ms | 208 KB | Output is correct |
28 | Correct | 1 ms | 208 KB | Output is correct |
29 | Correct | 1 ms | 208 KB | Output is correct |
30 | Incorrect | 1 ms | 312 KB | Output isn't correct |
31 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 316 KB | Output is correct |
4 | Correct | 1 ms | 316 KB | Output is correct |
5 | Correct | 1 ms | 316 KB | Output is correct |
6 | Correct | 1 ms | 204 KB | Output is correct |
7 | Correct | 1 ms | 204 KB | Output is correct |
8 | Correct | 1 ms | 204 KB | Output is correct |
9 | Correct | 1 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 316 KB | Output is correct |
11 | Correct | 1 ms | 316 KB | Output is correct |
12 | Correct | 1 ms | 316 KB | Output is correct |
13 | Correct | 1 ms | 204 KB | Output is correct |
14 | Correct | 1 ms | 204 KB | Output is correct |
15 | Correct | 1 ms | 204 KB | Output is correct |
16 | Correct | 1 ms | 204 KB | Output is correct |
17 | Incorrect | 1 ms | 204 KB | Output isn't correct |
18 | Halted | 0 ms | 0 KB | - |