제출 #1115392

#제출 시각아이디문제언어결과실행 시간메모리
1115392vjudge1Longest beautiful sequence (IZhO17_subsequence)C++17
0 / 100
1 ms504 KiB
#include "bits/stdc++.h"

using namespace std;

int dp[20][20];
int a[20];
int k[20];

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];
	}

	for (int i = 0; i < N; i ++) {
		dp[i][0] = 1;
	}

	for (int i = 0; i < N; i ++) {
		for (int j = 1; j <= i; j ++) {
			for (int l = 0; l < i; l ++) {
				int bt = __builtin_popcount(a[i] & a[l]);
				if (k[j] == bt && dp[l][j - 1]) {
					dp[i][j] = 1;
				}
			}
		}
	}

	int mx = 0;
	int d = 0;
	for (int i = 0; i < N; i ++) {
		for (int j = 1; j <= i; j ++) {
			if (dp[i][j] && j > mx) {
				mx = j, d = i;
			}
		}
	}

	cout << mx + 1 << endl;

	deque<int> ans;
	for (int i = d; 0 <= mx; i --, mx --) {
		ans.push_front(i + 1);
		for (int j = i; 1 <= j; j --) {
			int bt = __builtin_popcount(a[j] & a[i]);
			if (k[mx] == bt && dp[j - 1][mx - 1]) {
				i = j;
				break;
			}
		}
	}

	for (int i : ans) {
		cout << i << ' ';
	}
	cout << endl;
}

int main() {
	solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...