Submission #93881

#	Time	Username	Problem	Language	Result	Execution time	Memory
93881		dalgerok	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3338 ms	94396 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;


const int N = 1e5 + 5, M = (1 << 20), K = (1 << 10);




int n, a[N], k[N], cnt[M], pr[N];
int dp[K][11][K], pos[K][11][K];
int ans, ans_pos;



int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    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 < M; i++){
        cnt[i] = __builtin_popcount(i);
    }
    for(int i = 1; i <= n; i++){
        int mask1 = (a[i] >> 10),
            mask2 = (a[i] & (K - 1));
        int cur = 0, cur_pos = 0;
        for(int mask = 0; mask < K; mask++){
            int need = k[i] - cnt[(mask1 & mask)];
            if(0 <= need && need <= 10){
                if(dp[mask][need][mask2] > cur){
                    cur = dp[mask][need][mask2];
                    cur_pos = pos[mask][need][mask2];
                }
            }
        }
        cur += 1;
        if(cur > ans){
            ans = cur;
            ans_pos = i;
        }
        pr[i] = cur_pos;
        for(int mask = 0; mask < K; mask++){
            int dif = cnt[(mask2 & mask)];
            if(dp[mask1][dif][mask] < cur){
                dp[mask1][dif][mask] = cur;
                pos[mask1][dif][mask] = i;
            }
        }
    }
    vector < int > anss;
    while(ans_pos > 0){
        anss.push_back(ans_pos);
        ans_pos = pr[ans_pos];
    }
    reverse(anss.begin(), anss.end());
    cout << (int)anss.size() << "\n";
    for(auto it : anss){
        cout << it << " ";
    }
}

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