Submission #1232593

#TimeUsernameProblemLanguageResultExecution timeMemory
1232593ereringLongest beautiful sequence (IZhO17_subsequence)C++17
0 / 100
11 ms5956 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define endl '\n'
#define int long long
const int N=1e5+5,inf=2e9,MOD=1e9+7;
int a[N],k[N],ans[N],cnt[N],par[N];
pair<int,int> dp[(1<<10)+5][(1<<10)+5][21];
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for(int i=0;i<(1<<10);i++){
        int x=i;
        while(x>0){
            if(x%2)cnt[i]++;
            x/=2;
        }
    }
    int n; cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        par[i]=-1;
    }
    for(int i=0;i<n;i++)cin>>k[i];
    int sol=0;
    for(int i=0;i<n;i++){
        ans[i]=1;
        for(int mask=0;mask<(1<<10);mask++){
            int need=k[i]-cnt[a[i]&mask];
            if(ans[i]<dp[mask][(a[i]>>10)][need].first+1){
                ans[i]=dp[mask][(a[i]>>10)][need].first+1;
                par[i]=dp[mask][(a[i]>>10)][need].second;
            }
        }
        for(int mask=0;mask<(1<<10);mask++){
            int ones=(1<<10)-1;
            dp[a[i]&ones][mask][mask&(a[i]>>10)]=max(dp[a[i]&ones][mask][mask&(a[i]>>10)],{ans[i],i});
        }
        sol=max(sol,ans[i]);
    }
    vector<int> final;
    for(int i=n-1;i>=0;i--){
        if(ans[i]==sol){
           // cout<<i<<' '<<par[i]<<endl;
            int x=i;
            while(par[x]!=-1){
                final.pb(x+1);
                x=par[x];
            }
            final.pb(x+1);
            break;
        }
    }
    cout<<sol<<endl;
    for(int i=final.size()-1;i>=0;i--)cout<<final[i]<<' ';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...