Submission #382707

#	Time	Username	Problem	Language	Result	Execution time	Memory
382707		SeDunion	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5391 ms	167548 KiB

subsequence

#include<bits/stdc++.h>
#ifndef LOCAL
#define cerr if(false)cerr
#endif // LOCAL
using namespace std;
using ll = long long;
const int N = 1e5 + 66;
 
const int LOG = 20;
const int HALF = LOG >> 1;
 
pair<int,int>dp[N],vals[1<<HALF][1<<HALF][LOG];
 
int a[N], k[N];

int bip[1<<LOG];
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for (int m1 = 0 ; m1 < (1 << HALF) ; ++ m1)
		bip[m1] = __builtin_popcount(m1);
	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) {
		int m1 = (a[i] & ((1 << HALF) - 1));
		int m2 = (a[i] >> HALF);
		for (int m2q = 0 ; m2q < (1 << HALF) ; ++ m2q) {
			int k2q = bip[m2 & m2q];
			int need = k[i] - k2q;
			if (need >= 0 && need < LOG) {
				dp[i] = max(dp[i], vals[m1][m2q][need]);
			}
		}
		dp[i].first++;
		pair<int,int>rel = {dp[i].first, i};
		for (int m1q = 0 ; m1q < (1 << HALF) ; ++ m1q) {
			int k1q = bip[m1q & m1];
			vals[m1q][m2][k1q] = max(vals[m1q][m2][k1q], rel);
		}
		cerr << dp[i].first << " " << dp[i].second << endl;
	}
	int x = max_element(dp + 1, dp + 1 + n) - dp;
	cout << dp[x].first << "\n";
	vector<int>ans;
	while (x != 0) {
		ans.emplace_back(x);
		x = dp[x].second;
	}
	for (int i = (int)ans.size() - 1 ; i >= 0 ; -- i) cout << ans[i] << " ";
}

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