Submission #819594

#	Time	Username	Problem	Language	Result	Execution time	Memory
819594		SanguineChameleon	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5194 ms	93244 KiB

subsequence

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

const int maxn = 1e5 + 20;
int a[maxn];
int c[maxn];
pair<int, int> dp[maxn];
pair<int, int> best[1024][1024][11];

int main() {
	for (int x = 0; x < 1024; x++) {
		for (int y = 0; y < 1024; y++) {
			for (int k = 0; k <= 10; k++) {
				best[x][y][k] = {-1, -1};
			}
		}
	}
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> c[i];
	}
	pair<int, int> best_dp = {-1, -1};
	for (int i = 1; i <= n; i++) {
		dp[i] = {1, -1};
		int left_mask = a[i] & 1023;
		int right_mask = a[i] >> 10;
		for (int x = 0; x < 1024; x++) {
			int rem = c[i] - __builtin_popcount(left_mask & x);
			if (0 <= rem && rem <= 10) {
				dp[i] = max(dp[i], best[x][right_mask][rem]);
			}
		}
		best_dp = max(best_dp, make_pair(dp[i].first, i));
		pair<int, int> nxt = {dp[i].first + 1, i};
		for (int x = 0; x < 1024; x++) {
			int cnt = __builtin_popcount(right_mask & x);
			best[left_mask][x][cnt] = max(best[left_mask][x][cnt], nxt);
		}
	}
	vector<int> res;
	int cur = best_dp.second;
	while (cur != -1) {
		res.push_back(cur);
		cur = dp[cur].second;
	}
	reverse(res.begin(), res.end());
	cout << res.size() << '\n';
	for (auto x: res) {
		cout << x << " ";
	}
	cout << '\n';
}

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