# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
36180 | 2017-12-06T07:04:19 Z | UncleGrandpa925 | Longest beautiful sequence (IZhO17_subsequence) | C++14 | 4549 ms | 48776 KB |
/*input 4 1 2 3 4 10 0 1 0 5 5 3 5 3 5 10 1 20 1 20 */ #include <bits/stdc++.h> using namespace std; #define sp ' ' #define endl '\n' #define fi first #define se second #define mp make_pair #define N 100005 #define M 1024 #define bit(x,y) ((x>>y)&1LL) int n; int a[N], b[N], cnt[M]; int dp[N], par[N]; int g[M][M][11]; vector<int> order; signed main() { // #ifdef in1code // freopen("1test.inp", "r", stdin); // #endif scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) scanf("%d", &b[i]); for (int i = 0; i < M; i++) cnt[i] = __builtin_popcount(i); memset(g, 0, sizeof(g)); pair<int, int> ans = mp(1, 1); for (int i = 1; i <= n; i ++) { dp[i] = 1; int prefix = a[i] >> 10; int suffix = a[i] - (prefix << 10); for (int mask = 0; mask < M; mask++) { int left = b[i] - cnt[mask & prefix]; if (left < 0 || left > 10) continue; int y = g[mask][suffix][left]; if (dp[y] + 1 > dp[i]) { dp[i] = dp[y] + 1; par[i] = y; } } if (dp[i] > ans.fi) ans = mp(dp[i], i); for (int mask = 0; mask < M; mask ++) { int x = mask & suffix; int &y = g[prefix][mask][cnt[x]]; if (dp[y] < dp[i]) y = i; } } while (ans.fi > 0) { order.push_back(ans.se); ans.se = par[ans.se]; ans.fi--; } reverse(order.begin(), order.end()); printf("%lu\n", order.size()); for (int i = 0; i < order.size(); i++) printf("%d ", order[i]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 48636 KB | answer = 4 |
2 | Correct | 3 ms | 48636 KB | answer = 1 |
3 | Correct | 6 ms | 48636 KB | answer = 2 |
4 | Correct | 3 ms | 48636 KB | answer = 1 |
5 | Correct | 0 ms | 48636 KB | answer = 2 |
6 | Correct | 9 ms | 48636 KB | answer = 1 |
7 | Correct | 6 ms | 48636 KB | answer = 1 |
8 | Correct | 0 ms | 48636 KB | answer = 3 |
9 | Correct | 3 ms | 48636 KB | answer = 2 |
10 | Correct | 0 ms | 48636 KB | answer = 3 |
11 | Correct | 6 ms | 48636 KB | answer = 2 |
12 | Correct | 0 ms | 48636 KB | answer = 3 |
13 | Correct | 0 ms | 48636 KB | answer = 2 |
14 | Correct | 3 ms | 48636 KB | answer = 1 |
15 | Correct | 9 ms | 48636 KB | answer = 1 |
16 | Correct | 0 ms | 48636 KB | answer = 1 |
17 | Correct | 0 ms | 48636 KB | answer = 1 |
18 | Correct | 6 ms | 48636 KB | answer = 1 |
19 | Correct | 0 ms | 48636 KB | answer = 1 |
20 | Correct | 9 ms | 48636 KB | answer = 1 |
21 | Correct | 3 ms | 48636 KB | answer = 1 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 48636 KB | answer = 4 |
2 | Correct | 3 ms | 48636 KB | answer = 1 |
3 | Correct | 6 ms | 48636 KB | answer = 2 |
4 | Correct | 3 ms | 48636 KB | answer = 1 |
5 | Correct | 0 ms | 48636 KB | answer = 2 |
6 | Correct | 9 ms | 48636 KB | answer = 1 |
7 | Correct | 6 ms | 48636 KB | answer = 1 |
8 | Correct | 0 ms | 48636 KB | answer = 3 |
9 | Correct | 3 ms | 48636 KB | answer = 2 |
10 | Correct | 0 ms | 48636 KB | answer = 3 |
11 | Correct | 6 ms | 48636 KB | answer = 2 |
12 | Correct | 0 ms | 48636 KB | answer = 3 |
13 | Correct | 0 ms | 48636 KB | answer = 2 |
14 | Correct | 3 ms | 48636 KB | answer = 1 |
15 | Correct | 9 ms | 48636 KB | answer = 1 |
16 | Correct | 0 ms | 48636 KB | answer = 1 |
17 | Correct | 0 ms | 48636 KB | answer = 1 |
18 | Correct | 6 ms | 48636 KB | answer = 1 |
19 | Correct | 0 ms | 48636 KB | answer = 1 |
20 | Correct | 9 ms | 48636 KB | answer = 1 |
21 | Correct | 3 ms | 48636 KB | answer = 1 |
22 | Correct | 149 ms | 48636 KB | answer = 358 |
23 | Correct | 146 ms | 48636 KB | answer = 336 |
24 | Correct | 139 ms | 48636 KB | answer = 339 |
25 | Correct | 143 ms | 48636 KB | answer = 357 |
26 | Correct | 143 ms | 48636 KB | answer = 354 |
27 | Correct | 133 ms | 48636 KB | answer = 333 |
28 | Correct | 123 ms | 48636 KB | answer = 314 |
29 | Correct | 126 ms | 48636 KB | answer = 322 |
30 | Correct | 133 ms | 48636 KB | answer = 339 |
31 | Correct | 159 ms | 48636 KB | answer = 351 |
32 | Correct | 216 ms | 48636 KB | answer = 1 |
33 | Correct | 206 ms | 48636 KB | answer = 1 |
34 | Correct | 189 ms | 48636 KB | answer = 1 |
35 | Correct | 203 ms | 48636 KB | answer = 1 |
36 | Correct | 226 ms | 48636 KB | answer = 1 |
37 | Correct | 153 ms | 48636 KB | answer = 1 |
38 | Correct | 149 ms | 48636 KB | answer = 1 |
39 | Correct | 159 ms | 48636 KB | answer = 1 |
40 | Correct | 143 ms | 48636 KB | answer = 1 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 48636 KB | answer = 4 |
2 | Correct | 3 ms | 48636 KB | answer = 1 |
3 | Correct | 6 ms | 48636 KB | answer = 2 |
4 | Correct | 3 ms | 48636 KB | answer = 1 |
5 | Correct | 0 ms | 48636 KB | answer = 2 |
6 | Correct | 9 ms | 48636 KB | answer = 1 |
7 | Correct | 6 ms | 48636 KB | answer = 1 |
8 | Correct | 0 ms | 48636 KB | answer = 3 |
9 | Correct | 3 ms | 48636 KB | answer = 2 |
10 | Correct | 0 ms | 48636 KB | answer = 3 |
11 | Correct | 6 ms | 48636 KB | answer = 2 |
12 | Correct | 0 ms | 48636 KB | answer = 3 |
13 | Correct | 0 ms | 48636 KB | answer = 2 |
14 | Correct | 3 ms | 48636 KB | answer = 1 |
15 | Correct | 9 ms | 48636 KB | answer = 1 |
16 | Correct | 0 ms | 48636 KB | answer = 1 |
17 | Correct | 0 ms | 48636 KB | answer = 1 |
18 | Correct | 6 ms | 48636 KB | answer = 1 |
19 | Correct | 0 ms | 48636 KB | answer = 1 |
20 | Correct | 9 ms | 48636 KB | answer = 1 |
21 | Correct | 3 ms | 48636 KB | answer = 1 |
22 | Correct | 149 ms | 48636 KB | answer = 358 |
23 | Correct | 146 ms | 48636 KB | answer = 336 |
24 | Correct | 139 ms | 48636 KB | answer = 339 |
25 | Correct | 143 ms | 48636 KB | answer = 357 |
26 | Correct | 143 ms | 48636 KB | answer = 354 |
27 | Correct | 133 ms | 48636 KB | answer = 333 |
28 | Correct | 123 ms | 48636 KB | answer = 314 |
29 | Correct | 126 ms | 48636 KB | answer = 322 |
30 | Correct | 133 ms | 48636 KB | answer = 339 |
31 | Correct | 159 ms | 48636 KB | answer = 351 |
32 | Correct | 216 ms | 48636 KB | answer = 1 |
33 | Correct | 206 ms | 48636 KB | answer = 1 |
34 | Correct | 189 ms | 48636 KB | answer = 1 |
35 | Correct | 203 ms | 48636 KB | answer = 1 |
36 | Correct | 226 ms | 48636 KB | answer = 1 |
37 | Correct | 153 ms | 48636 KB | answer = 1 |
38 | Correct | 149 ms | 48636 KB | answer = 1 |
39 | Correct | 159 ms | 48636 KB | answer = 1 |
40 | Correct | 143 ms | 48636 KB | answer = 1 |
41 | Correct | 1546 ms | 48776 KB | answer = 6296 |
42 | Correct | 1646 ms | 48776 KB | answer = 6267 |
43 | Correct | 1543 ms | 48776 KB | answer = 6264 |
44 | Correct | 1546 ms | 48776 KB | answer = 6384 |
45 | Correct | 1733 ms | 48776 KB | answer = 6272 |
46 | Correct | 1453 ms | 48776 KB | answer = 6177 |
47 | Correct | 1176 ms | 48776 KB | answer = 6144 |
48 | Correct | 1489 ms | 48776 KB | answer = 6272 |
49 | Correct | 1463 ms | 48776 KB | answer = 6241 |
50 | Correct | 1463 ms | 48776 KB | answer = 6169 |
51 | Correct | 389 ms | 48636 KB | answer = 1 |
52 | Correct | 389 ms | 48636 KB | answer = 1 |
53 | Correct | 406 ms | 48636 KB | answer = 1 |
54 | Correct | 373 ms | 48636 KB | answer = 1 |
55 | Correct | 386 ms | 48636 KB | answer = 1 |
56 | Correct | 1323 ms | 48636 KB | answer = 1426 |
57 | Correct | 1093 ms | 48636 KB | answer = 1427 |
58 | Correct | 1156 ms | 48636 KB | answer = 1428 |
59 | Correct | 1299 ms | 48636 KB | answer = 1427 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 48636 KB | answer = 4 |
2 | Correct | 3 ms | 48636 KB | answer = 1 |
3 | Correct | 6 ms | 48636 KB | answer = 2 |
4 | Correct | 3 ms | 48636 KB | answer = 1 |
5 | Correct | 0 ms | 48636 KB | answer = 2 |
6 | Correct | 9 ms | 48636 KB | answer = 1 |
7 | Correct | 6 ms | 48636 KB | answer = 1 |
8 | Correct | 0 ms | 48636 KB | answer = 3 |
9 | Correct | 3 ms | 48636 KB | answer = 2 |
10 | Correct | 0 ms | 48636 KB | answer = 3 |
11 | Correct | 6 ms | 48636 KB | answer = 2 |
12 | Correct | 0 ms | 48636 KB | answer = 3 |
13 | Correct | 0 ms | 48636 KB | answer = 2 |
14 | Correct | 3 ms | 48636 KB | answer = 1 |
15 | Correct | 9 ms | 48636 KB | answer = 1 |
16 | Correct | 0 ms | 48636 KB | answer = 1 |
17 | Correct | 0 ms | 48636 KB | answer = 1 |
18 | Correct | 6 ms | 48636 KB | answer = 1 |
19 | Correct | 0 ms | 48636 KB | answer = 1 |
20 | Correct | 9 ms | 48636 KB | answer = 1 |
21 | Correct | 3 ms | 48636 KB | answer = 1 |
22 | Correct | 149 ms | 48636 KB | answer = 358 |
23 | Correct | 146 ms | 48636 KB | answer = 336 |
24 | Correct | 139 ms | 48636 KB | answer = 339 |
25 | Correct | 143 ms | 48636 KB | answer = 357 |
26 | Correct | 143 ms | 48636 KB | answer = 354 |
27 | Correct | 133 ms | 48636 KB | answer = 333 |
28 | Correct | 123 ms | 48636 KB | answer = 314 |
29 | Correct | 126 ms | 48636 KB | answer = 322 |
30 | Correct | 133 ms | 48636 KB | answer = 339 |
31 | Correct | 159 ms | 48636 KB | answer = 351 |
32 | Correct | 216 ms | 48636 KB | answer = 1 |
33 | Correct | 206 ms | 48636 KB | answer = 1 |
34 | Correct | 189 ms | 48636 KB | answer = 1 |
35 | Correct | 203 ms | 48636 KB | answer = 1 |
36 | Correct | 226 ms | 48636 KB | answer = 1 |
37 | Correct | 153 ms | 48636 KB | answer = 1 |
38 | Correct | 149 ms | 48636 KB | answer = 1 |
39 | Correct | 159 ms | 48636 KB | answer = 1 |
40 | Correct | 143 ms | 48636 KB | answer = 1 |
41 | Correct | 1546 ms | 48776 KB | answer = 6296 |
42 | Correct | 1646 ms | 48776 KB | answer = 6267 |
43 | Correct | 1543 ms | 48776 KB | answer = 6264 |
44 | Correct | 1546 ms | 48776 KB | answer = 6384 |
45 | Correct | 1733 ms | 48776 KB | answer = 6272 |
46 | Correct | 1453 ms | 48776 KB | answer = 6177 |
47 | Correct | 1176 ms | 48776 KB | answer = 6144 |
48 | Correct | 1489 ms | 48776 KB | answer = 6272 |
49 | Correct | 1463 ms | 48776 KB | answer = 6241 |
50 | Correct | 1463 ms | 48776 KB | answer = 6169 |
51 | Correct | 389 ms | 48636 KB | answer = 1 |
52 | Correct | 389 ms | 48636 KB | answer = 1 |
53 | Correct | 406 ms | 48636 KB | answer = 1 |
54 | Correct | 373 ms | 48636 KB | answer = 1 |
55 | Correct | 386 ms | 48636 KB | answer = 1 |
56 | Correct | 1323 ms | 48636 KB | answer = 1426 |
57 | Correct | 1093 ms | 48636 KB | answer = 1427 |
58 | Correct | 1156 ms | 48636 KB | answer = 1428 |
59 | Correct | 1299 ms | 48636 KB | answer = 1427 |
60 | Correct | 2833 ms | 48776 KB | answer = 7034 |
61 | Correct | 3119 ms | 48776 KB | answer = 7045 |
62 | Correct | 3093 ms | 48776 KB | answer = 7147 |
63 | Correct | 2986 ms | 48776 KB | answer = 7038 |
64 | Correct | 2923 ms | 48776 KB | answer = 7169 |
65 | Correct | 2873 ms | 48776 KB | answer = 6735 |
66 | Correct | 3106 ms | 48776 KB | answer = 6713 |
67 | Correct | 2799 ms | 48776 KB | answer = 6748 |
68 | Correct | 2646 ms | 48776 KB | answer = 6607 |
69 | Correct | 2813 ms | 48776 KB | answer = 6722 |
70 | Correct | 4256 ms | 48636 KB | answer = 1 |
71 | Correct | 4283 ms | 48636 KB | answer = 1 |
72 | Correct | 4486 ms | 48636 KB | answer = 1 |
73 | Correct | 4549 ms | 48636 KB | answer = 1 |
74 | Correct | 4459 ms | 48636 KB | answer = 1 |
75 | Correct | 3256 ms | 48636 KB | answer = 1 |
76 | Correct | 3206 ms | 48636 KB | answer = 1 |
77 | Correct | 2919 ms | 48636 KB | answer = 1 |
78 | Correct | 3149 ms | 48636 KB | answer = 1 |
79 | Correct | 2226 ms | 48636 KB | answer = 21 |
80 | Correct | 2543 ms | 48636 KB | answer = 7 |
81 | Correct | 2626 ms | 48636 KB | answer = 3 |
82 | Correct | 2886 ms | 48636 KB | answer = 2 |
83 | Correct | 3199 ms | 48636 KB | answer = 1 |
84 | Correct | 3179 ms | 48636 KB | answer = 1 |
85 | Correct | 3269 ms | 48636 KB | answer = 1 |
86 | Correct | 2229 ms | 48636 KB | answer = 11 |
87 | Correct | 2676 ms | 48636 KB | answer = 11 |
88 | Correct | 2773 ms | 48636 KB | answer = 6 |
89 | Correct | 3069 ms | 48636 KB | answer = 4 |
90 | Correct | 2979 ms | 48636 KB | answer = 2 |
91 | Correct | 3339 ms | 48636 KB | answer = 2 |
92 | Correct | 3149 ms | 48636 KB | answer = 2 |
93 | Correct | 3036 ms | 48776 KB | answer = 7211 |
94 | Correct | 3016 ms | 48776 KB | answer = 7032 |
95 | Correct | 2836 ms | 48776 KB | answer = 7092 |
96 | Correct | 3933 ms | 48776 KB | answer = 14167 |
97 | Correct | 3599 ms | 48776 KB | answer = 14159 |
98 | Correct | 3813 ms | 48776 KB | answer = 14125 |
99 | Correct | 3779 ms | 48776 KB | answer = 14121 |
100 | Correct | 3856 ms | 48776 KB | answer = 14010 |
101 | Correct | 3966 ms | 48776 KB | answer = 13976 |
102 | Correct | 3316 ms | 48636 KB | answer = 3 |
103 | Correct | 3056 ms | 48636 KB | answer = 2 |
104 | Correct | 3219 ms | 48636 KB | answer = 3 |
105 | Correct | 3349 ms | 48636 KB | answer = 2 |
106 | Correct | 3143 ms | 48636 KB | answer = 3 |
107 | Correct | 2619 ms | 48636 KB | answer = 4 |
108 | Correct | 1829 ms | 48636 KB | answer = 5 |
109 | Correct | 1256 ms | 48636 KB | answer = 8 |
110 | Correct | 819 ms | 48636 KB | answer = 22 |
111 | Correct | 3056 ms | 48776 KB | answer = 6760 |
112 | Correct | 2996 ms | 48776 KB | answer = 6788 |
113 | Correct | 2946 ms | 48776 KB | answer = 6632 |