Submission #706403

#	Time	Username	Problem	Language	Result	Execution time	Memory
706403		piOOE	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	3 ms	596 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int A = 10;

pair<int, int> dp[1 << A][A][1 << A];
int best[1 << A * 2];

pair<int, int> query(int x, int k) {
    int first = x & ((1 << A) - 1);
    int second = x >> A;
    pair<int, int> ans{0, -1};

    for (int p = 0; p < (1 << A); ++p) {
        int need = k - __builtin_popcount(first & p);

        if (need >= 0 && dp[p][need][second].first != 0) {
            ans = max(ans, dp[p][need][second]);
        }
    }

    return ans;
}

void update(int x, int k, int id) {
    if (best[x] >= k) {
        return;
    }

    best[x] = k;


    int first = x & ((1 << A) - 1);
    int second = x >> A;

    for (int p = 0; p < (1 << A); ++p) {
        int pop = __builtin_popcount(p & second);

        dp[first][pop][p] = max(dp[first][pop][p], {k, id});
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n), k(n);

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    for (int i = 0; i < n; ++i) {
        cin >> k[i];
    }

    pair<int, int> ans{};

    vector<int> par(n, -1);

    for (int i = 0; i < n; ++i) {
        auto [x, p] = query(a[i], k[i]);
        x += 1;
        par[i] = p;

        ans = max(ans, {x, i});

        update(a[i], x, i);
    }

    cout << ans.first << '\n';

    int x = ans.second;

    vector<int> res;

    while (x != -1) {
        res.push_back(x);
        x = par[x];
    }

    reverse(res.begin(), res.end());

    for (int v : res) {
        cout << v + 1 << ' ';
    }

    cout << '\n';

    return 0;
}

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