Submission #719460

#	Time	Username	Problem	Language	Result	Execution time	Memory
719460		DEQK	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3792 ms	183584 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define sz(a) ((int) a.size())
const int N = 1e5 + 15;
const int L = 10;
int n, a[N], k[N], pr[N];
pair<int, int> dp[(1 << L)][(1 << (L + 1))][21];
int cnt[(1 << L)][(1 << L)];
int main() {
	ios::sync_with_stdio(0);
	cin.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 x = 0; x < (1 << L); x++) for(int y = 0; y < (1 << L); y++) {
		cnt[x][y] = __builtin_popcount(x & y);
	}
	int ans = 1, pos = 1;
	for(int i = 1; i <= n; i++) {
		int l = a[i] % (1 << L);
		int r = a[i] >> L;
		int cur = 1;
		for(int j = 0; j < (1 << L); j++) {
			int nd = k[i] - cnt[j][r];
			if(nd >= 0 && nd <= L) {
				if(dp[j][l][nd].first + 1 > cur) {
					cur = dp[j][l][nd].first + 1;
					pr[i] = dp[j][l][nd].second;
				}
			}
		}
		if(cur > ans) {
			ans = cur;
			pos = i;
		}
		for(int j = 0; j < (1 << L); j++) {
			if(dp[r][j][cnt[j][l]].first < cur) {
				dp[r][j][cnt[j][l]].first = cur;
				dp[r][j][cnt[j][l]].second = i;
			}
		}
	}
	cout << ans << '\n';
	vector<int> res;
	while(pos) {
		res.pb(pos);
		pos = pr[pos];
	}
	reverse(res.begin(),res.end());
	for(int x : res) cout << x << ' ';
}

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