Submission #439684

#	Time	Username	Problem	Language	Result	Execution time	Memory
439684		zeyu	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	54 ms	88232 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];
int len[maxn];
vector<int> p(maxn, -1);
const int BT = (1 << 10) - 1;

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

/*
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