Submission #714546

#TimeUsernameProblemLanguageResultExecution timeMemory
714546egregiousLongest beautiful sequence (IZhO17_subsequence)C++14
23 / 100
6034 ms1740 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<int> k(n);
	for (int i = 0; i < n; i++) {
		cin >> k[i];
	}

	vector<int> dp(n, 1);
	// best_i: most optimal index to end on
	int ans = 1, best_i = 0;
	// prv[i] = optimal index to include right before i 
	vector<int> prv(n);
	// intially, prv[i] = i
	iota(prv.begin(), prv.end(), 0);

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (__builtin_popcount(a[j] & a[i]) == k[i]) {
				if (dp[j] + 1 > dp[i]) {
					prv[i] = j;
					dp[i] = dp[j] + 1;
				}
			}
		}
		if (dp[i] > ans) {
			ans = dp[i];
			best_i = i;
		}
	}
	
	cout << ans << endl;
	vector<int> res;
	while (prv[best_i] != best_i) {
		res.push_back(best_i);
		best_i = prv[best_i];
	}
	res.push_back(best_i);
	reverse(res.begin(), res.end());
	for (int x : res) cout << x + 1 << " ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...