Submission #1130795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130795		garamlee500	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	5734 ms	178336 KiB

subsequence

#include <iostream>
#include <vector>

using namespace std;

int n;

int bitCount[1<<10][1<<10];
int nums[100000];
int k[100000];
// longest ending at l, matching k bits with r
int dp[1<<10][1<<10][21]={0};
int dPindex[1<<10][1<<10][21]={0};
int bestPrev[100000];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 0; i < 1<<10; i ++){
        for (int j = 0; j < 1<<10; j++){
            bitCount[i][j] = __builtin_popcount(i&j);
        }
    }
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> nums[i];
    }

    for (int i = 0; i < n; i++){
        cin >> k[i];
    }
    int best = 0;
    int bestIndex=-1;
    for (int i = 0; i<n; i++){
        int bestToJoinUp=0;
        int bestPrevSoFar=-1;

        int li = nums[i]>>10;
        int ri = nums[i]%(1<<10);
        for (int l = 0; l < 1<<10; l++){
            if (bitCount[l][li]> k[i]){
                continue;
            }
            if (bestToJoinUp<
                              dp[l][ri][k[i]-bitCount[l][li]]
                              ){
                bestToJoinUp=dp[l][ri][k[i]-bitCount[l][li]];
                bestPrevSoFar = dPindex[l][ri][k[i]-bitCount[l][li]];
            }
        }
        if (bestToJoinUp+1>best){
            best = bestToJoinUp+1;
            bestIndex=i;
        }
        bestPrev[i]=bestPrevSoFar;
        for (int r = 0; r < (1<<10); r++){
            if (bestToJoinUp+1 > dp[li][r][bitCount[r][ri]]){
                dp[li][r][bitCount[r][ri]]=bestToJoinUp+1;

                dPindex[li][r][bitCount[r][ri]]=i;
            }

        }

    }
    cout << best << '\n';
    vector<int> result;
    for (int i = 0; i < best; i++){
        result.push_back(bestIndex+1);
        bestIndex=bestPrev[bestIndex];

    }
    std::reverse(result.begin(), result.end());
    for (int x: result){
        cout << x << ' ';

    }
    cout << '\n';

}

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