Submission #738941

#	Time	Username	Problem	Language	Result	Execution time	Memory
738941		MODDI	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	117 ms	1868 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n;
vi arr, k;
int main(){
	cin>>n;
	arr.resize(n);
	k.resize(n);
	bool uslov = true;
	for(int i = 0; i < n; i++)	
	{
		cin>>arr[i];
		if(arr[i] > (1 << 8))	uslov = false;
	}
	for(int i = 0; i < n; i++)	cin>>k[i];
	if(n <= 5000){
		int dp[5001], from[5001], ans = 0;
		memset(dp, 0, sizeof dp);
		dp[0] = 1;
		for(int i = 1; i < n; i++){
			dp[i] = 1;
			from[i] = i;
			for(int j = i-1; j >= 0; j--){
				if(__builtin_popcount(arr[i] & arr[j]) == k[i]){
					dp[i] = max(dp[i], 1 + dp[j]);
					if(dp[i] == 1 + dp[j])	from[i] = j;
				}
			}
		}
		vi ans_arr;
		int at = 0;
		for(int i = 0; i < n; i++){
			if(ans < dp[i]){
				ans = dp[i];
				at = i;
			}
		}
		while(from[at] != at){
			ans_arr.pb(at);
			at = from[at];
		}
		ans_arr.pb(at);
		reverse(ans_arr.begin(), ans_arr.end());
		cout<<ans<<endl;
		for(auto t : ans_arr)
			cout<<t+1<<" ";
		cout<<endl;
	}
	else if(uslov){
		int dp[100100], from[100100], pos[1<<8];
		dp[0] = 1;
		from[0] = 0;
		memset(pos, -1, sizeof pos);
		for(int i = 1; i < n; i++){
			dp[i] = 1;
			from[i] = i;
			for(int j = 0; j < (1 << 8); j++){
				if(__builtin_popcount(arr[i] & j) == k[i]){
					if(pos[j] != -1){
						dp[i] = max(dp[i], 1 + dp[pos[j]]);
						if(dp[i] == 1 + dp[pos[j]])
							from[i] = pos[j];
					}
				}
			}
			if(dp[i] > dp[pos[arr[i]]]){
				pos[arr[i]] = i;
			}
		}
		int ans = 0, at = 0;
		for(int i = 0; i < n; i++)
		{
			ans = max(ans, dp[i]);
			if(ans == dp[i])
				at = i;
		}
		vi ans_arr;
		while(from[at] != at){
			ans_arr.pb(at);
			at = from[at];
		}
		ans_arr.pb(at);
		reverse(ans_arr.begin(), ans_arr.end());
		cout<<ans<<endl;
		for(auto t : ans_arr)
			cout<<t+1<<" ";
		cout<<endl;
	}
	return 0;
}

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