제출 #901576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
901576		OAleksa	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	6025 ms	4288 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 1e5 + 69;
int n, a[N], b[N], dp[N], par[N];
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1;i <= n;i++)
		cin >> a[i];
	for (int i = 1;i <= n;i++)
		cin >> b[i];
	dp[1] = 1;
	for (int i = 2;i <= n;i++) {
		dp[i] = 1;
		for (int j = i - 1;j >= 1;j--) {
			int x = __builtin_popcount((a[i] & a[j]));
			if (x == b[i]) {
				if (dp[j] + 1 > dp[i]) {
					par[i] = j;
					dp[i] = dp[j] + 1;
				}
			}
		}
	}
	int mx = 1;
	for (int i = 2;i <= n;i++) {
		if (dp[i] > dp[mx]) 
			mx = i;
	}
	int t = mx;
	vector<int> ans;
	while (t != 0) {
		ans.push_back(t);
		t = par[t];
	}
	reverse(ans.begin(), ans.end());
	cout << ans.size() << '\n';
	for (auto i : ans)
		cout << i << " ";
  return 0;
}

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