Submission #624311

#	Time	Username	Problem	Language	Result	Execution time	Memory
624311		GusterGoose27	Longest beautiful sequence (IZhO17_subsequence)	C++11	100 / 100	3743 ms	48244 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;
const int MAXALLOC = 1024;
int n;
int nums[MAXN];
int com_bits[MAXN];
int best_dp[MAXALLOC][MAXALLOC][11]; // first half, number of bits in common with second half
int dp[MAXN+1];
int pdp[MAXN+1];

int dpmax(int a, int b) {
	if (dp[a] > dp[b]) return a;
	return b;
}

void print_vals(int i, bool space = 0) {
	if (i == 0) return;
	print_vals(pdp[i], 1);
	cout << i;
	if (space) cout << " ";
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> nums[i];
	for (int i = 0; i < n; i++) cin >> com_bits[i];
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int p1 = nums[i] >> 10;
		int p2 = nums[i] - (p1 << 10);
		int b = 0;
		for (int mask = 0; mask < MAXALLOC; mask++) {
			int req = com_bits[i]-__builtin_popcount(p1&mask);
			if (0 <= req && req <= 10) b = dpmax(b, best_dp[mask][p2][req]);
		}
		dp[i+1] = 1+dp[b];
		pdp[i+1] = b;
		ans = dpmax(ans, i+1);
		for (int mask = 0; mask < MAXALLOC; mask++) {
			best_dp[p1][mask][__builtin_popcount(mask&p2)] = dpmax(best_dp[p1][mask][__builtin_popcount(mask&p2)], i+1);
		}
	}
	cout << dp[ans] << "\n";
	print_vals(ans);
	cout << "\n";
}

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