제출 #523888

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523888		boykut	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	106 ms	4456 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int k[n];
	for (int i = 0; i < n; i++) {
		cin >> k[i];
	}

	if (n <= 5000) {
		int dp[n], p[n], mx = -1;
		fill(p, p + n, -1);
		for (int i = 0; i < n; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (__builtin_popcount(a[i] & a[j]) == k[i] && dp[j] + 1 > dp[i]) {
					dp[i] = dp[j] + 1;
					p[i] = j;
				}
			}
			if (mx == -1 || dp[i] > dp[mx]) {
				mx = i;
			}
		}
		vector<int> ans;
		int v = mx;
		while (v != -1) {
			ans.push_back(1 + v);
			v = p[v];
		}
		cout << ans.size() << '\n';
		reverse(ans.begin(), ans.end());
		for (int v : ans)
			cout << v << ' ';
	} else {
		vector<int> vec[9];
		pair<int, int> dpp[1 << 8];
		for (int mask = 0; mask < (1 << 8); mask++) {
			vec[__builtin_popcount(mask)].push_back(mask);
			dpp[mask] = {-1e9, -1e9};
		}
		int dp[n], p[n], mx = -1;
		fill(p, p + n, -1);
		for (int i = 0; i < n; i++) {
			dp[i] = 1;
			for (int mask = 0; mask < (1 << 8); mask++) {
				if (__builtin_popcount(a[i] & mask) == k[i]) {
					if (dpp[mask].first + 1 > dp[i]) {
						dp[i] = dpp[mask].first + 1;
						p[i] = dpp[mask].second;
					}
				}
			}
			dpp[a[i]] = max(dpp[a[i]], {dp[i], i});
			if (mx == -1 || dp[i] > dp[mx])
				mx = i;
		}
		vector<int> ans;
		int v = mx;
		while (v != -1) {
			ans.push_back(1 + v);
			v = p[v];
		}
		cout << ans.size() << '\n';
		reverse(ans.begin(), ans.end());
		for (int v : ans)
			cout << v << ' ';
	}
	return 0;
}

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