Submission #934443

#	Time	Username	Problem	Language	Result	Execution time	Memory
934443		parsadox2	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	6011 ms	3168 KiB

subsequence

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#define MAX(a,b) ((a) > (b) ? (a) : (b)) 

using namespace std;

const int N = 1e5 + 10;
int n , a[N] , b[N] , dp[N];

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);   cout.tie(0);
	cin >> n;
	for(int i = 1 ; i <= n ; i++)
		cin >> a[i];
	for(int i = 1 ; i <= n ; i++)
		cin >> b[i];
	int ans = 0 , las = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 1 ; j < i ; j++)  
			dp[i] = (__builtin_popcount((a[i] & a[j])) == b[i] ? MAX(dp[i] , dp[j]) : dp[i]);
		dp[i]++;
		ans = max(ans , dp[i]);
		if(dp[i] == ans)
			las = i;
	}
	vector <int> res;
	res.push_back(las);
	for(int i = las - 1 ; i > 0 ; i--)
	{
		if(dp[i] == dp[las] - 1 && __builtin_popcount((a[las] & a[i])) == b[las])
		{
			res.push_back(i);
			las = i;
		}
	}
	reverse(res.begin() , res.end());
	cout << res.size() << '\n';
	for(auto u : res)
		cout << u << " ";
	cout << '\n';
	return 0;
}

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