제출 #1130791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130791		garamlee500	Longest beautiful sequence (IZhO17_subsequence)	C++20	0 / 100	17 ms	7240 KiB

subsequence

#include <iostream>
#include <vector>

using namespace std;

int n;

int bitCount[1<<10][1<<10];
int nums[1<<20];
int k[1<<20];
// 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[1<<20];
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 (bestToJoinUp<
                              dp[l][ri][k[i]]
                              ){
                bestToJoinUp=dp[l][ri][k[i]];
                bestPrevSoFar = dPindex[l][ri][k[i]];
            }
        }
        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: 0 / 7
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60