제출 #739070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
739070		AverageAmogusEnjoyer	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	6071 ms	2864 KiB

subsequence

/*
ID: dalpone1
TASK: Longest_Beautiful_Sequence
LANG: C++
*/
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end() 
#define pb push_back
#define ll long long
#define nl '\n'
const int N = 100100, K = 21;
int dp[N][2], n, a[N], k[N], ans = 1, ans_pos = 0;
int main() {
	// ifstream cin(".in");
	// ofstream cout(".out");
	ios::sync_with_stdio(0);
	cin.tie(0);
	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]++, dp[i][1]--;
	for (int i = 1; i < n; i++)
		for (int j = 0; j < i; j++)
			if (__builtin_popcount(a[i] & a[j]) == k[i] && dp[i][0] < dp[j][0] + 1) 
				dp[i][0] = dp[j][0] + 1, dp[i][1] = j, ans_pos = (ans < dp[i][0] ? i : ans_pos), ans = max(ans, dp[i][0]);
	cout << ans << nl;
	vector<int> sequence;
	for (int i = ans_pos; i != -1; i = dp[i][1]) 
		sequence.pb(i+1);
	reverse(all(sequence));
	assert((int) sequence.size() == ans);
	for (int i: sequence)
		cout << i << " ";
}

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