Submission #1110839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110839		KK_1729	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	6056 ms	4428 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"
 
void printVector(vector<int> a){
    for (auto x: a) cout << x << " ";
    cout << endl;
}

void solve(){
	int n; cin >> n;
	vector<int> a(n);
	FOR(i,0,n) cin >> a[i];
	vector<int> k(n);
	FOR(i,0,n) cin >> k[i];

	vector<int> dp(n, 1);
	vector<int> prev(n);
	int best = 0;
	int c = 0;
	FOR(i,0,n){
		prev[i] = i;
		FOR(j,0,i){
			if (__builtin_popcount(a[i]&a[j]) == k[i]){
				if (dp[j]+1 > dp[i]){
					dp[i] = dp[j]+1;
					prev[i] = j;
				}
			}
		}
		if (dp[i] > best){
			best = dp[i];
			c = i;
		}
	}
	cout << best << endl;
	vector<int> ans = {};
	while (prev[c] != c){
		ans.pb(c+1);
		c = prev[c];
	}
	ans.pb(c+1);
	reverse(all(ans));
	printVector(ans);
}
 
 
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    solve();
}

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