Submission #1115473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115473		vjudge1	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	2 ms	3152 KiB

subsequence

#include "bits/stdc++.h"

using namespace std;

const int mxN = 100005;
const int mxBt = 10;

int dp[1 << mxBt][1 << mxBt][mxBt];
int ans[mxN];
int a[mxN];
int k[mxN];

void solve() {
	int N;
	cin >> N;

	for (int i = 0; i < N; i ++) {
		cin >> a[i];
	}

	for (int i = 0; i < N; i ++) {
		cin >> k[i];
	}

	int mask = (1 << mxBt) - 1;
	int r = 0, d = 0;
	for (int i = 0; i < N; i ++) {
		ans[i] = 1;
		for (int bottomMask = 0; bottomMask < (1 << mxBt); bottomMask ++) {
			int need = k[i] - __builtin_popcount(bottomMask & a[i]);
			ans[i] = max(ans[i], dp[bottomMask][a[i] >> mxBt][need] + 1);
		}
		for (int topMask = 0; topMask < (1 << mxBt); topMask ++) {
			int value = __builtin_popcount((topMask << mxBt) & a[i]);
			dp[a[i] & mask][topMask][value] = max(dp[a[i] & mask][topMask][value], ans[i]);
		}
		if (ans[i] > r) {
			r = ans[i];
			d = i;
		}
	}

	cout << r << endl;
	deque<int> path;
	for (int i = d; r; r --) {
		path.push_front(i + 1);
		for (int j = i - 1; 0 <= j; j --) {
			int value = __builtin_popcount(a[j] & a[i]);
			if (value == k[i] && ans[j] == r - 1) {
				i = j;
				break;
			}
		}
	}
	for (int i : path) {
		cout << i << ' ';
	}
	cout << endl;
}

int main() {
	solve();
}

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