Submission #1344744

#TimeUsernameProblemLanguageResultExecution timeMemory
1344744WarinchaiLongest beautiful sequence (IZhO17_subsequence)C++20
0 / 100
2 ms4676 KiB
#include<bits/stdc++.h>
using namespace std;

int ar[100005];
int k[100005];
pair<int,int> cnt[(1<<10)][(1<<10)][11];
int dp[100005];
int prv[100005];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>ar[i];
    for(int i=1;i<=n;i++)cin>>k[i];
    for(int i=1;i<=n;i++){
        pair<int,int> temp={0,0};
        int l=(ar[i]>>10);
        for(int j=0;j<(1<<10);j++){
            int need=k[i]-__builtin_popcount(ar[i]&j);
            if(need>=0&&need<=10)temp=max(temp,cnt[l][j][need]);
        }
        dp[i]=temp.first+1;
        prv[i]=temp.second;
        int r=(ar[i]^l);
        for(int j=0;j<(1<<10);j++){
            int have=__builtin_popcount((j<<10)&ar[i]);
            cnt[j][r][have]=max(cnt[j][r][have],{dp[i],i});
        }
    }
    pair<int,int> ans={0,0};
    for(int i=1;i<=n;i++)ans=max(ans,{dp[i],i});
    cout<<ans.first<<"\n";
    int temp=ans.second;
    vector<int>v;
    while(temp!=0){
        v.push_back(temp);
        temp=prv[temp];
    }
    reverse(v.begin(),v.end());
    for(auto x:v)cout<<x<<" ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...