oj.uz

Submission #406743

# Submission time Handle Problem Language Result Execution time Memory
406743 2021-05-18T04:04:32 Z CrouchingDragon Longest beautiful sequence (IZhO17_subsequence) C++17
100 / 100
 2687 ms 51516 KB 
#include "bits/stdc++.h"

using namespace std;

#define endl '\n'
#define debug(x) cerr << #x << " == " << (x) << '\n';
#define all(x) begin(x), end(x)

using ll = long long;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

template<typename T>
bool chmax(T& x, T y) { return x < y ? (x = y, true) : false; }

constexpr int K = 20, L = 10;
int dp[1 << L][1 << L][L + 1];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> a(n), k(n);
    for (auto& x : a) cin >> x;
    for (auto& x : k) cin >> x;

    vector<int> popcount(1 << K);
    for (int mask = 1; mask < (1 << K); ++mask) {
        popcount[mask] = 1 + popcount[mask & (mask - 1)];
    }

    vector<int> p(n + 1), opt(n + 1);
    int m = 0, last = 0;

    for (int i = 1; i <= n; ++i) {
        int left = a[i - 1] & ((1 << L) - 1), right = a[i - 1] >> L;
        for (int mask = 0; mask < (1 << L); ++mask) {
            int x = k[i - 1] - popcount[mask & left];
            if (0 <= x && x <= L && chmax(opt[i], opt[dp[mask][right][x]])) {
                p[i] = dp[mask][right][x];
            }
        }
        ++opt[i];
        for (int mask = 0; mask < (1 << L); ++mask) {
            int& j = dp[left][mask][popcount[mask & right]];
            if (opt[j] < opt[i]) j = i;
        }
        if (chmax(m, opt[i])) last = i;
    }

    vector<int> I;
    while (last) {
        I.push_back(last);
        last = p[last];
    }
    reverse(all(I));
    assert((int)I.size() == m);

    cout << m << endl;
    for (int j = 0; j < m; ++j) {
        cout << I[j] << "\n "[j + 1 < m];
    }

    exit(0);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4684 KB answer = 4
2 Correct 4 ms 4556 KB answer = 1
3 Correct 4 ms 4556 KB answer = 2
4 Correct 4 ms 4428 KB answer = 1
5 Correct 6 ms 4556 KB answer = 2
6 Correct 4 ms 4556 KB answer = 1
7 Correct 4 ms 4428 KB answer = 1
8 Correct 7 ms 5188 KB answer = 3
9 Correct 8 ms 5068 KB answer = 2
10 Correct 6 ms 5068 KB answer = 3
11 Correct 6 ms 5068 KB answer = 2
12 Correct 7 ms 5196 KB answer = 3
13 Correct 7 ms 5068 KB answer = 2
14 Correct 10 ms 4940 KB answer = 1
15 Correct 9 ms 5196 KB answer = 1
16 Correct 11 ms 5208 KB answer = 1
17 Correct 8 ms 5068 KB answer = 1
18 Correct 5 ms 4952 KB answer = 1
19 Correct 5 ms 4940 KB answer = 1
20 Correct 5 ms 4928 KB answer = 1
21 Correct 5 ms 4940 KB answer = 1

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4684 KB answer = 4
2 Correct 4 ms 4556 KB answer = 1
3 Correct 4 ms 4556 KB answer = 2
4 Correct 4 ms 4428 KB answer = 1
5 Correct 6 ms 4556 KB answer = 2
6 Correct 4 ms 4556 KB answer = 1
7 Correct 4 ms 4428 KB answer = 1
8 Correct 7 ms 5188 KB answer = 3
9 Correct 8 ms 5068 KB answer = 2
10 Correct 6 ms 5068 KB answer = 3
11 Correct 6 ms 5068 KB answer = 2
12 Correct 7 ms 5196 KB answer = 3
13 Correct 7 ms 5068 KB answer = 2
14 Correct 10 ms 4940 KB answer = 1
15 Correct 9 ms 5196 KB answer = 1
16 Correct 11 ms 5208 KB answer = 1
17 Correct 8 ms 5068 KB answer = 1
18 Correct 5 ms 4952 KB answer = 1
19 Correct 5 ms 4940 KB answer = 1
20 Correct 5 ms 4928 KB answer = 1
21 Correct 5 ms 4940 KB answer = 1
22 Correct 121 ms 49364 KB answer = 358
23 Correct 122 ms 49228 KB answer = 336
24 Correct 124 ms 49292 KB answer = 339
25 Correct 122 ms 49416 KB answer = 357
26 Correct 122 ms 49224 KB answer = 354
27 Correct 112 ms 47100 KB answer = 333
28 Correct 116 ms 46868 KB answer = 314
29 Correct 114 ms 46348 KB answer = 322
30 Correct 121 ms 46916 KB answer = 339
31 Correct 121 ms 47144 KB answer = 351
32 Correct 157 ms 47360 KB answer = 1
33 Correct 163 ms 47560 KB answer = 1
34 Correct 149 ms 47000 KB answer = 1
35 Correct 159 ms 47688 KB answer = 1
36 Correct 167 ms 47300 KB answer = 1
37 Correct 73 ms 33336 KB answer = 1
38 Correct 88 ms 33180 KB answer = 1
39 Correct 68 ms 33108 KB answer = 1
40 Correct 82 ms 33092 KB answer = 1

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4684 KB answer = 4
2 Correct 4 ms 4556 KB answer = 1
3 Correct 4 ms 4556 KB answer = 2
4 Correct 4 ms 4428 KB answer = 1
5 Correct 6 ms 4556 KB answer = 2
6 Correct 4 ms 4556 KB answer = 1
7 Correct 4 ms 4428 KB answer = 1
8 Correct 7 ms 5188 KB answer = 3
9 Correct 8 ms 5068 KB answer = 2
10 Correct 6 ms 5068 KB answer = 3
11 Correct 6 ms 5068 KB answer = 2
12 Correct 7 ms 5196 KB answer = 3
13 Correct 7 ms 5068 KB answer = 2
14 Correct 10 ms 4940 KB answer = 1
15 Correct 9 ms 5196 KB answer = 1
16 Correct 11 ms 5208 KB answer = 1
17 Correct 8 ms 5068 KB answer = 1
18 Correct 5 ms 4952 KB answer = 1
19 Correct 5 ms 4940 KB answer = 1
20 Correct 5 ms 4928 KB answer = 1
21 Correct 5 ms 4940 KB answer = 1
22 Correct 121 ms 49364 KB answer = 358
23 Correct 122 ms 49228 KB answer = 336
24 Correct 124 ms 49292 KB answer = 339
25 Correct 122 ms 49416 KB answer = 357
26 Correct 122 ms 49224 KB answer = 354
27 Correct 112 ms 47100 KB answer = 333
28 Correct 116 ms 46868 KB answer = 314
29 Correct 114 ms 46348 KB answer = 322
30 Correct 121 ms 46916 KB answer = 339
31 Correct 121 ms 47144 KB answer = 351
32 Correct 157 ms 47360 KB answer = 1
33 Correct 163 ms 47560 KB answer = 1
34 Correct 149 ms 47000 KB answer = 1
35 Correct 159 ms 47688 KB answer = 1
36 Correct 167 ms 47300 KB answer = 1
37 Correct 73 ms 33336 KB answer = 1
38 Correct 88 ms 33180 KB answer = 1
39 Correct 68 ms 33108 KB answer = 1
40 Correct 82 ms 33092 KB answer = 1
41 Correct 749 ms 17600 KB answer = 6296
42 Correct 741 ms 17596 KB answer = 6267
43 Correct 719 ms 17596 KB answer = 6264
44 Correct 728 ms 17668 KB answer = 6384
45 Correct 768 ms 17592 KB answer = 6272
46 Correct 640 ms 13252 KB answer = 6177
47 Correct 695 ms 13256 KB answer = 6144
48 Correct 648 ms 13264 KB answer = 6272
49 Correct 623 ms 13260 KB answer = 6241
50 Correct 635 ms 13260 KB answer = 6169
51 Correct 339 ms 9668 KB answer = 1
52 Correct 326 ms 9608 KB answer = 1
53 Correct 395 ms 9612 KB answer = 1
54 Correct 325 ms 9664 KB answer = 1
55 Correct 404 ms 9552 KB answer = 1
56 Correct 865 ms 9612 KB answer = 1426
57 Correct 893 ms 9692 KB answer = 1427
58 Correct 874 ms 9612 KB answer = 1428
59 Correct 876 ms 9616 KB answer = 1427

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4684 KB answer = 4
2 Correct 4 ms 4556 KB answer = 1
3 Correct 4 ms 4556 KB answer = 2
4 Correct 4 ms 4428 KB answer = 1
5 Correct 6 ms 4556 KB answer = 2
6 Correct 4 ms 4556 KB answer = 1
7 Correct 4 ms 4428 KB answer = 1
8 Correct 7 ms 5188 KB answer = 3
9 Correct 8 ms 5068 KB answer = 2
10 Correct 6 ms 5068 KB answer = 3
11 Correct 6 ms 5068 KB answer = 2
12 Correct 7 ms 5196 KB answer = 3
13 Correct 7 ms 5068 KB answer = 2
14 Correct 10 ms 4940 KB answer = 1
15 Correct 9 ms 5196 KB answer = 1
16 Correct 11 ms 5208 KB answer = 1
17 Correct 8 ms 5068 KB answer = 1
18 Correct 5 ms 4952 KB answer = 1
19 Correct 5 ms 4940 KB answer = 1
20 Correct 5 ms 4928 KB answer = 1
21 Correct 5 ms 4940 KB answer = 1
22 Correct 121 ms 49364 KB answer = 358
23 Correct 122 ms 49228 KB answer = 336
24 Correct 124 ms 49292 KB answer = 339
25 Correct 122 ms 49416 KB answer = 357
26 Correct 122 ms 49224 KB answer = 354
27 Correct 112 ms 47100 KB answer = 333
28 Correct 116 ms 46868 KB answer = 314
29 Correct 114 ms 46348 KB answer = 322
30 Correct 121 ms 46916 KB answer = 339
31 Correct 121 ms 47144 KB answer = 351
32 Correct 157 ms 47360 KB answer = 1
33 Correct 163 ms 47560 KB answer = 1
34 Correct 149 ms 47000 KB answer = 1
35 Correct 159 ms 47688 KB answer = 1
36 Correct 167 ms 47300 KB answer = 1
37 Correct 73 ms 33336 KB answer = 1
38 Correct 88 ms 33180 KB answer = 1
39 Correct 68 ms 33108 KB answer = 1
40 Correct 82 ms 33092 KB answer = 1
41 Correct 749 ms 17600 KB answer = 6296
42 Correct 741 ms 17596 KB answer = 6267
43 Correct 719 ms 17596 KB answer = 6264
44 Correct 728 ms 17668 KB answer = 6384
45 Correct 768 ms 17592 KB answer = 6272
46 Correct 640 ms 13252 KB answer = 6177
47 Correct 695 ms 13256 KB answer = 6144
48 Correct 648 ms 13264 KB answer = 6272
49 Correct 623 ms 13260 KB answer = 6241
50 Correct 635 ms 13260 KB answer = 6169
51 Correct 339 ms 9668 KB answer = 1
52 Correct 326 ms 9608 KB answer = 1
53 Correct 395 ms 9612 KB answer = 1
54 Correct 325 ms 9664 KB answer = 1
55 Correct 404 ms 9552 KB answer = 1
56 Correct 865 ms 9612 KB answer = 1426
57 Correct 893 ms 9692 KB answer = 1427
58 Correct 874 ms 9612 KB answer = 1428
59 Correct 876 ms 9616 KB answer = 1427
60 Correct 1936 ms 51384 KB answer = 7034
61 Correct 1903 ms 51380 KB answer = 7045
62 Correct 1956 ms 51460 KB answer = 7147
63 Correct 1939 ms 51456 KB answer = 7038
64 Correct 1896 ms 51460 KB answer = 7169
65 Correct 1898 ms 51380 KB answer = 6735
66 Correct 1888 ms 51296 KB answer = 6713
67 Correct 1900 ms 51232 KB answer = 6748
68 Correct 1867 ms 51468 KB answer = 6607
69 Correct 1884 ms 51392 KB answer = 6722
70 Correct 2657 ms 51436 KB answer = 1
71 Correct 2649 ms 51344 KB answer = 1
72 Correct 2680 ms 51412 KB answer = 1
73 Correct 2687 ms 51340 KB answer = 1
74 Correct 2667 ms 51300 KB answer = 1
75 Correct 1004 ms 51356 KB answer = 1
76 Correct 947 ms 51348 KB answer = 1
77 Correct 967 ms 51340 KB answer = 1
78 Correct 979 ms 51268 KB answer = 1
79 Correct 874 ms 23972 KB answer = 21
80 Correct 912 ms 35012 KB answer = 7
81 Correct 931 ms 44056 KB answer = 3
82 Correct 940 ms 49140 KB answer = 2
83 Correct 965 ms 49064 KB answer = 1
84 Correct 967 ms 50896 KB answer = 1
85 Correct 984 ms 51268 KB answer = 1
86 Correct 829 ms 23760 KB answer = 11
87 Correct 878 ms 34984 KB answer = 11
88 Correct 941 ms 44020 KB answer = 6
89 Correct 943 ms 49184 KB answer = 4
90 Correct 979 ms 49104 KB answer = 2
91 Correct 961 ms 50908 KB answer = 2
92 Correct 995 ms 51368 KB answer = 2
93 Correct 1910 ms 51424 KB answer = 7211
94 Correct 1898 ms 51412 KB answer = 7032
95 Correct 1896 ms 51412 KB answer = 7092
96 Correct 2527 ms 51512 KB answer = 14167
97 Correct 2544 ms 51508 KB answer = 14159
98 Correct 2545 ms 51516 KB answer = 14125
99 Correct 2557 ms 51512 KB answer = 14121
100 Correct 2538 ms 51512 KB answer = 14010
101 Correct 2570 ms 51512 KB answer = 13976
102 Correct 991 ms 51372 KB answer = 3
103 Correct 953 ms 50860 KB answer = 2
104 Correct 956 ms 48996 KB answer = 3
105 Correct 967 ms 51364 KB answer = 2
106 Correct 973 ms 51032 KB answer = 3
107 Correct 890 ms 48976 KB answer = 4
108 Correct 823 ms 43988 KB answer = 5
109 Correct 733 ms 34908 KB answer = 8
110 Correct 638 ms 23848 KB answer = 22
111 Correct 1909 ms 51316 KB answer = 6760
112 Correct 1925 ms 51388 KB answer = 6788
113 Correct 2047 ms 51224 KB answer = 6632