Submission #885190

#	Time	Username	Problem	Language	Result	Execution time	Memory
885190		alex_2008	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	24 ms	9168 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int a[N], k[N], dp[N];
int bitCount[(1 << 20)];
int way[N];
void precalc() {
	bitCount[0] = 0;
	for (int i = 1; i < (1 << 20); i++) {
		bitCount[i] = bitCount[i / 2] + (i % 2);
	}
}
int main() {
	precalc();
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> k[i];
	}
	dp[0] = 1;
	way[0] = -1;
	for (int i = 1; i < n; i++) {
		dp[i] = 1;
		way[i] = -1;
		for (int j = i - 1; j >= 0; j--) {
			if (bitCount[(a[i] & a[j])] == k[i] && dp[i] < dp[j] + 1)  {
				dp[i] = dp[j] + 1;
				way[i] = j;
			}
		}
	}
	int mxdp_ind = 0;
	for (int i = 1; i < n; i++) {
		if (dp[i] > dp[mxdp_ind]) {
			mxdp_ind = i;
		}
	}
	vector <int> ans;
	int ind = mxdp_ind;
	while (ind != -1) {
		ans.push_back(ind + 1);
		ind = way[ind];
	}
	cout << (int)ans.size() << "\n";
	reverse(ans.begin(), ans.end());
	for (auto it : ans) {
		cout << it << " ";
	}
}

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