제출 #343616

#제출 시각아이디문제언어결과실행 시간메모리
343616GurbanLongest beautiful sequence (IZhO17_subsequence)C++17
23 / 100
6046 ms1852 KiB
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

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
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...