Submission #681839

#	Time	Username	Problem	Language	Result	Execution time	Memory
681839		Karuk	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5138 ms	92116 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
int max(int a,int b) {
    return a>b?a:b;
}
const int N=1e5+1;
const int M=(1<<10);
pair<int,int>dp[M][M][11];///{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;
}

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