oj.uz

Submission #36132

# Submission time Handle Problem Language Result Execution time Memory
36132 2017-12-06T02:53:36 Z cheater2k Longest beautiful sequence (IZhO17_subsequence) C++14
100 / 100
 5223 ms 54736 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX = (1 << 20);
const int TMP = (1 << 10) - 1;
const int N = 100005;

// 10 last bits: mask & TMP
// 10 first bits: mask >> 10

int n, a[N], k[N];
vector<int> G[MAX >> 10][11]; // G[mask][overlap]
int save[MAX][11]; // (dp, mask)
int trace[N], f[N];

void mxm(pair<int,int> &x, pair<int,int> y) {
	if (x < y) x = y;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) cin >> k[i];

	for (int mask = 0; mask < (MAX >> 10); ++mask) {
		for (int nmask = 0; nmask < (MAX >> 10); ++nmask) {
			int overlap = __builtin_popcount(mask & nmask);
			G[mask][overlap].push_back(nmask);
		}
	}

	// solve
	for (int i = 1; i <= n; ++i) {
		int dp = 0;
		int suf = (a[i] & TMP);
		int pre = (a[i] >> 10);

		for (int k2 = 0; k2 <= min(10, k[i]); ++k2) {
			int k1 = k[i] - k2;
			if (k1 > 10) continue;
			// find dp[i]
			for (int nsuf : G[suf][k2]) {
				if (dp < f[save[(pre << 10) + nsuf][k1]]) {
					dp = f[save[(pre << 10) + nsuf][k1]];
					trace[i] = save[(pre << 10) + nsuf][k1];
				}
			}
		}
		f[i] = ++dp;
		
		// update dp[i] to other dps
		for (int overlap = 0; overlap <= 10; ++overlap) {
			for (int mask : G[pre][overlap]) {
				if (f[i] > f[save[(mask << 10) + suf][overlap]]) {
					save[(mask << 10) + suf][overlap] = i;
 				}
			}
		}
	}

	int mx = 0, pos = 0;
	for (int i = 1; i <= n; ++i) if (f[i] > mx) mx = f[i], pos = i;

	printf("%d\n", mx);
	vector<int> ans;
	while(pos > 0) {
		ans.push_back(pos);
		pos = trace[pos];
	}
	reverse(ans.begin(), ans.end());
	for (int i : ans) printf("%d ", i); printf("\n");
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 54600 KB answer = 4
2 Correct 16 ms 54600 KB answer = 1
3 Correct 19 ms 54600 KB answer = 2
4 Correct 13 ms 54600 KB answer = 1
5 Correct 9 ms 54600 KB answer = 2
6 Correct 19 ms 54600 KB answer = 1
7 Correct 16 ms 54600 KB answer = 1
8 Correct 29 ms 54600 KB answer = 3
9 Correct 23 ms 54600 KB answer = 2
10 Correct 16 ms 54600 KB answer = 3
11 Correct 9 ms 54600 KB answer = 2
12 Correct 16 ms 54600 KB answer = 3
13 Correct 16 ms 54600 KB answer = 2
14 Correct 16 ms 54600 KB answer = 1
15 Correct 19 ms 54600 KB answer = 1
16 Correct 29 ms 54600 KB answer = 1
17 Correct 13 ms 54600 KB answer = 1
18 Correct 9 ms 54600 KB answer = 1
19 Correct 16 ms 54600 KB answer = 1
20 Correct 16 ms 54600 KB answer = 1
21 Correct 13 ms 54600 KB answer = 1

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 54600 KB answer = 4
2 Correct 16 ms 54600 KB answer = 1
3 Correct 19 ms 54600 KB answer = 2
4 Correct 13 ms 54600 KB answer = 1
5 Correct 9 ms 54600 KB answer = 2
6 Correct 19 ms 54600 KB answer = 1
7 Correct 16 ms 54600 KB answer = 1
8 Correct 29 ms 54600 KB answer = 3
9 Correct 23 ms 54600 KB answer = 2
10 Correct 16 ms 54600 KB answer = 3
11 Correct 9 ms 54600 KB answer = 2
12 Correct 16 ms 54600 KB answer = 3
13 Correct 16 ms 54600 KB answer = 2
14 Correct 16 ms 54600 KB answer = 1
15 Correct 19 ms 54600 KB answer = 1
16 Correct 29 ms 54600 KB answer = 1
17 Correct 13 ms 54600 KB answer = 1
18 Correct 9 ms 54600 KB answer = 1
19 Correct 16 ms 54600 KB answer = 1
20 Correct 16 ms 54600 KB answer = 1
21 Correct 13 ms 54600 KB answer = 1
22 Correct 246 ms 54600 KB answer = 358
23 Correct 226 ms 54600 KB answer = 336
24 Correct 233 ms 54600 KB answer = 339
25 Correct 236 ms 54600 KB answer = 357
26 Correct 223 ms 54600 KB answer = 354
27 Correct 193 ms 54600 KB answer = 333
28 Correct 206 ms 54600 KB answer = 314
29 Correct 199 ms 54600 KB answer = 322
30 Correct 209 ms 54600 KB answer = 339
31 Correct 206 ms 54600 KB answer = 351
32 Correct 229 ms 54600 KB answer = 1
33 Correct 223 ms 54600 KB answer = 1
34 Correct 256 ms 54600 KB answer = 1
35 Correct 226 ms 54600 KB answer = 1
36 Correct 249 ms 54600 KB answer = 1
37 Correct 199 ms 54600 KB answer = 1
38 Correct 149 ms 54600 KB answer = 1
39 Correct 176 ms 54600 KB answer = 1
40 Correct 163 ms 54600 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 54600 KB answer = 4
2 Correct 16 ms 54600 KB answer = 1
3 Correct 19 ms 54600 KB answer = 2
4 Correct 13 ms 54600 KB answer = 1
5 Correct 9 ms 54600 KB answer = 2
6 Correct 19 ms 54600 KB answer = 1
7 Correct 16 ms 54600 KB answer = 1
8 Correct 29 ms 54600 KB answer = 3
9 Correct 23 ms 54600 KB answer = 2
10 Correct 16 ms 54600 KB answer = 3
11 Correct 9 ms 54600 KB answer = 2
12 Correct 16 ms 54600 KB answer = 3
13 Correct 16 ms 54600 KB answer = 2
14 Correct 16 ms 54600 KB answer = 1
15 Correct 19 ms 54600 KB answer = 1
16 Correct 29 ms 54600 KB answer = 1
17 Correct 13 ms 54600 KB answer = 1
18 Correct 9 ms 54600 KB answer = 1
19 Correct 16 ms 54600 KB answer = 1
20 Correct 16 ms 54600 KB answer = 1
21 Correct 13 ms 54600 KB answer = 1
22 Correct 246 ms 54600 KB answer = 358
23 Correct 226 ms 54600 KB answer = 336
24 Correct 233 ms 54600 KB answer = 339
25 Correct 236 ms 54600 KB answer = 357
26 Correct 223 ms 54600 KB answer = 354
27 Correct 193 ms 54600 KB answer = 333
28 Correct 206 ms 54600 KB answer = 314
29 Correct 199 ms 54600 KB answer = 322
30 Correct 209 ms 54600 KB answer = 339
31 Correct 206 ms 54600 KB answer = 351
32 Correct 229 ms 54600 KB answer = 1
33 Correct 223 ms 54600 KB answer = 1
34 Correct 256 ms 54600 KB answer = 1
35 Correct 226 ms 54600 KB answer = 1
36 Correct 249 ms 54600 KB answer = 1
37 Correct 199 ms 54600 KB answer = 1
38 Correct 149 ms 54600 KB answer = 1
39 Correct 176 ms 54600 KB answer = 1
40 Correct 163 ms 54600 KB answer = 1
41 Correct 1856 ms 54736 KB answer = 6296
42 Correct 2033 ms 54736 KB answer = 6267
43 Correct 2009 ms 54736 KB answer = 6264
44 Correct 2099 ms 54736 KB answer = 6384
45 Correct 2123 ms 54736 KB answer = 6272
46 Correct 1793 ms 54736 KB answer = 6177
47 Correct 2009 ms 54736 KB answer = 6144
48 Correct 2403 ms 54736 KB answer = 6272
49 Correct 2016 ms 54736 KB answer = 6241
50 Correct 2005 ms 54736 KB answer = 6169
51 Correct 1443 ms 54600 KB answer = 1
52 Correct 1383 ms 54600 KB answer = 1
53 Correct 1163 ms 54600 KB answer = 1
54 Correct 1529 ms 54600 KB answer = 1
55 Correct 1213 ms 54600 KB answer = 1
56 Correct 2149 ms 54600 KB answer = 1426
57 Correct 1799 ms 54600 KB answer = 1427
58 Correct 1686 ms 54600 KB answer = 1428
59 Correct 1783 ms 54600 KB answer = 1427

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 54600 KB answer = 4
2 Correct 16 ms 54600 KB answer = 1
3 Correct 19 ms 54600 KB answer = 2
4 Correct 13 ms 54600 KB answer = 1
5 Correct 9 ms 54600 KB answer = 2
6 Correct 19 ms 54600 KB answer = 1
7 Correct 16 ms 54600 KB answer = 1
8 Correct 29 ms 54600 KB answer = 3
9 Correct 23 ms 54600 KB answer = 2
10 Correct 16 ms 54600 KB answer = 3
11 Correct 9 ms 54600 KB answer = 2
12 Correct 16 ms 54600 KB answer = 3
13 Correct 16 ms 54600 KB answer = 2
14 Correct 16 ms 54600 KB answer = 1
15 Correct 19 ms 54600 KB answer = 1
16 Correct 29 ms 54600 KB answer = 1
17 Correct 13 ms 54600 KB answer = 1
18 Correct 9 ms 54600 KB answer = 1
19 Correct 16 ms 54600 KB answer = 1
20 Correct 16 ms 54600 KB answer = 1
21 Correct 13 ms 54600 KB answer = 1
22 Correct 246 ms 54600 KB answer = 358
23 Correct 226 ms 54600 KB answer = 336
24 Correct 233 ms 54600 KB answer = 339
25 Correct 236 ms 54600 KB answer = 357
26 Correct 223 ms 54600 KB answer = 354
27 Correct 193 ms 54600 KB answer = 333
28 Correct 206 ms 54600 KB answer = 314
29 Correct 199 ms 54600 KB answer = 322
30 Correct 209 ms 54600 KB answer = 339
31 Correct 206 ms 54600 KB answer = 351
32 Correct 229 ms 54600 KB answer = 1
33 Correct 223 ms 54600 KB answer = 1
34 Correct 256 ms 54600 KB answer = 1
35 Correct 226 ms 54600 KB answer = 1
36 Correct 249 ms 54600 KB answer = 1
37 Correct 199 ms 54600 KB answer = 1
38 Correct 149 ms 54600 KB answer = 1
39 Correct 176 ms 54600 KB answer = 1
40 Correct 163 ms 54600 KB answer = 1
41 Correct 1856 ms 54736 KB answer = 6296
42 Correct 2033 ms 54736 KB answer = 6267
43 Correct 2009 ms 54736 KB answer = 6264
44 Correct 2099 ms 54736 KB answer = 6384
45 Correct 2123 ms 54736 KB answer = 6272
46 Correct 1793 ms 54736 KB answer = 6177
47 Correct 2009 ms 54736 KB answer = 6144
48 Correct 2403 ms 54736 KB answer = 6272
49 Correct 2016 ms 54736 KB answer = 6241
50 Correct 2005 ms 54736 KB answer = 6169
51 Correct 1443 ms 54600 KB answer = 1
52 Correct 1383 ms 54600 KB answer = 1
53 Correct 1163 ms 54600 KB answer = 1
54 Correct 1529 ms 54600 KB answer = 1
55 Correct 1213 ms 54600 KB answer = 1
56 Correct 2149 ms 54600 KB answer = 1426
57 Correct 1799 ms 54600 KB answer = 1427
58 Correct 1686 ms 54600 KB answer = 1428
59 Correct 1783 ms 54600 KB answer = 1427
60 Correct 4249 ms 54736 KB answer = 7034
61 Correct 4436 ms 54736 KB answer = 7045
62 Correct 4409 ms 54736 KB answer = 7147
63 Correct 4269 ms 54736 KB answer = 7038
64 Correct 4276 ms 54736 KB answer = 7169
65 Correct 4313 ms 54736 KB answer = 6735
66 Correct 4163 ms 54736 KB answer = 6713
67 Correct 4413 ms 54736 KB answer = 6748
68 Correct 4516 ms 54736 KB answer = 6607
69 Correct 4166 ms 54736 KB answer = 6722
70 Correct 4179 ms 54600 KB answer = 1
71 Correct 4206 ms 54600 KB answer = 1
72 Correct 4186 ms 54600 KB answer = 1
73 Correct 4316 ms 54600 KB answer = 1
74 Correct 4379 ms 54600 KB answer = 1
75 Correct 2936 ms 54600 KB answer = 1
76 Correct 3033 ms 54600 KB answer = 1
77 Correct 3063 ms 54600 KB answer = 1
78 Correct 3093 ms 54600 KB answer = 1
79 Correct 2316 ms 54600 KB answer = 21
80 Correct 2516 ms 54600 KB answer = 7
81 Correct 2446 ms 54600 KB answer = 3
82 Correct 2566 ms 54600 KB answer = 2
83 Correct 2809 ms 54600 KB answer = 1
84 Correct 3306 ms 54600 KB answer = 1
85 Correct 3159 ms 54600 KB answer = 1
86 Correct 2249 ms 54600 KB answer = 11
87 Correct 2233 ms 54600 KB answer = 11
88 Correct 2416 ms 54600 KB answer = 6
89 Correct 2776 ms 54600 KB answer = 4
90 Correct 2823 ms 54600 KB answer = 2
91 Correct 2999 ms 54600 KB answer = 2
92 Correct 3153 ms 54600 KB answer = 2
93 Correct 4369 ms 54736 KB answer = 7211
94 Correct 4203 ms 54736 KB answer = 7032
95 Correct 4703 ms 54736 KB answer = 7092
96 Correct 5013 ms 54736 KB answer = 14167
97 Correct 5059 ms 54736 KB answer = 14159
98 Correct 4963 ms 54736 KB answer = 14125
99 Correct 5119 ms 54736 KB answer = 14121
100 Correct 5223 ms 54736 KB answer = 14010
101 Correct 5129 ms 54736 KB answer = 13976
102 Correct 3123 ms 54600 KB answer = 3
103 Correct 3053 ms 54600 KB answer = 2
104 Correct 2769 ms 54600 KB answer = 3
105 Correct 2983 ms 54600 KB answer = 2
106 Correct 2723 ms 54600 KB answer = 3
107 Correct 2839 ms 54600 KB answer = 4
108 Correct 2539 ms 54600 KB answer = 5
109 Correct 2226 ms 54600 KB answer = 8
110 Correct 2045 ms 54600 KB answer = 22
111 Correct 4293 ms 54736 KB answer = 6760
112 Correct 4113 ms 54736 KB answer = 6788
113 Correct 4296 ms 54736 KB answer = 6632