Submission #444573

#	Time	Username	Problem	Language	Result	Execution time	Memory
444573		dutch	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3845 ms	55376 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5, B = 1<<10;

int n, a[MAXN], k[MAXN], p[MAXN], dp[21][B][B], g[21][B][B], pc[B];
array<int, 2> res;

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i=0; i<n; ++i) cin >> a[i];
	for(int i=0; i<B; ++i) pc[i] = __builtin_popcount(i);

	for(int i=0; i<n; ++i){
		cin >> k[i];
		int curr = 1, req, x = (a[i] & (B-1)), r = (a[i] ^ x) >> 10;
		p[i] = -1;

		for(int l=0; l<B; ++l){
			req = k[i] - pc[l & x];
			if(0 <= req && curr <= dp[req][r][l]){
				curr = dp[req][r][l] + 1;
				p[i] = g[req][r][l];
			}
		}

		for(int j=0; j<B; ++j){
			req = pc[j & r];
			if(dp[req][j][x] < curr){
				dp[req][j][x] = curr;
				g[req][j][x] = i;
			}
		}

		res = max(res, {curr, i});
	}
	cout << res[0] << '\n';
	int ans[res[0]];
	for(int i=0; i<res[0]; ++i){
		ans[i] = res[1];
		res[1] = p[res[1]];
	}
	for(int i=res[0]; --i>=0; ) cout << ans[i]+1 << ' ';
}

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