Submission #738927

#	Time	Username	Problem	Language	Result	Execution time	Memory
738927		MODDI	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	116 ms	2604 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);
	for(int i = 0; i < n; i++)	cin>>arr[i];
	for(int i = 0; i < n; i++)	cin>>k[i];
	
	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;
	return 0;
}

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