Submission #1130929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130929		mnbvcxz123	Longest beautiful sequence (IZhO17_subsequence)	C++20	23 / 100	6091 ms	1860 KiB

subsequence

#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);
	int ans = 1;
	int best_i = 0;
	vector<int> prv(n);
	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 << " "; }
}

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