제출 #439679

#제출 시각아이디문제언어결과실행 시간메모리
439679zeyuLongest beautiful sequence (IZhO17_subsequence)C++17
0 / 100
8 ms3276 KiB
#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(){
	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 << " ";
}

/*
4
1 2 3 4
10 0 1 0
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...