Submission #747864

#	Time	Username	Problem	Language	Result	Execution time	Memory
747864		tcmmichaelb139	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	6071 ms	2388 KiB

subsequence

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

const int MAXN = 100'001;

int n;
int dp[MAXN];
int pre[MAXN];

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

	cin >> n;

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

	for (int i = 0; i <= n; i++)
		pre[i] = -1, dp[i] = 1;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (__builtin_popcount(a[j] & a[i]) == k[i]) {
				if (dp[i] < dp[j] + 1) {
					dp[i] = dp[j] + 1;
					pre[i] = j;
				}
			}
		}
	}

	int ans = 0, ind = -1;
	for (int i = 0; i < n; i++) {
		if (ans < dp[i]) {
			ans = dp[i];
			ind = i;
		}
	}

	vector<int> sol;
	for (int i = ind; i != -1; i = pre[i]) {
		sol.push_back(i);
	}
	reverse(begin(sol), end(sol));
	cout << size(sol) << '\n';
	for (int i = 0; i < size(sol); i++)
		cout << sol[i] + 1 << " \n"[i + 1 == size(sol)];
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 0; i < size(sol); i++)
      |                  ~~^~~~~~~~~~~
subsequence.cpp:53:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   cout << sol[i] + 1 << " \n"[i + 1 == size(sol)];
      |                               ~~~~~~^~~~~~~~~~~~

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