Submission #818505

#	Time	Username	Problem	Language	Result	Execution time	Memory
818505		pavement	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4580 ms	48064 KiB

subsequence

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

const int k = 10;
int n, cl[1 << k][1 << k][k + 1];
vector<int> a, c, dp, prv;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	a.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	c.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}
	dp.resize(n, 1);
	prv.resize(n, -1);
	memset(cl, -1, sizeof cl);
	for (int i = 0; i < n; i++) {
		for (int lh = 0; lh < (1 << k); lh++) {
			int rh = a[i] >> k;
			int lh_i = a[i] & ((1 << k) - 1);
			if (c[i] < __builtin_popcount(lh & lh_i) || c[i] - __builtin_popcount(lh & lh_i) > k) {
				continue;
			}
			int to = cl[lh][rh][c[i] - __builtin_popcount(lh & lh_i)];
			if (to != -1) {
				if (dp[to] + 1 > dp[i]) {
					dp[i] = dp[to] + 1;
					prv[i] = to;
				}
			}
		}
		for (int rh = 0; rh < (1 << k); rh++) {
			int lh = a[i] & ((1 << k) - 1);
			int rh_i = (a[i] ^ lh) >> k;
			if (cl[lh][rh][__builtin_popcount(rh & rh_i)] == -1 || dp[cl[lh][rh][__builtin_popcount(rh & rh_i)]] < dp[i]) {
				cl[lh][rh][__builtin_popcount(rh & rh_i)] = i;
			}
		}
	}
	int mx = -1;
	for (int i = 0; i < n; i++) {
		if (mx == -1 || dp[i] >= dp[mx]) {
			mx = i;
		}
	}
	vector<int> ret;
	while (mx != -1) {
		ret.push_back(mx + 1);
		mx = prv[mx];
	}
	reverse(ret.begin(), ret.end());
	cout << ret.size() << '\n';
	for (int i : ret) {
		cout << i << ' ';
	}
	cout << '\n';
}

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