Submission #753639

#	Time	Username	Problem	Language	Result	Execution time	Memory
753639		AverageAmogusEnjoyer	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2767 ms	97456 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) x.begin(), x.end() 
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int) x.size()
#define pb push_back
#define ll long long
#define nl '\n'

const int N = 100100, K = 10;

int n, prv[N], a[N], k[N], bc[1<<K][1<<K];

struct state{
	int len, pos;
} dp[(1<<K)+5][(1<<K)+5][K+1];

void solve() {
	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=0;i<(1<<K);i++) 
		for (int j=0;j<(1<<K);j++)
			bc[i][j]=__builtin_popcount(i&j);
	iota(prv,prv+n,0);
	int ans = 1, best_i = 0;
	for (int i=0;i<n;i++) {
		int l = a[i]>>K, r = a[i]%(1<<K);
		int best = 1;
		for (int j=0;j<(1<<K);j++) {
			int needed = k[i]-bc[l][j];
			if (needed<0||needed>K) {continue;}
			if (best<dp[j][r][needed].len+1) {
				best=dp[j][r][needed].len+1;
				prv[i]=dp[j][r][needed].pos;
			}
		}
		if (best > ans) {
			ans = best;
			best_i = i;
		}
		for (int j=0;j<(1<<K);j++) {
			int new_k = bc[j][r];
			if (new_k > K) {continue;}
			if (dp[l][j][new_k].len < best) {
				dp[l][j][new_k].len=best;
				dp[l][j][new_k].pos=i;
			}
		}
	}
	cout << ans << nl;
	vector<int> res;
	res.pb(best_i);
	while(prv[best_i]!=best_i) {
		res.pb(prv[best_i]);
		best_i = prv[best_i];
	}
	assert(sz(res)==ans);
	reverse(all(res));
	for (auto i:res) cout << i+1 << " ";
	cout << nl;
}

signed main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tt=1; 
	// cin >> tt;
	while(tt--) { solve(); }
}

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