Submission #1115393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115393		vjudge1	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	1 ms	336 KiB

subsequence

#include "bits/stdc++.h"

using namespace std;

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

void solve() {
	int N;
	cin >> N;

	assert(N < 20);

	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();
}

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