# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1050780 | 2024-08-09T14:22:00 Z | manhlinh1501 | Bali Sculptures (APIO15_sculpture) | C++17 | 148 ms | 35416 KB |
#include <bits/stdc++.h> using namespace std; using i64 = long long; const i64 oo64 = LLONG_MAX; const int MAXN = 2050; int N, L, R; int a[MAXN]; i64 ans = oo64; namespace subtask1 { bool is_subtask() { return N <= 20; } void solution() { if(is_subtask() == false) return; for(int mask = 0; mask < (1 << N); mask++) { vector<i64> b; b.emplace_back(0); int cb = (mask >> 0 & 1); for(int i = 0; i < N; i++) { if((mask >> i & 1) == cb) b.back() += a[i + 1]; else { b.emplace_back(a[i + 1]); cb ^= 1; } } i64 res = 0; for(i64 x : b) res |= x; if(L <= b.size() and b.size() <= R) ans = min(ans, res); } cout << ans; exit(0); } } namespace subtask23 { int dpL[MAXN][MAXN]; int dpR[MAXN][MAXN]; bool is_subtask() { for(int i = 1; i <= N; i++) { if(a[i] > 20) return false; } return N <= 100; } void solution() { if(is_subtask() == false) return; memset(dpL, 0x3f, sizeof dpL); memset(dpR, -0x3f, sizeof dpR); dpL[0][0] = dpR[0][0] = 0; for(int i = 1; i <= N; i++) { int cur = 0; for(int j = i; j >= 1; j--) { cur += a[j]; for(int mask = 0; mask < (1 << 11); mask++) { dpL[i][mask | cur] = min(dpL[i][mask | cur], dpL[j - 1][mask] + 1); dpR[i][mask | cur] = max(dpR[i][mask | cur], dpR[j - 1][mask] + 1); } } } for(int mask = 0; mask < (1 << 11); mask++) { if(dpL[N][mask] > dpR[N][mask]) continue; if((L <= dpL[N][mask] and dpR[N][mask] <= R) or (L <= dpL[N][mask] and dpL[N][mask] <= R) or (L <= dpR[N][mask] and dpR[N][mask] <= R)) cout << mask, exit(0); } cout << "-1"; exit(0); } } namespace subtask4 { bool is_subtask() { return N <= 100; } bool dp[MAXN][MAXN]; bool check(int mask) { memset(dp, 0, sizeof dp); dp[0][0] = true; for(int i = 1; i <= N; i++) { i64 cur = 0; for(int j = i; j >= 1; j--) { cur += a[j]; if((mask | a[j]) == mask) { for(int z = 1; z <= R; z++) dp[i][z] |= dp[j - 1][z - 1]; } } } for(int i = L; i <= R; i++) { if(dp[N][i]) return true; } return false; } void solution() { if(is_subtask() == false) return; const int B = 50; i64 ans = (1LL << B) - 1; for(int i = B - 1; i >= 0; i--) { if(check(ans ^ (1LL << i))) ans = ans ^ (1LL << i); } cout << ans; exit(0); } } signed main() { #define TASK "code" if (fopen(TASK ".inp", "r")) { freopen(TASK ".inp", "r", stdin); freopen(TASK ".out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> L >> R; for(int i = 1; i <= N; i++) cin >> a[i]; subtask1::solution(); subtask23::solution(); subtask4::solution(); return (0 ^ 0); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 4 ms | 348 KB | Output is correct |
7 | Correct | 15 ms | 464 KB | Output is correct |
8 | Correct | 132 ms | 436 KB | Output is correct |
9 | Correct | 128 ms | 436 KB | Output is correct |
10 | Correct | 129 ms | 348 KB | Output is correct |
11 | Correct | 127 ms | 440 KB | Output is correct |
12 | Correct | 130 ms | 436 KB | Output is correct |
13 | Correct | 131 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
19 | Correct | 4 ms | 348 KB | Output is correct |
20 | Correct | 15 ms | 464 KB | Output is correct |
21 | Correct | 129 ms | 348 KB | Output is correct |
22 | Correct | 139 ms | 348 KB | Output is correct |
23 | Correct | 142 ms | 344 KB | Output is correct |
24 | Correct | 129 ms | 344 KB | Output is correct |
25 | Correct | 127 ms | 436 KB | Output is correct |
26 | Correct | 134 ms | 348 KB | Output is correct |
27 | Correct | 0 ms | 348 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 1 ms | 348 KB | Output is correct |
30 | Correct | 65 ms | 348 KB | Output is correct |
31 | Correct | 134 ms | 440 KB | Output is correct |
32 | Correct | 144 ms | 344 KB | Output is correct |
33 | Correct | 127 ms | 444 KB | Output is correct |
34 | Correct | 127 ms | 348 KB | Output is correct |
35 | Correct | 133 ms | 348 KB | Output is correct |
36 | Correct | 131 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 1 ms | 344 KB | Output is correct |
6 | Correct | 4 ms | 348 KB | Output is correct |
7 | Correct | 19 ms | 348 KB | Output is correct |
8 | Correct | 127 ms | 344 KB | Output is correct |
9 | Correct | 132 ms | 348 KB | Output is correct |
10 | Correct | 148 ms | 348 KB | Output is correct |
11 | Correct | 134 ms | 440 KB | Output is correct |
12 | Correct | 127 ms | 348 KB | Output is correct |
13 | Correct | 129 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 0 ms | 348 KB | Output is correct |
19 | Correct | 4 ms | 348 KB | Output is correct |
20 | Correct | 15 ms | 464 KB | Output is correct |
21 | Correct | 138 ms | 348 KB | Output is correct |
22 | Correct | 147 ms | 344 KB | Output is correct |
23 | Correct | 134 ms | 436 KB | Output is correct |
24 | Correct | 127 ms | 348 KB | Output is correct |
25 | Correct | 129 ms | 348 KB | Output is correct |
26 | Correct | 131 ms | 344 KB | Output is correct |
27 | Correct | 4 ms | 35164 KB | Output is correct |
28 | Correct | 5 ms | 35240 KB | Output is correct |
29 | Correct | 6 ms | 35164 KB | Output is correct |
30 | Correct | 7 ms | 35228 KB | Output is correct |
31 | Correct | 8 ms | 35232 KB | Output is correct |
32 | Correct | 8 ms | 35164 KB | Output is correct |
33 | Correct | 8 ms | 35164 KB | Output is correct |
34 | Correct | 9 ms | 35160 KB | Output is correct |
35 | Correct | 9 ms | 35164 KB | Output is correct |
36 | Correct | 8 ms | 35164 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 344 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 4 ms | 348 KB | Output is correct |
7 | Correct | 15 ms | 460 KB | Output is correct |
8 | Correct | 130 ms | 348 KB | Output is correct |
9 | Correct | 128 ms | 344 KB | Output is correct |
10 | Correct | 135 ms | 344 KB | Output is correct |
11 | Correct | 136 ms | 436 KB | Output is correct |
12 | Correct | 129 ms | 344 KB | Output is correct |
13 | Correct | 133 ms | 444 KB | Output is correct |
14 | Correct | 4 ms | 35160 KB | Output is correct |
15 | Correct | 5 ms | 35164 KB | Output is correct |
16 | Correct | 6 ms | 35240 KB | Output is correct |
17 | Correct | 8 ms | 35416 KB | Output is correct |
18 | Correct | 8 ms | 35164 KB | Output is correct |
19 | Correct | 8 ms | 35160 KB | Output is correct |
20 | Correct | 8 ms | 35232 KB | Output is correct |
21 | Correct | 8 ms | 35164 KB | Output is correct |
22 | Correct | 8 ms | 35224 KB | Output is correct |
23 | Correct | 9 ms | 35164 KB | Output is correct |
24 | Correct | 9 ms | 35236 KB | Output is correct |
25 | Correct | 11 ms | 35124 KB | Output is correct |
26 | Correct | 16 ms | 35160 KB | Output is correct |
27 | Correct | 19 ms | 35160 KB | Output is correct |
28 | Correct | 22 ms | 35164 KB | Output is correct |
29 | Correct | 19 ms | 35160 KB | Output is correct |
30 | Correct | 22 ms | 35232 KB | Output is correct |
31 | Correct | 22 ms | 35164 KB | Output is correct |
32 | Correct | 22 ms | 35160 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 4 ms | 464 KB | Output is correct |
7 | Correct | 16 ms | 348 KB | Output is correct |
8 | Correct | 129 ms | 348 KB | Output is correct |
9 | Correct | 128 ms | 344 KB | Output is correct |
10 | Correct | 140 ms | 436 KB | Output is correct |
11 | Correct | 141 ms | 348 KB | Output is correct |
12 | Correct | 136 ms | 348 KB | Output is correct |
13 | Correct | 127 ms | 348 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 0 ms | 348 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 4 ms | 348 KB | Output is correct |
20 | Correct | 15 ms | 348 KB | Output is correct |
21 | Correct | 126 ms | 440 KB | Output is correct |
22 | Correct | 127 ms | 348 KB | Output is correct |
23 | Correct | 127 ms | 348 KB | Output is correct |
24 | Correct | 131 ms | 452 KB | Output is correct |
25 | Correct | 126 ms | 444 KB | Output is correct |
26 | Correct | 127 ms | 348 KB | Output is correct |
27 | Correct | 1 ms | 348 KB | Output is correct |
28 | Correct | 0 ms | 348 KB | Output is correct |
29 | Correct | 1 ms | 348 KB | Output is correct |
30 | Correct | 62 ms | 444 KB | Output is correct |
31 | Correct | 133 ms | 344 KB | Output is correct |
32 | Correct | 140 ms | 348 KB | Output is correct |
33 | Correct | 128 ms | 344 KB | Output is correct |
34 | Correct | 142 ms | 348 KB | Output is correct |
35 | Correct | 144 ms | 348 KB | Output is correct |
36 | Correct | 129 ms | 444 KB | Output is correct |
37 | Correct | 5 ms | 35160 KB | Output is correct |
38 | Correct | 5 ms | 35164 KB | Output is correct |
39 | Correct | 6 ms | 35216 KB | Output is correct |
40 | Correct | 7 ms | 35232 KB | Output is correct |
41 | Correct | 9 ms | 35164 KB | Output is correct |
42 | Correct | 8 ms | 35240 KB | Output is correct |
43 | Correct | 8 ms | 35164 KB | Output is correct |
44 | Correct | 8 ms | 35164 KB | Output is correct |
45 | Correct | 8 ms | 35164 KB | Output is correct |
46 | Correct | 8 ms | 35228 KB | Output is correct |
47 | Correct | 8 ms | 35164 KB | Output is correct |
48 | Correct | 11 ms | 35164 KB | Output is correct |
49 | Correct | 15 ms | 35240 KB | Output is correct |
50 | Correct | 19 ms | 35164 KB | Output is correct |
51 | Correct | 22 ms | 35032 KB | Output is correct |
52 | Correct | 19 ms | 35164 KB | Output is correct |
53 | Correct | 19 ms | 35236 KB | Output is correct |
54 | Correct | 22 ms | 35240 KB | Output is correct |
55 | Correct | 22 ms | 35164 KB | Output is correct |
56 | Incorrect | 5 ms | 4696 KB | Output isn't correct |
57 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 348 KB | Output is correct |
2 | Correct | 0 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 0 ms | 348 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 6 ms | 460 KB | Output is correct |
7 | Correct | 16 ms | 344 KB | Output is correct |
8 | Correct | 128 ms | 444 KB | Output is correct |
9 | Correct | 130 ms | 348 KB | Output is correct |
10 | Correct | 127 ms | 440 KB | Output is correct |
11 | Correct | 128 ms | 344 KB | Output is correct |
12 | Correct | 128 ms | 344 KB | Output is correct |
13 | Correct | 128 ms | 440 KB | Output is correct |
14 | Correct | 0 ms | 348 KB | Output is correct |
15 | Correct | 0 ms | 348 KB | Output is correct |
16 | Correct | 1 ms | 348 KB | Output is correct |
17 | Correct | 63 ms | 440 KB | Output is correct |
18 | Correct | 126 ms | 344 KB | Output is correct |
19 | Correct | 129 ms | 440 KB | Output is correct |
20 | Correct | 127 ms | 348 KB | Output is correct |
21 | Correct | 128 ms | 344 KB | Output is correct |
22 | Correct | 130 ms | 344 KB | Output is correct |
23 | Correct | 128 ms | 344 KB | Output is correct |
24 | Correct | 5 ms | 35164 KB | Output is correct |
25 | Correct | 5 ms | 35164 KB | Output is correct |
26 | Correct | 6 ms | 35164 KB | Output is correct |
27 | Correct | 7 ms | 35164 KB | Output is correct |
28 | Correct | 8 ms | 35164 KB | Output is correct |
29 | Correct | 8 ms | 35160 KB | Output is correct |
30 | Correct | 8 ms | 35148 KB | Output is correct |
31 | Correct | 8 ms | 35164 KB | Output is correct |
32 | Correct | 8 ms | 35164 KB | Output is correct |
33 | Correct | 8 ms | 35164 KB | Output is correct |
34 | Correct | 9 ms | 35164 KB | Output is correct |
35 | Correct | 11 ms | 35236 KB | Output is correct |
36 | Correct | 15 ms | 35240 KB | Output is correct |
37 | Correct | 21 ms | 35164 KB | Output is correct |
38 | Correct | 22 ms | 35164 KB | Output is correct |
39 | Correct | 19 ms | 35212 KB | Output is correct |
40 | Correct | 19 ms | 35164 KB | Output is correct |
41 | Correct | 21 ms | 35232 KB | Output is correct |
42 | Correct | 23 ms | 35164 KB | Output is correct |
43 | Incorrect | 5 ms | 4700 KB | Output isn't correct |
44 | Halted | 0 ms | 0 KB | - |