Submission #1037473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037473		ef10	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	3 ms	5212 KiB

subsequence

// Source: https://usaco.guide/general/io

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

int N;
int A[100005];
int K[100005];
int BC[1<<10][1<<10];
pair<int,int> dp[1<<10][1<<10][25];
int prv[100005];

int main() {
	for (int i = 0; i < (1<<10); i++) {
		for (int j = 0; j < (1<<10); j++) {
			BC[i][j] = __builtin_popcount(i & j);
		}
	}
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> K[i];
	}
	iota(prv,prv+N,0);
	int longest = 0;
	int best = -1;
	for (int i = 0; i < N; i++) {
		int l = A[i] >> 10;
		int r = A[i] % (1<<10);
		int lbs = 1;
		for (int j = 0; j < (1<<10); j++) {
			int k = K[i]-BC[j][l];
			if (k < 0 || k > 10) continue;
			if (dp[j][r][k].first + 1 > lbs) {
				lbs = dp[j][r][k].first + 1;
				prv[i] = dp[j][r][k].second;
			}
		}
		if (lbs > longest) {
			longest = lbs;
			best = i;
		}
		for (int j = 0; j < (1<<10); j++) {
			int k = BC[r][j];
			if (k < 0 || k > 10) continue;
			if (lbs > dp[l][j][k].first) {
				dp[l][j][k].first = lbs;
				dp[l][j][k].second = i;
			}
		}
	}
	vector<int> res;
	while (true) {
		res.push_back(best);
		if (prv[best] == best) break;
		best = prv[best];
	}
	reverse(res.begin(),res.end());
	cout << longest << endl;
	for (auto e : res) {
		cout << e << " ";
	}
}

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