Submission #1217804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217804		sam230609	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	3531 ms	100844 KiB

subsequence

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5+1,M=1024;
int n,m,num[N],dif[N],b[M][N],par[N],res=1,ans=0;
pair<int,int> dp[M][M][11];
signed main(){
    cin >>n;
    for(int i=1;i<=n;i++) cin >>num[i];
    for(int i=1;i<=n;i++) cin >>dif[i];
    for(int i=0;i<M;i++)
        for(int j=i;j<M;j++)
            b[i][j]=b[j][i]=__builtin_popcount(i&j);
    for(int i=1;i<=n;i++){
    	int l=num[i]>>10,r=num[i]%(1<<10);
    	pair<int,int> tmp={0,0};
    	for(int j=0;j<M;j++){
    		int &cur=b[l][j],tar=dif[i]-cur;
    		if(tar<0 || tar>10) continue;
    		if(dp[j][r][tar].fi>tmp.fi) tmp=dp[j][r][tar];
    	}tmp.fi++; par[i]=tmp.se; tmp.se=i;
    	if(tmp.fi>ans) res=i,ans=tmp.fi;
    	for(int j=0;j<M;j++){
    		int &cur=b[r][j];
    		if(dp[l][j][cur].fi<tmp.fi) dp[l][j][cur]=tmp;
    	}
    }int x=ans;
    while(res>0) num[x--]=res,res=par[res];
    cout <<ans<<"\n";
    for(int i=1;i<=ans;i++) cout <<num[i]<<" ";
}

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