Submission #681836

#	Time	Username	Problem	Language	Result	Execution time	Memory
681836		Karuk	Longest beautiful sequence (IZhO17_subsequence)	C++14	7 / 100	238 ms	81864 KiB

subsequence

#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;
    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;
}

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