Submission #1007280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007280		Muaath_5	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3124 ms	54160 KiB

subsequence

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define chmax(x, y) x = max(x, y);
using namespace std;

const int N = 1e5+5;

int n, a[N], k[N];
pair<int, int> dp[21][1<<20];

int prv[N];

const int UPPER = 0b11111111110000000000;
const int LOWER = 0b00000000001111111111;

void update(int num, pii val) {
	for (int x = 0; x < (1<<10); x++)
		chmax(dp[__builtin_popcount((x<<10) & (UPPER&num))][(LOWER&num) | (x<<10)], val);
}

pair<int, int> query_max(int num, int und) {
	pii mx = {0,0};
	for (int x = 0; x < (1<<10); x++) {
		if ( und < __builtin_popcount(x & (LOWER&num)) ) continue;
		mx = max(mx, dp[und-__builtin_popcount(x & (LOWER&num))][(UPPER&num) | x]);
	}
		
	return mx;
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; cin >> a[i++]);
	for (int i = 1; i <= n; cin >> k[i++]);
	
	pair<int, int> mx = {0,0};
	for (int i = 1; i <= n; i++) {
		pii qr = query_max(a[i], k[i]);
		qr.first++;
		prv[i]=qr.second;
		qr.second = i;
		mx = max(mx, qr);
		update(a[i], qr);
	}
	
	vector<int> lis;
	while (mx.second) {
		lis.push_back(mx.second);
		mx.second = prv[mx.second];
	}
	reverse(lis.begin(), lis.end());
	
	cout << lis.size() << '\n';
	for (int i : lis) cout << i << ' ';
}

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