Submission #881998

#	Time	Username	Problem	Language	Result	Execution time	Memory
881998		anton	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	6039 ms	5728 KiB

subsequence

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>

const int MAX_N = 1e5;
const int BAR = 2;
const int MAX_X = 20;
int n;


pii dp[MAX_N], back[MAX_N];
int a[MAX_N], k[MAX_N];

int popcount(int i){
    if(i==0){
        return 0;
    }
    return popcount(i & (i-1)) +1;
}

void display(pii u){
    //cout<<u.first<<" "<<u.second<<endl;
    if(u.second!=-1){
        
        cout<<u.second+1<<" ";
        display(back[u.second]);    
    }
}

signed main(){
    cin>>n;

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

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

    pii ans = pii(0, n-1);
    for(int i = n-1; i>=0; i--){
        pii res =pii(0, -1);
        for(int j = i+1; j<n; j++){
            if(popcount(a[i]&a[j]) == k[j]){
                res = max(res, dp[j]);
            }
        }
        
        
        back[i] = res;
        res.first+=1;
        

        //cout<<res.first<<" "<<res.second<<endl;

        res.second=  i;
        
        ans = max(ans, res);
        
        dp[i] = res;

    }


    cout<<ans.first<<endl;
    display(ans);
    cout<<endl;
}

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