Submission #406743

#	Time	Username	Problem	Language	Result	Execution time	Memory
406743		CrouchingDragon	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2687 ms	51516 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; }

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 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 60 / 60