Submission #343615

#	Time	Username	Problem	Language	Result	Execution time	Memory
343615		Gurban	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	6024 ms	1948 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int maxn=1e5+5;
int n,k,a[maxn],pos;
pair<int,int>dp[maxn];
vector<int>v;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1;i <= n;i++){
		cin >> k;
		dp[i] = {1,i};
		for(int j = 1;j < i;j++)
			if(__builtin_popcount(a[i]&a[j]) == k and dp[j].first + 1 > dp[i].first) dp[i].first = dp[j].first+1,dp[i].second=j;
		if(dp[pos].first < dp[i].first) pos = i;
	}
	cout<<dp[pos].first<<'\n';
	while(dp[pos].second != pos){
		v.push_back(pos);
		pos = dp[pos].second;
	}
	v.push_back(pos);
	reverse(v.begin(),v.end());
	for(auto i : v) cout<<i<<' ';
}
/*
4
1 2 3 4
10 0 1 0

2
8 9
20 0

5
5 3 5 3 5
10 1 20 1 20
*/

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