Submission #934447

#	Time	Username	Problem	Language	Result	Execution time	Memory
934447		parsadox2	Longest beautiful sequence (IZhO17_subsequence)	C++14	7 / 100	21 ms	4952 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 , M = 1e6 + 10;
int n , a[N] , b[N] , dp[N] , cnt[M];

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];
	for(int i = 1 ; i < M ; i++)
		cnt[i] = cnt[i >> 1] + (i & 1);
	int ans = 0 , las = 0;
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 1 ; j < i ; j++)  
			dp[i] = (cnt[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 && cnt[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: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60