Submission #439691

#	Time	Username	Problem	Language	Result	Execution time	Memory
439691		zeyu	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5007 ms	175172 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(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	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];
	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] < 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 = 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;
	}
	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 << " ";
}

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