Submission #934710

#	Time	Username	Problem	Language	Result	Execution time	Memory
934710		amirhoseinfar1385	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5249 ms	93236 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxk=22;
int all[maxn],dp[(1<<10)][(1<<10)][maxk],n,allb[maxn],res[maxn];
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>all[i];
	}
	for(int i=1;i<=n;i++){
		cin>>allb[i];
	}
	for(int i=1;i<=n;i++){
		int first=(all[i]&((1<<10)-1));
		int second=(all[i]>>10);
		int mx=0,btf=0,bts=0;
		for(int j=0;j<(1<<10);j++){
			btf=__builtin_popcount(first&j);
			if(btf>allb[i]){
				continue;
			}
			mx=max(mx,dp[j][second][allb[i]-btf]);
		}
		res[i]=mx+1;
		for(int j=0;j<(1<<10);j++){
			bts=__builtin_popcount(second&j);
			dp[first][j][bts]=max(dp[first][j][bts],res[i]);
		}
	}
	vector<int>mainres;
	int mx=0,last=0;
	for(int i=1;i<=n;i++){
		if(res[i]>mx){
			last=i;
			mx=res[i];
		}
	}
	mainres.push_back(last);
	int f=last;
	while(res[last]!=1){
		f=last;
		for(int i=last-1;i>=1;i--){
			if(res[i]==res[last]-1&&__builtin_popcount(all[last]&all[i])==allb[last]){
				last=i;
				mainres.push_back(last);
				break;
			}
		}
		if(f==last){
			assert(0);
		}
	}
	reverse(mainres.begin(),mainres.end());
	int sz=mainres.size();
	cout<<sz<<"\n";
	for(auto x:mainres){
		cout<<x<<" ";
	}
	cout<<"\n";
}

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