Submission #824088

#	Time	Username	Problem	Language	Result	Execution time	Memory
824088		phi	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4365 ms	174864 KiB

subsequence

#include <iostream>
#include <vector>
#include <array>

using namespace std;

int main() {
    int n;
    cin >> n;

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

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

    constexpr int mk = 20;
    constexpr int b = mk / 2;
    constexpr int mask = (1 << b) - 1;

    array<array<array<int, mk + 1>, 1 << b>, 1 << b> dp = {};
    array<array<array<int, mk + 1>, 1 << b>, 1 << b> current = {};
    vector<int> prev(n);

    int ans = -1;
    int end = -1;

    for (int i = 0; i < n; i++) {
        int lbs = 1;
        int p = -1;

        for (int j = 0; j < (1 << b); j++) {
            if (k[i] < __builtin_popcount(j & a[i])) continue;
            int c = dp[j][a[i] >> b][k[i] - __builtin_popcount(j & a[i])];
            if (lbs < c + 1) {
                lbs = c + 1;
                p = current[j][a[i] >> b][k[i] - __builtin_popcount(j & a[i])];
            }
        }

        for (int j = 0; j < (1 << b); j++) {
            int c = __builtin_popcount(j & (a[i] >> b));
            if (dp[a[i] & mask][j][c] < lbs) {
                dp[a[i] & mask][j][c] = lbs;
                current[a[i] & mask][j][c] = i;
            }
        }

        prev[i] = p;

        if (lbs > ans) {
            ans = lbs;
            end = i;
        }
    }

    vector<int> arr;
    while (end != -1) {
        arr.push_back(end + 1);
        end = prev[end];
    }

    cout << arr.size() << "\n";
    for (int i = arr.size() - 1; i >= 0; i--)
        cout << arr[i] << " \n"[i == 0];

    return 0;
}

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