Submission #673591

#	Time	Username	Problem	Language	Result	Execution time	Memory
673591		viwlesxq	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2972 ms	83376 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
 
using ll = int64_t;
using str = string;
 
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
 
const int MAXBIT = 10, MAXMASK = 1 << 10, MAXN = 1e5 + 1;
int dp[MAXBIT + 1][MAXMASK][MAXMASK], last[MAXBIT + 1][MAXMASK][MAXMASK], p[MAXN], cnt_ans, ind;
vector <int> ans;

int count(int x) {
	return __builtin_popcount(x);
}
 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	int a[n + 1], k[n + 1];
	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 r = a[i] >> MAXBIT, l = a[i] & ((1 << MAXBIT) - 1), res = 1;
		for (int mask = 0; mask < MAXMASK; mask++) {
			int cnt = k[i] - count(mask & l);
			if (cnt < 0 || cnt > MAXBIT) continue;
			if (res < dp[cnt][mask][r] + 1) {
				res = dp[cnt][mask][r] + 1;
				p[i] = last[cnt][mask][r];
			}
		} 
		for (int mask = 0; mask < MAXMASK; mask++) {
			int cnt = count(mask & r);
			if (res > dp[cnt][l][mask]) {
				dp[cnt][l][mask] = res;
				last[cnt][l][mask] = i;
			}
		}
		if (cnt_ans < res) {
			cnt_ans = res;
			ind = i;
		}
	}
	cout << cnt_ans << '\n';
	while (ind) {
		ans.pb(ind);
		ind = p[ind];
	}
	reverse(all(ans));
	for (int i : ans) cout << i << ' ';
}

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