Submission #1125263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125263		Joseph0121	Longest beautiful sequence (IZhO17_subsequence)	C++20	23 / 100	45 ms	328 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
//dp[N] = longest subsequence ending with Nth number (so im = N)
const int maxn = 5e3+5;
int N;
int from[maxn];
int a[maxn], k[maxn],dp[maxn];

int main() {
	cin>>N;
	for(int i = 1;i<=N;i++) cin>>a[i];
	for(int i = 1;i<=N;i++) cin>>k[i];
	
	for(int i = 1;i<=N;i++){
		dp[i] = 1;
	}
	dp[1] = 1;
	for(int i = 2;i<=N;i++){
		for(int j = 1;j<=i-1;j++){
			if(__builtin_popcount(a[i]&a[j]) == k[i]){
				if(dp[j]+1 > dp[i]){
					dp[i] = dp[j]+1;
					from[i] = j;
				}
			}
		}
		
	}
	// for(int i = 1;i<=N;i++) cout<<from[i]<<" ";
	// cout<<endl;
	int idx = 1;
	for(int i = 2;i<=N;i++){
		if(dp[i] > dp[idx]) idx = i;
	}
	vector<int> ans;
	// cout<<idx<<endl;
	while(dp[idx]!=1){
		ans.push_back(idx);
		idx = from[idx];
	}
		ans.push_back(idx);
	reverse(ans.begin(),ans.end());

	cout<<ans.size()<<endl;
	for(auto i: ans) cout<<i<<" ";
	// for(int i = 1;i<=N;i++){
	// 	cout<<ans[i]<<" ";
	// }
	// your code goes here
	return 0;
}

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