Submission #1131055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131055		nlkn	Longest beautiful sequence (IZhO17_subsequence)	C++20	0 / 100	1 ms	712 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int B = 8;
struct State {
	int len, end;
};
int main() {
	// preprocess:
	// bc[i][j] = bit_count(i & j)
	vector<vector<int>> bc(1 << B, vector<int>(1 << B));
	for (int i = 0; i < (1 << B); i++) {
		for (int j = 0; j < (1 << B); j++) { bc[i][j] = __builtin_popcount(i & j); }
	}

	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	vector<int> k(n);
	for (int i = 0; i < n; i++) cin >> k[i];
	int ans = 1;
	// best_i: most optimal index to end on
	int best_i = 0;
	vector<int> prv(n);               // prv[i]: best index to include before i
	iota(prv.begin(), prv.end(), 0);  // prv[i] = i

	vector<vector<State>> dp2(1 << B, vector<State>(B, State{0, -1}));
	for (int i = 0; i < n; i++) {
		// length of longest LBS that ends at i
		int len = dp2[a[i]][k[i]].len + 1;
		if (dp2[a[i]][k[i]].end != -1) { prv[i] = dp2[a[i]][k[i]].end; }
		for (int j = 0; j < (1 << B); j++) {
			State &affected_state = dp2[j][bc[a[i]][j]];
			if (len > affected_state.len) { affected_state = State{len, i}; }
		}
		if (len > ans) {
			ans = len;
			best_i = i;
		}
	}

	cout << ans << endl;

	vector<int> res;
	while (prv[best_i] != best_i) {
		res.push_back(best_i);
		best_i = prv[best_i];
	}
	res.push_back(best_i);
	reverse(res.begin(), res.end());
	for (int x : res) { cout << x + 1 << " "; }
}

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