Submission #1130884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130884		nlkn	Longest beautiful sequence (IZhO17_subsequence)	C++20	7 / 100	6091 ms	8564 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n; cin >> n;
	int a[n],k[n],maxai=0,ans=1,ind=0;
	for(int i=0; i<n; i++)cin>>a[i];
	for(int i=0; i<n; i++)maxai=max(a[i],maxai);
	for(int i=0; i<n; i++)cin>>k[i];
	vector<int> dp(maxai+1),curr(maxai+1,-1),last(n,-1);
	dp[a[0]]=1;
	curr[a[0]]=0;
	for(int i=1; i<n; i++){
		if(curr[a[i]]==-1)curr[a[i]]=i;
		for(int j=0; j<=maxai; j++){
			if(__builtin_popcount(a[i]&j)==k[i]){
				if(dp[a[i]]<dp[j]+1){
					last[i]=curr[j];
	//				cout<<j<<" "<<i<<" "<<last[i]<<endl;
					curr[a[i]]=i;
					dp[a[i]]=dp[j]+1;	
					if(dp[a[i]]>ans)ind=i;
				}
			}	
		}
		dp[a[i]]=max(dp[a[i]],1);
		ans=max(ans,dp[a[i]]);
	}
	vector<int> the;
		while(last[ind]!=-1){
			the.push_back(ind+1);
			ind=last[ind];
		}
			the.push_back(ind+1);
	cout<<ans<<endl;
	for(int i=the.size()-1; i>=0; i--)cout<<the[i]<<" ";
}

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