Submission #888826

#	Time	Username	Problem	Language	Result	Execution time	Memory
888826		tigran	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2943 ms	184224 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[1024];
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] >> 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;
}

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