Submission #36129

#	Time	Username	Problem	Language	Result	Execution time	Memory
36129		cheater2k	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	6000 ms	99792 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

const int MAX = (1 << 20);
const int TMP = (1 << 10) - 1;
const int N = 100005;

// 10 last bits: mask & TMP
// 10 first bits: mask >> 10

int n, a[N], k[N];
vector<int> G[MAX >> 10][11]; // G[mask][overlap]
pair<int,int> save[MAX][11]; // (dp, mask)
int trace[N], f[N];

void mxm(pair<int,int> &x, pair<int,int> y) {
	if (x < y) x = y;
}

int main() {
	ios_base::sync_with_stdio(false); 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 mask = 0; mask < (MAX >> 10); ++mask) {
		for (int nmask = 0; nmask < (MAX >> 10); ++nmask) {
			int overlap = __builtin_popcount(mask & nmask);
			G[mask][overlap].push_back(nmask);
		}
	}

	// solve
	for (int i = 1; i <= n; ++i) {
		pair<int,int> dp;
		int suf = (a[i] & TMP);
		int pre = (a[i] >> 10);

		for (int k2 = 0; k2 <= min(10, k[i]); ++k2) {
			int k1 = k[i] - k2;
			if (k1 > 10) continue;
			// find dp[i]
			for (int nsuf : G[suf][k2]) {
				mxm(dp, save[(pre << 10) + nsuf][k1]);
			}
		}
		f[i] = ++dp.first;
		trace[i] = dp.second;
		dp.second = i;
		
		// update dp[i] to other dps
		for (int overlap = 0; overlap <= 10; ++overlap) {
			for (int mask : G[pre][overlap]) {
				mxm(save[(mask << 10) + suf][overlap], dp);
			}
		}
	}

	int mx = 0, pos = 0;
	for (int i = 1; i <= n; ++i) if (f[i] > mx) mx = f[i], pos = i;

	printf("%d\n", mx);
	vector<int> ans;
	while(pos > 0) {
		ans.push_back(pos);
		pos = trace[pos];
	}
	reverse(ans.begin(), ans.end());
	for (int i : ans) printf("%d ", i); printf("\n");
}

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