oj.uz

Submission #956099

# Submission time Handle Problem Language Result Execution time Memory
956099 2024-04-01T05:07:22 Z Trisanu_Das Longest beautiful sequence (IZhO17_subsequence) C++17
100 / 100
 4093 ms 74964 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1e5, B = 1<<10;
 
int n, a[MAXN], k[MAXN], p[MAXN], dp[21][B][B], g[21][B][B];
array<int, 2> res;
 
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i=0; i<n; ++i) cin >> a[i];
 
	for(int i=0; i<n; ++i){
		cin >> k[i];
		int curr = 1, req, x = (a[i] & (B-1)), r = (a[i] ^ x) >> 10;
		p[i] = -1;
 
		for(int l=0; l<B; ++l){
			req = k[i] - __builtin_popcount(l & x);
			if(0 <= req && curr <= dp[req][r][l]){
				curr = dp[req][r][l] + 1;
				p[i] = g[req][r][l];
			}
		}
 
		for(int j=0; j<B; ++j){
			req = __builtin_popcount(j&r);
			if(dp[req][j][x] < curr){
				dp[req][j][x] = curr;
				g[req][j][x] = i;
			}
		}
 
		res = max(res, {curr, i});
	}
	cout << res[0] << '\n';
	int ans[res[0]];
	for(int i=0; i<res[0]; ++i){
		ans[i] = res[1];
		res[1] = p[res[1]];
	}
	for(int i=res[0]; --i>=0; ) cout << ans[i]+1 << ' ';
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10844 KB answer = 4
2 Correct 3 ms 10844 KB answer = 1
3 Correct 3 ms 10840 KB answer = 2
4 Correct 3 ms 10844 KB answer = 1
5 Correct 3 ms 10844 KB answer = 2
6 Correct 15 ms 40796 KB answer = 1
7 Correct 6 ms 29276 KB answer = 1
8 Correct 11 ms 47704 KB answer = 3
9 Correct 17 ms 53884 KB answer = 2
10 Correct 11 ms 49756 KB answer = 3
11 Correct 11 ms 50780 KB answer = 2
12 Correct 11 ms 50524 KB answer = 3
13 Correct 12 ms 54556 KB answer = 2
14 Correct 11 ms 51292 KB answer = 1
15 Correct 11 ms 51548 KB answer = 1
16 Correct 14 ms 61428 KB answer = 1
17 Correct 12 ms 50156 KB answer = 1
18 Correct 9 ms 50776 KB answer = 1
19 Correct 9 ms 50780 KB answer = 1
20 Correct 8 ms 49756 KB answer = 1
21 Correct 8 ms 50780 KB answer = 1

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10844 KB answer = 4
2 Correct 3 ms 10844 KB answer = 1
3 Correct 3 ms 10840 KB answer = 2
4 Correct 3 ms 10844 KB answer = 1
5 Correct 3 ms 10844 KB answer = 2
6 Correct 15 ms 40796 KB answer = 1
7 Correct 6 ms 29276 KB answer = 1
8 Correct 11 ms 47704 KB answer = 3
9 Correct 17 ms 53884 KB answer = 2
10 Correct 11 ms 49756 KB answer = 3
11 Correct 11 ms 50780 KB answer = 2
12 Correct 11 ms 50524 KB answer = 3
13 Correct 12 ms 54556 KB answer = 2
14 Correct 11 ms 51292 KB answer = 1
15 Correct 11 ms 51548 KB answer = 1
16 Correct 14 ms 61428 KB answer = 1
17 Correct 12 ms 50156 KB answer = 1
18 Correct 9 ms 50776 KB answer = 1
19 Correct 9 ms 50780 KB answer = 1
20 Correct 8 ms 49756 KB answer = 1
21 Correct 8 ms 50780 KB answer = 1
22 Correct 202 ms 72488 KB answer = 358
23 Correct 219 ms 72508 KB answer = 336
24 Correct 210 ms 72544 KB answer = 339
25 Correct 196 ms 72404 KB answer = 357
26 Correct 203 ms 72784 KB answer = 354
27 Correct 198 ms 72392 KB answer = 333
28 Correct 196 ms 70312 KB answer = 314
29 Correct 222 ms 72428 KB answer = 322
30 Correct 206 ms 70224 KB answer = 339
31 Correct 198 ms 72444 KB answer = 351
32 Correct 194 ms 69972 KB answer = 1
33 Correct 217 ms 70032 KB answer = 1
34 Correct 192 ms 67948 KB answer = 1
35 Correct 211 ms 67924 KB answer = 1
36 Correct 237 ms 69912 KB answer = 1
37 Correct 87 ms 62880 KB answer = 1
38 Correct 94 ms 62876 KB answer = 1
39 Correct 91 ms 62764 KB answer = 1
40 Correct 85 ms 62876 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10844 KB answer = 4
2 Correct 3 ms 10844 KB answer = 1
3 Correct 3 ms 10840 KB answer = 2
4 Correct 3 ms 10844 KB answer = 1
5 Correct 3 ms 10844 KB answer = 2
6 Correct 15 ms 40796 KB answer = 1
7 Correct 6 ms 29276 KB answer = 1
8 Correct 11 ms 47704 KB answer = 3
9 Correct 17 ms 53884 KB answer = 2
10 Correct 11 ms 49756 KB answer = 3
11 Correct 11 ms 50780 KB answer = 2
12 Correct 11 ms 50524 KB answer = 3
13 Correct 12 ms 54556 KB answer = 2
14 Correct 11 ms 51292 KB answer = 1
15 Correct 11 ms 51548 KB answer = 1
16 Correct 14 ms 61428 KB answer = 1
17 Correct 12 ms 50156 KB answer = 1
18 Correct 9 ms 50776 KB answer = 1
19 Correct 9 ms 50780 KB answer = 1
20 Correct 8 ms 49756 KB answer = 1
21 Correct 8 ms 50780 KB answer = 1
22 Correct 202 ms 72488 KB answer = 358
23 Correct 219 ms 72508 KB answer = 336
24 Correct 210 ms 72544 KB answer = 339
25 Correct 196 ms 72404 KB answer = 357
26 Correct 203 ms 72784 KB answer = 354
27 Correct 198 ms 72392 KB answer = 333
28 Correct 196 ms 70312 KB answer = 314
29 Correct 222 ms 72428 KB answer = 322
30 Correct 206 ms 70224 KB answer = 339
31 Correct 198 ms 72444 KB answer = 351
32 Correct 194 ms 69972 KB answer = 1
33 Correct 217 ms 70032 KB answer = 1
34 Correct 192 ms 67948 KB answer = 1
35 Correct 211 ms 67924 KB answer = 1
36 Correct 237 ms 69912 KB answer = 1
37 Correct 87 ms 62880 KB answer = 1
38 Correct 94 ms 62876 KB answer = 1
39 Correct 91 ms 62764 KB answer = 1
40 Correct 85 ms 62876 KB answer = 1
41 Correct 902 ms 12040 KB answer = 6296
42 Correct 914 ms 11996 KB answer = 6267
43 Correct 913 ms 11888 KB answer = 6264
44 Correct 975 ms 11964 KB answer = 6384
45 Correct 898 ms 12116 KB answer = 6272
46 Correct 896 ms 11928 KB answer = 6177
47 Correct 919 ms 12112 KB answer = 6144
48 Correct 932 ms 12112 KB answer = 6272
49 Correct 929 ms 12132 KB answer = 6241
50 Correct 897 ms 12392 KB answer = 6169
51 Correct 777 ms 11960 KB answer = 1
52 Correct 759 ms 11800 KB answer = 1
53 Correct 785 ms 11884 KB answer = 1
54 Correct 779 ms 12192 KB answer = 1
55 Correct 771 ms 12044 KB answer = 1
56 Correct 1285 ms 12064 KB answer = 1426
57 Correct 1256 ms 11896 KB answer = 1427
58 Correct 1413 ms 12084 KB answer = 1428
59 Correct 1380 ms 12200 KB answer = 1427

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10844 KB answer = 4
2 Correct 3 ms 10844 KB answer = 1
3 Correct 3 ms 10840 KB answer = 2
4 Correct 3 ms 10844 KB answer = 1
5 Correct 3 ms 10844 KB answer = 2
6 Correct 15 ms 40796 KB answer = 1
7 Correct 6 ms 29276 KB answer = 1
8 Correct 11 ms 47704 KB answer = 3
9 Correct 17 ms 53884 KB answer = 2
10 Correct 11 ms 49756 KB answer = 3
11 Correct 11 ms 50780 KB answer = 2
12 Correct 11 ms 50524 KB answer = 3
13 Correct 12 ms 54556 KB answer = 2
14 Correct 11 ms 51292 KB answer = 1
15 Correct 11 ms 51548 KB answer = 1
16 Correct 14 ms 61428 KB answer = 1
17 Correct 12 ms 50156 KB answer = 1
18 Correct 9 ms 50776 KB answer = 1
19 Correct 9 ms 50780 KB answer = 1
20 Correct 8 ms 49756 KB answer = 1
21 Correct 8 ms 50780 KB answer = 1
22 Correct 202 ms 72488 KB answer = 358
23 Correct 219 ms 72508 KB answer = 336
24 Correct 210 ms 72544 KB answer = 339
25 Correct 196 ms 72404 KB answer = 357
26 Correct 203 ms 72784 KB answer = 354
27 Correct 198 ms 72392 KB answer = 333
28 Correct 196 ms 70312 KB answer = 314
29 Correct 222 ms 72428 KB answer = 322
30 Correct 206 ms 70224 KB answer = 339
31 Correct 198 ms 72444 KB answer = 351
32 Correct 194 ms 69972 KB answer = 1
33 Correct 217 ms 70032 KB answer = 1
34 Correct 192 ms 67948 KB answer = 1
35 Correct 211 ms 67924 KB answer = 1
36 Correct 237 ms 69912 KB answer = 1
37 Correct 87 ms 62880 KB answer = 1
38 Correct 94 ms 62876 KB answer = 1
39 Correct 91 ms 62764 KB answer = 1
40 Correct 85 ms 62876 KB answer = 1
41 Correct 902 ms 12040 KB answer = 6296
42 Correct 914 ms 11996 KB answer = 6267
43 Correct 913 ms 11888 KB answer = 6264
44 Correct 975 ms 11964 KB answer = 6384
45 Correct 898 ms 12116 KB answer = 6272
46 Correct 896 ms 11928 KB answer = 6177
47 Correct 919 ms 12112 KB answer = 6144
48 Correct 932 ms 12112 KB answer = 6272
49 Correct 929 ms 12132 KB answer = 6241
50 Correct 897 ms 12392 KB answer = 6169
51 Correct 777 ms 11960 KB answer = 1
52 Correct 759 ms 11800 KB answer = 1
53 Correct 785 ms 11884 KB answer = 1
54 Correct 779 ms 12192 KB answer = 1
55 Correct 771 ms 12044 KB answer = 1
56 Correct 1285 ms 12064 KB answer = 1426
57 Correct 1256 ms 11896 KB answer = 1427
58 Correct 1413 ms 12084 KB answer = 1428
59 Correct 1380 ms 12200 KB answer = 1427
60 Correct 3624 ms 73604 KB answer = 7034
61 Correct 3667 ms 74916 KB answer = 7045
62 Correct 3610 ms 74620 KB answer = 7147
63 Correct 3691 ms 74444 KB answer = 7038
64 Correct 3611 ms 74328 KB answer = 7169
65 Correct 3461 ms 74488 KB answer = 6735
66 Correct 3594 ms 74368 KB answer = 6713
67 Correct 4093 ms 74532 KB answer = 6748
68 Correct 3714 ms 74572 KB answer = 6607
69 Correct 3564 ms 74848 KB answer = 6722
70 Correct 2703 ms 74292 KB answer = 1
71 Correct 2849 ms 74468 KB answer = 1
72 Correct 2727 ms 74300 KB answer = 1
73 Correct 2665 ms 72552 KB answer = 1
74 Correct 2605 ms 72352 KB answer = 1
75 Correct 1070 ms 72636 KB answer = 1
76 Correct 1170 ms 72448 KB answer = 1
77 Correct 1079 ms 72580 KB answer = 1
78 Correct 1141 ms 72424 KB answer = 1
79 Correct 1214 ms 44792 KB answer = 21
80 Correct 1138 ms 51540 KB answer = 7
81 Correct 1173 ms 57368 KB answer = 3
82 Correct 1130 ms 62776 KB answer = 2
83 Correct 1088 ms 66872 KB answer = 1
84 Correct 1091 ms 70948 KB answer = 1
85 Correct 1110 ms 72532 KB answer = 1
86 Correct 1035 ms 69724 KB answer = 11
87 Correct 1028 ms 71552 KB answer = 11
88 Correct 1046 ms 73084 KB answer = 6
89 Correct 1121 ms 73656 KB answer = 4
90 Correct 1100 ms 73400 KB answer = 2
91 Correct 1172 ms 73352 KB answer = 2
92 Correct 1079 ms 72672 KB answer = 2
93 Correct 3536 ms 74964 KB answer = 7211
94 Correct 3621 ms 74684 KB answer = 7032
95 Correct 3708 ms 74512 KB answer = 7092
96 Correct 3962 ms 74748 KB answer = 14167
97 Correct 3951 ms 74788 KB answer = 14159
98 Correct 3918 ms 74800 KB answer = 14125
99 Correct 3786 ms 74608 KB answer = 14121
100 Correct 3922 ms 74820 KB answer = 14010
101 Correct 3957 ms 74780 KB answer = 13976
102 Correct 1132 ms 72460 KB answer = 3
103 Correct 1061 ms 70656 KB answer = 2
104 Correct 1066 ms 67248 KB answer = 3
105 Correct 1076 ms 72488 KB answer = 2
106 Correct 1061 ms 72880 KB answer = 3
107 Correct 1227 ms 74428 KB answer = 4
108 Correct 1210 ms 73848 KB answer = 5
109 Correct 1256 ms 72772 KB answer = 8
110 Correct 1459 ms 70508 KB answer = 22
111 Correct 3455 ms 74752 KB answer = 6760
112 Correct 3428 ms 74600 KB answer = 6788
113 Correct 3557 ms 74860 KB answer = 6632