Submission #444554

#	Time	Username	Problem	Language	Result	Execution time	Memory
444554		dutch	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	6043 ms	66272 KiB

subsequence

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

const int MAXN = 1e5, B = 8, C = 20-B;

int n, a[MAXN], k[MAXN], p[MAXN], rightOn, dp[C+1][1<<C][1<<B], g[C+1][1<<C][1<<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<n; ++i) cin >> k[i];

	for(int i=B; i<20; ++i) rightOn |= 1<<i;

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

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

		for(int j=0; j<(1<<C); ++j){
			req = __builtin_popcount(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: 0 / 17
• Subtask 4: 0 / 60