제출 #36132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
36132		cheater2k	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5223 ms	54736 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]
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) {
		int dp = 0;
		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]) {
				if (dp < f[save[(pre << 10) + nsuf][k1]]) {
					dp = f[save[(pre << 10) + nsuf][k1]];
					trace[i] = save[(pre << 10) + nsuf][k1];
				}
			}
		}
		f[i] = ++dp;
		
		// update dp[i] to other dps
		for (int overlap = 0; overlap <= 10; ++overlap) {
			for (int mask : G[pre][overlap]) {
				if (f[i] > f[save[(mask << 10) + suf][overlap]]) {
					save[(mask << 10) + suf][overlap] = i;
 				}
			}
		}
	}

	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: 60 / 60