Submission #439700

#	Time	Username	Problem	Language	Result	Execution time	Memory
439700		zeyu	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5759 ms	174032 KiB

subsequence

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
int dp[1 << 10][1 << 10][21];
int prv[1 << 10][1 << 10][21];
vector<int> len(maxn), p(maxn, -1);
int n, ans, lst = -1;
const int BT = (1 << 10) - 1;

int main(){
	memset(prv, -1, sizeof(prv));
	cin >> n;
	int a[n];
	for (int i = 0; i < n; i ++) cin >> a[i];
	int pop[1 << 10];
	for (int i = 0; i < 1 << 10; i ++) pop[i] = __builtin_popcount(i);
	for (int i = 0; i < n; i ++){
		int k; cin >> k;
		len[i] = 1;
		for (int j = 0; j < (1 << 10); j ++){
			int K = k - pop[j & (a[i] >> 10)];
			if (K < 0) continue;
			if (len[i] < dp[j][a[i] & BT][K] + 1){
				len[i] = dp[j][a[i] & BT][K] + 1;
				p[i] = prv[j][a[i] & BT][K];
			}
		}
		int bg = a[i] >> 10;
		for (int j = 0; j < 1 << 10; j ++){
			int K = pop[a[i] & j];
			if (dp[bg][j][K] < len[i]){
				dp[bg][j][K] = len[i];
				prv[bg][j][K] = i;
			}
		}
		ans = max(ans, len[i]);
		if (ans == len[i]) lst = i;
	}
	vector<int> res;
	cout << ans << endl;
	for (; lst != -1; lst = p[lst]) res.push_back(lst);
	for (int i = ans - 1; i >= 0; i --) cout << res[i] + 1 << " ";
}

/*
4
1 2 3 4 
10 0 1 0
*/

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