제출 #759726

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
759726		NK_	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3263 ms	96408 KiB

subsequence

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

const int B = 10;

template<class T> using V = vector<T>;

struct T {
	int x, i;
};

const int INF = 1e9+10;

int pct(int x) { return __builtin_popcount(x); }

int PCT[1 << B][1 << B];
T dp[1 << B][1 << B][B + 1];
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	V<int> A(N); for(auto& x : A) cin >> x;
	V<int> K(N); for(auto& x : K) cin >> x;

	for(int i = 0; i < 1 << B; i++) for(int j = 0; j < 1 << B; j++) {
		PCT[i][j] = pct(i & j);
		for(int k = 0; k <= B; k++) {
			dp[i][j][k] = {-INF, -1};
		}
	}

	V<int> prv(N, -1), len(N, 1);

	for(int i = 0; i < N; i++) {
		int lx = A[i] / (1 << B);
		int rx = A[i] % (1 << B);

		for(int l = 0; l < 1 << B; l++) {
			int need = K[i] - PCT[l][lx];

			if (need < 0 || need > B) continue;

			if (len[i] < dp[l][rx][need].x + 1) {
				len[i] = dp[l][rx][need].x + 1;
				prv[i] = dp[l][rx][need].i;
			}
		}	

		for(int r = 0; r < 1 << B; r++) {
			if (dp[lx][r][PCT[rx][r]].x < len[i]) {
				dp[lx][r][PCT[rx][r]].x = len[i];
				dp[lx][r][PCT[rx][r]].i = i;
			}
		}
	}
	
	int best = -1, ans = -1;
	for(int i = 0; i < N; i++) {
		if (ans < len[i]) best = i, ans = len[i];
	}

	V<int> ANS;
	while(best != -1) {
		ANS.push_back(best + 1);
		best = prv[best];
	}

	reverse(begin(ANS), end(ANS));
	cout << size(ANS) << nl;
	for(auto x : ANS) cout << x << " ";

    return 0;
}

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