제출 #1122315

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122315		I_love_Banu	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2539 ms	49028 KiB

subsequence

#include "bits/stdc++.h"

using namespace std;

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

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

void put(int d) {
	for (int i = d - 1; 0 <= i; i --) {
		int value = __builtin_popcount(a[i] & a[d]);
		if (value == k[d] && ans[i] + 1 == ans[d]) {
			put(i);
			break;
		}
	}
	cout << d + 1 << ' ';
}

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 = -1;
	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]);
			if (0 <= need && need <= mxBt) {
				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;
	put(d);
}

int main() {
	solve();
}

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