Submission #1269085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269085		BuzzyBeez	Longest beautiful sequence (IZhO17_subsequence)	C++20	0 / 100	13 ms	7752 KiB

subsequence

#include <bits/allocator.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,popcnt,lzcnt")
#include <bits/stdc++.h> 
using namespace std;

const int B = 10; 

vector<int> adj[1 << B][B + 1];

void prep() {
	for (int i = 0; i < (1 << B); ++i) for (int j = 0; j < (1 << B); ++j)
		adj[i][__builtin_popcount(i & j)].push_back(j);
}

int a[100008], b[100008], k[100008];
pair<int, int> dp[100008];
pair<int, int> opt[1 << B][1 << B][B + 1];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	prep();
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		b[i] = a[i] % (1 << B); a[i] >>= B;
		// cout << a[i] << ' ' << b[i] << '\n';
	}
	// cout << endl;
	for (int i = 1; i <= n; ++i) cin >> k[i];
	for (int i = 1; i <= n; ++i) {
		dp[i] = {0, 0};
		// cout << "At " << i << ": \n";
		for (int sl = 0; sl <= k[i]; ++sl) for (int m1 : adj[a[i]][sl]) {
			dp[i] = max(dp[i], opt[m1][b[i]][k[i] - sl]);
			// cout << opt[m1][b[i]][k[i] - sl].first << ' ' << opt[m1][b[i]][k[i] - sl].second << '\n';
		}
		++dp[i].first;
		for (int sr = 0; sr <= B; ++sr) for (int m2 : adj[b[i]][sr])
			opt[a[i]][m2][sr] = max(opt[a[i]][m2][sr], make_pair(dp[i].first, i));
		// cout << dp[i].first << ' ' << dp[i].second << "!!" << '\n';
	}
	int mx = n;
	for (int i = n; i; --i) if (dp[i].first > dp[mx].first) mx = i;
	cout << dp[mx].first << '\n';
	int pt = mx; vector<int> trace;
	while (pt) {
		trace.push_back(pt);
		pt = dp[pt].second;
	}
	reverse(trace.begin(), trace.end());
	for (int i : trace) cout << i << ' ';
}

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