Submission #401365

#	Time	Username	Problem	Language	Result	Execution time	Memory
401365		ngpin04	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3683 ms	93440 KiB

subsequence

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e5 + 5; 

int numbit[1 << 20];
int idmax[1 << 20][21];
int ptr[N];
int dp[N];
int a[N];
int k[N];
int n;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	for (int i = 1; i <= n; i++)
		cin >> k[i];

	for (int i = 0; i < (1 << 20); i++) 
		numbit[i] = __builtin_popcount(i);

	for (int i = 1; i <= n; i++) {
		dp[i] = 1;
		for (int mask = 0; mask < (1 << 20); mask += (1 << 10)) {
			int cnt = numbit[mask & a[i]];
			if (cnt > k[i])
				continue;
			int pre = (((1 << 10) - 1) & a[i]) | mask; 
			int tmp = idmax[pre][k[i] - cnt];
			if (dp[i] < dp[tmp] + 1) {
				dp[i] = dp[tmp] + 1;
				ptr[i] = tmp;
			}
		}

		for (int mask = 0; mask < (1 << 10); mask++) {
			int val = mask | ((((1 << 10) - 1) << 10) & a[i]); 
			int cnt = numbit[mask & a[i]];
			int &res = idmax[val][cnt];
			if (dp[i] > dp[res])
				res = i;
		}
	}	
	int s = max_element(dp + 1, dp + n + 1) - dp;
	cout << dp[s] << "\n";
	vector <int> ans;
	while (s != 0) {
		ans.push_back(s);
		s = ptr[s];
	}
	reverse(ans.begin(), ans.end());
	for (int i : ans)
		cout << i << " ";
	return 0;
}

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