제출 #1336535

#제출 시각아이디문제언어결과실행 시간메모리
1336535sh_qaxxorov_571Longest beautiful sequence (IZhO17_subsequence)C++20
0 / 100
41 ms90768 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int dp[1 << 10][1 << 10][21];
int parent_idx[1 << 10][1 << 10][21];
int backtrack[100005];
int a[100005], k[100005];

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

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> k[i];

    for (int i = 0; i < (1 << 10); i++) {
        for (int j = 0; j < (1 << 10); j++) {
            for (int bit = 0; bit <= 20; bit++) {
                dp[i][j][bit] = 0;
            }
        }
    }

    int best_len = 0;
    int last_pos = 0;

    for (int i = 1; i <= n; i++) {
        int cur_a = a[i];
        int low = cur_a & 1023;
        int high = cur_a >> 10;
        
        int current_max = 1;
        int p_idx = 0;

        if (i > 1) {
            for (int prev_low = 0; prev_low < 1024; prev_low++) {
                int common_low = __builtin_popcount(low & prev_low);
                int needed_high = k[i] - common_low;
                if (needed_high >= 0 && needed_high <= 10) {
                    if (dp[high][prev_low][needed_high] + 1 > current_max) {
                        current_max = dp[high][prev_low][needed_high] + 1;
                        p_idx = parent_idx[high][prev_low][needed_high];
                    }
                }
            }
        }

        backtrack[i] = p_idx;
        if (current_max > best_len) {
            best_len = current_max;
            last_pos = i;
        }

        int cur_high_pop = __builtin_popcount(high);
        for (int next_high = 0; next_high < 1024; next_high++) {
            int common_high = __builtin_popcount(high & next_high);
            if (current_max > dp[next_high][low][common_high]) {
                dp[next_high][low][common_high] = current_max;
                parent_idx[next_high][low][common_high] = i;
            }
        }
    }

    cout << best_len << "\n";
    vector<int> res;
    while (last_pos != 0) {
        res.push_back(a[last_pos]);
        last_pos = backtrack[last_pos];
    }
    reverse(res.begin(), res.end());

    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << (i == res.size() - 1 ? "" : " ");
    }
    cout << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...