Submission #934453

#	Time	Username	Problem	Language	Result	Execution time	Memory
934453		parsadox2	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	6060 ms	7044 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 = (1 << 20) + 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++)
	{
		int dard = 0;
		for(int j = 1 ; j < i ; j++)  
			dard = MAX(dard , __builtin_popcount((a[i] & a[j])) == b[i] ? dp[j] : 0);
		dp[i] = dard + 1;
		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;
		}
	}
	cout << ans << '\n';
	for(int i = ans - 1 ; i > -1 ; i--)
		cout << res[i] << " ";
	cout << '\n';
	return 0;
}

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