Submission #1284045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284045		duyanhchupapi	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	3134 ms	92504 KiB

subsequence

#include <bits/stdc++.h>
using namespace std; 
using ll = long long; 
const int N = 1e5 + 5;
int n, a[N], k[N], dp[N], trace[N], luu[1025][1025][22], base = 1024;

int main() { 
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);	
	cin >> n;
	for(int i=1;i<=n;++i) cin >> a[i];
	for(int i=1;i<=n;++i) cin >> k[i];
	for(int i=1;i<=n;++i) {
		dp[i] = 1;
		int mask2 = a[i] % base;
		int mask1 = (a[i] - mask2) / base;
		for(int mask=0;mask<base;++mask) {
			int K = __builtin_popcount(mask & mask1);
			K = luu[mask][mask2][k[i] - K];
			if(dp[K] + 1 > dp[i]) dp[i] = dp[K] + 1, trace[i] = K;
		}
		for(int mask=0;mask<base;++mask) {
			int id = __builtin_popcount(mask & mask2);
			if(dp[luu[mask1][mask][id]] < dp[i]) 
				luu[mask1][mask][id] = i;
		}
	}
	int cur = 0;
	for(int i=1;i<=n;++i) if(dp[i] > dp[cur]) cur = i;
	cout << dp[cur] << '\n';
	vector <int> ans;
	while(cur != 0) {
		ans.push_back(cur);
		cur = trace[cur];
	}
	reverse(ans.begin(), ans.end());
	for(int x : ans) cout << x << ' ';
 	return 0;
}

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