Submission #888798

#	Time	Username	Problem	Language	Result	Execution time	Memory
888798		alex_2008	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	5 ms	1372 KiB

subsequence

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 1e5 + 10;
int a[N], k[N];
pair <int, int> d[1030][1030][22];
int bitCnt[1025];
int dp[N], way[N];

int bitcount(int x) {
	return bitCnt[x];
}

void precalc() {
	for (int i = 1; i < 1024; i++) {
		bitCnt[i] = bitCnt[(i / 2)] + (i % 2);
	}
}

int main() {
	precalc();
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> k[i];
	}
	int final_ans;
	for (int i = 1; i <= n; i++) {
		dp[i] = 1;
		int left = ((1 << 10) - 1) & a[i];
		int right = a[i] & ((1 << 20) - (1 << 10));
		for (int l = 0; l < 1024; l++) {
			int nk = k[i] - bitcount(left & l);
			if (nk >= 0 && dp[i] < d[l][right][nk].first + 1) {
				dp[i] = d[l][right][nk].first + 1;
				way[i] = d[l][right][nk].second;
			}
		}
		for (int r = 0; r < 1024; r++) {
			int bitdist = bitcount(right & r);
			if (d[left][r][bitdist].first <= dp[i]) {
				d[left][r][bitdist] = { dp[i], i };
			}
		}
		final_ans = max(final_ans, dp[i]);
	}
	vector <int> super_puper_final_ans;
	int ind = 1;
	for (int i = 2; i <= n; i++) {
		if (dp[i] > dp[ind]) {
			ind = i;
		}
	}
	while (dp[ind] != 1) {
		super_puper_final_ans.push_back(ind);
		ind = way[ind];
	}
	super_puper_final_ans.push_back(ind);
	reverse(super_puper_final_ans.begin(), super_puper_final_ans.end());
	cout << (int)super_puper_final_ans.size() << "\n";
	for (auto it : super_puper_final_ans) {
		cout << it << " ";
	}
	return 0;
}
/*
4
1 2 3 4
10 0 1 0

5
5 3 5 3 5
10 1 20 1 20
*/

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