Submission #818505

#TimeUsernameProblemLanguageResultExecution timeMemory
818505pavementLongest beautiful sequence (IZhO17_subsequence)C++17
100 / 100
4580 ms48064 KiB
#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';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...