oj.uz

Submission #384537

# Submission time Handle Problem Language Result Execution time Memory
384537 2021-04-01T20:25:27 Z antimirage Longest beautiful sequence (IZhO17_subsequence) C++14
100 / 100
 3472 ms 56064 KB 
#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define mk make_pair
#define pb emplace_back
#define all(s) s.begin(), s.end()
 
using namespace std;
 
const int N = 1e5 + 5;
 
int dp[25][1025][1025], p[N], n, ar[N], k, ans, ind[25][1025][1025], last, path[N], sz, cn[N];
 
main()
{
	for (int j = 0; j < 1024; j++)
		cn[j] = __builtin_popcount(j);
		
	cin >> n;
	
	for (int i = 1; i <= n; i++)
		scanf("%d", &ar[i]);
		
	for (int i = 1; i <= n; i++){
		scanf("%d", &k);
		
		int pref = (ar[i] >> 10);
		int suf = ar[i] - (pref << 10), res = 0;
		
		for (int j = 0; j < 1024; j++)
		{
			if ( cn[ j & suf ] <= k && dp[ k - cn[ j & suf ] ][pref][j] > res )
			{
				res = dp[ k - cn[ j & suf ] ][pref][j];
				p[i] = ind[ k - cn[ j & suf ] ][pref][j];
			}
		}
		res++;
		
		if (res > ans){
			ans = res;
			last = i;
		}
		
		for (int j = 0; j < 1024; j++){
			if (res > dp[cn[pref & j] ][j][suf])
			{
				dp[cn[pref & j] ][j][suf] = res;
				ind[cn[pref & j] ][j][suf] = i;
			}
		}
	}
	cout << ans << endl;
	
	while (ans--){
		path[++sz] = last;
		last = p[last];
	}
	for (int i = sz; i >= 1; i--)
		printf("%d ", path[i]);
}

Compilation message

subsequence.cpp:15:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main()
      |      ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |   scanf("%d", &ar[i]);
      |   ~~~~~^~~~~~~~~~~~~~
subsequence.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |   scanf("%d", &k);
      |   ~~~~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8556 KB answer = 4
2 Correct 6 ms 8556 KB answer = 1
3 Correct 7 ms 8556 KB answer = 2
4 Correct 6 ms 8556 KB answer = 1
5 Correct 6 ms 8556 KB answer = 2
6 Correct 13 ms 19564 KB answer = 1
7 Correct 6 ms 8684 KB answer = 1
8 Correct 22 ms 32492 KB answer = 3
9 Correct 24 ms 36844 KB answer = 2
10 Correct 22 ms 32236 KB answer = 3
11 Correct 24 ms 33644 KB answer = 2
12 Correct 23 ms 33644 KB answer = 3
13 Correct 23 ms 34176 KB answer = 2
14 Correct 21 ms 31468 KB answer = 1
15 Correct 24 ms 36204 KB answer = 1
16 Correct 27 ms 39788 KB answer = 1
17 Correct 27 ms 34156 KB answer = 1
18 Correct 11 ms 16364 KB answer = 1
19 Correct 11 ms 16364 KB answer = 1
20 Correct 10 ms 14316 KB answer = 1
21 Correct 11 ms 16364 KB answer = 1

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8556 KB answer = 4
2 Correct 6 ms 8556 KB answer = 1
3 Correct 7 ms 8556 KB answer = 2
4 Correct 6 ms 8556 KB answer = 1
5 Correct 6 ms 8556 KB answer = 2
6 Correct 13 ms 19564 KB answer = 1
7 Correct 6 ms 8684 KB answer = 1
8 Correct 22 ms 32492 KB answer = 3
9 Correct 24 ms 36844 KB answer = 2
10 Correct 22 ms 32236 KB answer = 3
11 Correct 24 ms 33644 KB answer = 2
12 Correct 23 ms 33644 KB answer = 3
13 Correct 23 ms 34176 KB answer = 2
14 Correct 21 ms 31468 KB answer = 1
15 Correct 24 ms 36204 KB answer = 1
16 Correct 27 ms 39788 KB answer = 1
17 Correct 27 ms 34156 KB answer = 1
18 Correct 11 ms 16364 KB answer = 1
19 Correct 11 ms 16364 KB answer = 1
20 Correct 10 ms 14316 KB answer = 1
21 Correct 11 ms 16364 KB answer = 1
22 Correct 211 ms 53868 KB answer = 358
23 Correct 211 ms 53996 KB answer = 336
24 Correct 206 ms 53868 KB answer = 339
25 Correct 225 ms 53996 KB answer = 357
26 Correct 212 ms 53900 KB answer = 354
27 Correct 200 ms 53484 KB answer = 333
28 Correct 216 ms 53612 KB answer = 314
29 Correct 198 ms 53484 KB answer = 322
30 Correct 207 ms 53612 KB answer = 339
31 Correct 204 ms 53484 KB answer = 351
32 Correct 179 ms 52844 KB answer = 1
33 Correct 213 ms 52972 KB answer = 1
34 Correct 180 ms 52972 KB answer = 1
35 Correct 184 ms 52972 KB answer = 1
36 Correct 188 ms 52844 KB answer = 1
37 Correct 113 ms 34540 KB answer = 1
38 Correct 111 ms 34412 KB answer = 1
39 Correct 109 ms 34540 KB answer = 1
40 Correct 115 ms 34412 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8556 KB answer = 4
2 Correct 6 ms 8556 KB answer = 1
3 Correct 7 ms 8556 KB answer = 2
4 Correct 6 ms 8556 KB answer = 1
5 Correct 6 ms 8556 KB answer = 2
6 Correct 13 ms 19564 KB answer = 1
7 Correct 6 ms 8684 KB answer = 1
8 Correct 22 ms 32492 KB answer = 3
9 Correct 24 ms 36844 KB answer = 2
10 Correct 22 ms 32236 KB answer = 3
11 Correct 24 ms 33644 KB answer = 2
12 Correct 23 ms 33644 KB answer = 3
13 Correct 23 ms 34176 KB answer = 2
14 Correct 21 ms 31468 KB answer = 1
15 Correct 24 ms 36204 KB answer = 1
16 Correct 27 ms 39788 KB answer = 1
17 Correct 27 ms 34156 KB answer = 1
18 Correct 11 ms 16364 KB answer = 1
19 Correct 11 ms 16364 KB answer = 1
20 Correct 10 ms 14316 KB answer = 1
21 Correct 11 ms 16364 KB answer = 1
22 Correct 211 ms 53868 KB answer = 358
23 Correct 211 ms 53996 KB answer = 336
24 Correct 206 ms 53868 KB answer = 339
25 Correct 225 ms 53996 KB answer = 357
26 Correct 212 ms 53900 KB answer = 354
27 Correct 200 ms 53484 KB answer = 333
28 Correct 216 ms 53612 KB answer = 314
29 Correct 198 ms 53484 KB answer = 322
30 Correct 207 ms 53612 KB answer = 339
31 Correct 204 ms 53484 KB answer = 351
32 Correct 179 ms 52844 KB answer = 1
33 Correct 213 ms 52972 KB answer = 1
34 Correct 180 ms 52972 KB answer = 1
35 Correct 184 ms 52972 KB answer = 1
36 Correct 188 ms 52844 KB answer = 1
37 Correct 113 ms 34540 KB answer = 1
38 Correct 111 ms 34412 KB answer = 1
39 Correct 109 ms 34540 KB answer = 1
40 Correct 115 ms 34412 KB answer = 1
41 Correct 1220 ms 10064 KB answer = 6296
42 Correct 1331 ms 10132 KB answer = 6267
43 Correct 1212 ms 10216 KB answer = 6264
44 Correct 1259 ms 10220 KB answer = 6384
45 Correct 1205 ms 10220 KB answer = 6272
46 Correct 1247 ms 10348 KB answer = 6177
47 Correct 1216 ms 10220 KB answer = 6144
48 Correct 1235 ms 10220 KB answer = 6272
49 Correct 1185 ms 10268 KB answer = 6241
50 Correct 1196 ms 10456 KB answer = 6169
51 Correct 643 ms 9836 KB answer = 1
52 Correct 648 ms 9708 KB answer = 1
53 Correct 647 ms 9836 KB answer = 1
54 Correct 637 ms 9700 KB answer = 1
55 Correct 645 ms 9724 KB answer = 1
56 Correct 2506 ms 9964 KB answer = 1426
57 Correct 2518 ms 10360 KB answer = 1427
58 Correct 2501 ms 9964 KB answer = 1428
59 Correct 2517 ms 9964 KB answer = 1427

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8556 KB answer = 4
2 Correct 6 ms 8556 KB answer = 1
3 Correct 7 ms 8556 KB answer = 2
4 Correct 6 ms 8556 KB answer = 1
5 Correct 6 ms 8556 KB answer = 2
6 Correct 13 ms 19564 KB answer = 1
7 Correct 6 ms 8684 KB answer = 1
8 Correct 22 ms 32492 KB answer = 3
9 Correct 24 ms 36844 KB answer = 2
10 Correct 22 ms 32236 KB answer = 3
11 Correct 24 ms 33644 KB answer = 2
12 Correct 23 ms 33644 KB answer = 3
13 Correct 23 ms 34176 KB answer = 2
14 Correct 21 ms 31468 KB answer = 1
15 Correct 24 ms 36204 KB answer = 1
16 Correct 27 ms 39788 KB answer = 1
17 Correct 27 ms 34156 KB answer = 1
18 Correct 11 ms 16364 KB answer = 1
19 Correct 11 ms 16364 KB answer = 1
20 Correct 10 ms 14316 KB answer = 1
21 Correct 11 ms 16364 KB answer = 1
22 Correct 211 ms 53868 KB answer = 358
23 Correct 211 ms 53996 KB answer = 336
24 Correct 206 ms 53868 KB answer = 339
25 Correct 225 ms 53996 KB answer = 357
26 Correct 212 ms 53900 KB answer = 354
27 Correct 200 ms 53484 KB answer = 333
28 Correct 216 ms 53612 KB answer = 314
29 Correct 198 ms 53484 KB answer = 322
30 Correct 207 ms 53612 KB answer = 339
31 Correct 204 ms 53484 KB answer = 351
32 Correct 179 ms 52844 KB answer = 1
33 Correct 213 ms 52972 KB answer = 1
34 Correct 180 ms 52972 KB answer = 1
35 Correct 184 ms 52972 KB answer = 1
36 Correct 188 ms 52844 KB answer = 1
37 Correct 113 ms 34540 KB answer = 1
38 Correct 111 ms 34412 KB answer = 1
39 Correct 109 ms 34540 KB answer = 1
40 Correct 115 ms 34412 KB answer = 1
41 Correct 1220 ms 10064 KB answer = 6296
42 Correct 1331 ms 10132 KB answer = 6267
43 Correct 1212 ms 10216 KB answer = 6264
44 Correct 1259 ms 10220 KB answer = 6384
45 Correct 1205 ms 10220 KB answer = 6272
46 Correct 1247 ms 10348 KB answer = 6177
47 Correct 1216 ms 10220 KB answer = 6144
48 Correct 1235 ms 10220 KB answer = 6272
49 Correct 1185 ms 10268 KB answer = 6241
50 Correct 1196 ms 10456 KB answer = 6169
51 Correct 643 ms 9836 KB answer = 1
52 Correct 648 ms 9708 KB answer = 1
53 Correct 647 ms 9836 KB answer = 1
54 Correct 637 ms 9700 KB answer = 1
55 Correct 645 ms 9724 KB answer = 1
56 Correct 2506 ms 9964 KB answer = 1426
57 Correct 2518 ms 10360 KB answer = 1427
58 Correct 2501 ms 9964 KB answer = 1428
59 Correct 2517 ms 9964 KB answer = 1427
60 Correct 2951 ms 55788 KB answer = 7034
61 Correct 2960 ms 55896 KB answer = 7045
62 Correct 2953 ms 55988 KB answer = 7147
63 Correct 2964 ms 55940 KB answer = 7038
64 Correct 2956 ms 55984 KB answer = 7169
65 Correct 2841 ms 55708 KB answer = 6735
66 Correct 2887 ms 55560 KB answer = 6713
67 Correct 2908 ms 55848 KB answer = 6748
68 Correct 2867 ms 55528 KB answer = 6607
69 Correct 2807 ms 55716 KB answer = 6722
70 Correct 2250 ms 55148 KB answer = 1
71 Correct 2278 ms 54892 KB answer = 1
72 Correct 2261 ms 55020 KB answer = 1
73 Correct 2278 ms 54892 KB answer = 1
74 Correct 2241 ms 55232 KB answer = 1
75 Correct 1235 ms 51096 KB answer = 1
76 Correct 1185 ms 51052 KB answer = 1
77 Correct 1220 ms 51180 KB answer = 1
78 Correct 1225 ms 51132 KB answer = 1
79 Correct 1231 ms 41300 KB answer = 21
80 Correct 1177 ms 46700 KB answer = 7
81 Correct 1200 ms 50540 KB answer = 3
82 Correct 1194 ms 52844 KB answer = 2
83 Correct 1143 ms 52844 KB answer = 1
84 Correct 1193 ms 51744 KB answer = 1
85 Correct 1254 ms 51196 KB answer = 1
86 Correct 1004 ms 46444 KB answer = 11
87 Correct 1104 ms 50284 KB answer = 11
88 Correct 1146 ms 52588 KB answer = 6
89 Correct 1191 ms 54040 KB answer = 4
90 Correct 1204 ms 53532 KB answer = 2
91 Correct 1222 ms 52200 KB answer = 2
92 Correct 1268 ms 51532 KB answer = 2
93 Correct 2939 ms 55788 KB answer = 7211
94 Correct 2943 ms 55788 KB answer = 7032
95 Correct 2941 ms 55660 KB answer = 7092
96 Correct 3460 ms 55960 KB answer = 14167
97 Correct 3470 ms 56064 KB answer = 14159
98 Correct 3451 ms 55916 KB answer = 14125
99 Correct 3464 ms 55736 KB answer = 14121
100 Correct 3472 ms 55684 KB answer = 14010
101 Correct 3436 ms 55748 KB answer = 13976
102 Correct 1255 ms 51052 KB answer = 3
103 Correct 1216 ms 51820 KB answer = 2
104 Correct 1177 ms 52844 KB answer = 3
105 Correct 1251 ms 51436 KB answer = 2
106 Correct 1260 ms 52256 KB answer = 3
107 Correct 1327 ms 55116 KB answer = 4
108 Correct 1346 ms 53996 KB answer = 5
109 Correct 1417 ms 51232 KB answer = 8
110 Correct 1507 ms 46316 KB answer = 22
111 Correct 2846 ms 55532 KB answer = 6760
112 Correct 2858 ms 55788 KB answer = 6788
113 Correct 2836 ms 55644 KB answer = 6632