Submission #597877

#	Time	Username	Problem	Language	Result	Execution time	Memory
597877		rsjw	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2084 ms	92624 KiB

subsequence

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

const int maxcount = 10;
const int mask = 1 << maxcount;
const int maxn = 100005;

int pop[mask];  // popcount array

int f[mask][mask][maxcount + 1];
int last[maxn];  // store position of last chosen element

int id[mask][mask][maxcount + 1];
int a[maxn], k[maxn];
int n;
int sol[maxn], len;

int main() {
	cin >> n;
	for (int i = 1; i < mask; i++) {
		pop[i] = pop[i >> 1] + (i & 1);
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> k[i];
	}
	int maxid = 0, maxn = 0;
	for (int i = 1; i <= n; i++) {
		int cur0 = (a[i]) >> maxcount, cur1 = (a[i]) & (mask - 1), ans = 1;
		for (int pre1 = 0; pre1 < mask; pre1++) {
			int q = k[i] - pop[pre1 & cur1];
			if (q >= 0 && q <= maxcount && ans < f[pre1][cur0][q] + 1) {
				ans = f[pre1][cur0][q] + 1;
				last[i] = id[pre1][cur0][q];
			}
		}
		for (int nex0 = 0; nex0 < mask; nex0++) {
			int q = pop[nex0 & cur0];
			if (ans > f[cur1][nex0][q]) {
				f[cur1][nex0][q] = ans;
				id[cur1][nex0][q] = i;
			}
		}
		if (maxn < ans) {
			maxn = ans;
			maxid = i;
		}
	}
	int cur = maxid;
	while (cur) { // generate path
		sol[++len] = cur;
		cur = last[cur];
	}
	cout << len << endl;
	for (int i = len; i >= 1; i--) {
		cout << sol[i] << " \n" [i == 1];
	}
}

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