제출 #36132

#제출 시각아이디문제언어결과실행 시간메모리
36132cheater2kLongest beautiful sequence (IZhO17_subsequence)C++14
100 / 100
5223 ms54736 KiB
#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");
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...