Submission #406693

#	Time	Username	Problem	Language	Result	Execution time	Memory
406693		CrouchingDragon	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3951 ms	96968 KiB

subsequence

#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)];
    }

    pair<int, int> dp[1 << L][1 << L][L + 1];

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

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

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

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

    exit(0);
}

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 60 / 60