Submission #681837

#TimeUsernameProblemLanguageResultExecution timeMemory
681837KarukLongest beautiful sequence (IZhO17_subsequence)C++14
7 / 100
187 ms81916 KiB
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
const int M=(1<<10);
pair<int,int>dp[M][M][10];///{score,index} [fixed left][supposed right][common right with supposed right]
int previous[N+1];
int main() {
    int n;
    cin>>n;
    int a[n+1];
    int k[n+1];
    for(int i=1; i<=n; i++)cin>>a[i];
    for(int i=1; i<=n; i++)cin>>k[i];
    pair<int,int>ans={0,0};
    for(int i=1; i<=n; i++) {
        pair<int,int>curans= {0,0};
        int left=(a[i]>>10),right=a[i]&((1<<10)-1);
        for(int j=0; j<M; j++) {
            int rem=k[i]-__builtin_popcount(j&left);
            if(rem<0 || rem>10)continue;
            curans=max(curans,dp[j][right][rem]);
        }
        curans.first++;
        previous[i]=curans.second;
        curans.second=i;
        ans=max(ans,curans);
        for(int j=0;j<M;j++) {
            int x=__builtin_popcount(j&right);
            dp[left][j][x]=max(dp[left][j][x],curans);
        }
    }
    int cur=ans.second;
    vector<int>anss;
    while(cur>0) {
        anss.push_back(cur);
        cur=previous[cur];
    }
    reverse(anss.begin(),anss.end());
    cout<<anss.size()<<endl;
    for(int i:anss)cout<<i<<' ';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...