Submission #1306962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306962		Nipphitch	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	1946 ms	96232 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define pii pair <int,int>
#define ff first 
#define ss second 
const int N=1e5;
const int M=10;

int n,a[N+1],k[N+1],bc[(1<<M)+1][(1<<M)+1],prv[N],ans,best_i;
pii dp[(1<<M)+1][(1<<M)+1][M+1];
vector <int> res;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    for(int i=0;i<(1<<M);i++) for(int j=0;j<(1<<M);j++) bc[i][j]=__builtin_popcount(i&j);
    cin >> n;
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++) cin >> k[i];
    for(int i=0;i<n;i++) prv[i]=i;
    for(int i=0;i<n;i++){
        int l=a[i]>>M,r=a[i]%(1<<M),lbs=1;
        for(int mask=0;mask<(1<<M);mask++){
            int need=k[i]-bc[mask][l];
            if(need<0 || need>M) continue;
            if(dp[mask][r][need].ff+1>lbs){
                lbs=dp[mask][r][need].ff+1;
                prv[i]=dp[mask][r][need].ss;
            }
        }
        if(lbs>ans){
            ans=lbs;
            best_i=i;
        }
        for(int mask=0;mask<(1<<M);mask++){
            pii &new_state=dp[l][mask][bc[r][mask]];
            if(lbs>new_state.ff){
                new_state.ff=lbs;
                new_state.ss=i;
            }
        }
    }
    while(prv[best_i]!=best_i){
        res.push_back(best_i);
        best_i=prv[best_i];
    }
    res.push_back(best_i);
    reverse(res.begin(),res.end());
    cout << ans << "\n";
    for(int x:res) cout << x+1 << " ";
}

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