Submission #406738

# Submission time Handle Problem Language Result Execution time Memory
406738 2021-05-18T04:00:18 Z CrouchingDragon Longest beautiful sequence (IZhO17_subsequence) C++14
0 / 100
72 ms 100192 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; }

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;

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

    int dp[1 << L][1 << L][L + 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);
}

# Verdict Execution time Memory Grader output
1 Correct 26 ms 49484 KB answer = 4
2 Correct 24 ms 49528 KB answer = 1
3 Correct 22 ms 49528 KB answer = 2
4 Correct 23 ms 49492 KB answer = 1
5 Correct 22 ms 49484 KB answer = 2
6 Correct 22 ms 49524 KB answer = 1
7 Correct 23 ms 49484 KB answer = 1
8 Correct 23 ms 49504 KB answer = 3
9 Correct 24 ms 49552 KB answer = 2
10 Correct 25 ms 49456 KB answer = 3
11 Correct 24 ms 49484 KB answer = 2
12 Correct 28 ms 49456 KB answer = 3
13 Correct 23 ms 49456 KB answer = 2
14 Correct 23 ms 49484 KB answer = 1
15 Correct 22 ms 49484 KB answer = 1
16 Correct 23 ms 49476 KB answer = 1
17 Correct 24 ms 49512 KB answer = 1
18 Runtime error 72 ms 100192 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 26 ms 49484 KB answer = 4
2 Correct 24 ms 49528 KB answer = 1
3 Correct 22 ms 49528 KB answer = 2
4 Correct 23 ms 49492 KB answer = 1
5 Correct 22 ms 49484 KB answer = 2
6 Correct 22 ms 49524 KB answer = 1
7 Correct 23 ms 49484 KB answer = 1
8 Correct 23 ms 49504 KB answer = 3
9 Correct 24 ms 49552 KB answer = 2
10 Correct 25 ms 49456 KB answer = 3
11 Correct 24 ms 49484 KB answer = 2
12 Correct 28 ms 49456 KB answer = 3
13 Correct 23 ms 49456 KB answer = 2
14 Correct 23 ms 49484 KB answer = 1
15 Correct 22 ms 49484 KB answer = 1
16 Correct 23 ms 49476 KB answer = 1
17 Correct 24 ms 49512 KB answer = 1
18 Runtime error 72 ms 100192 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 26 ms 49484 KB answer = 4
2 Correct 24 ms 49528 KB answer = 1
3 Correct 22 ms 49528 KB answer = 2
4 Correct 23 ms 49492 KB answer = 1
5 Correct 22 ms 49484 KB answer = 2
6 Correct 22 ms 49524 KB answer = 1
7 Correct 23 ms 49484 KB answer = 1
8 Correct 23 ms 49504 KB answer = 3
9 Correct 24 ms 49552 KB answer = 2
10 Correct 25 ms 49456 KB answer = 3
11 Correct 24 ms 49484 KB answer = 2
12 Correct 28 ms 49456 KB answer = 3
13 Correct 23 ms 49456 KB answer = 2
14 Correct 23 ms 49484 KB answer = 1
15 Correct 22 ms 49484 KB answer = 1
16 Correct 23 ms 49476 KB answer = 1
17 Correct 24 ms 49512 KB answer = 1
18 Runtime error 72 ms 100192 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 26 ms 49484 KB answer = 4
2 Correct 24 ms 49528 KB answer = 1
3 Correct 22 ms 49528 KB answer = 2
4 Correct 23 ms 49492 KB answer = 1
5 Correct 22 ms 49484 KB answer = 2
6 Correct 22 ms 49524 KB answer = 1
7 Correct 23 ms 49484 KB answer = 1
8 Correct 23 ms 49504 KB answer = 3
9 Correct 24 ms 49552 KB answer = 2
10 Correct 25 ms 49456 KB answer = 3
11 Correct 24 ms 49484 KB answer = 2
12 Correct 28 ms 49456 KB answer = 3
13 Correct 23 ms 49456 KB answer = 2
14 Correct 23 ms 49484 KB answer = 1
15 Correct 22 ms 49484 KB answer = 1
16 Correct 23 ms 49476 KB answer = 1
17 Correct 24 ms 49512 KB answer = 1
18 Runtime error 72 ms 100192 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -