제출 #1100025

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1100025		Muhammet	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	1439 ms	262144 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

int n, m[10000], b[100005];

vector <int> a, k;

int bitcount(int x){
	int ans = 0;
	while(x){
		ans += (x%2);
		x /= 2;
	}
	return ans;
}

int f(int x, int k2, int ind){
	int ans = 0;
	for(int i = 0; i <= (1<<8); i++){
		// cout << x << ' ' << i << ' ' << (x&i) << ' ' << bitcount(x&i) << '\n';
		if(bitcount(x&i) == k2){
			// cout << y << ' ' << i << ' ' << m[i] << '\n';
			ans = max(ans,m[i]);
		}
	}
	return ans+1;
}

int main(){
	cin >> n;
	a.resize(n+1);
	k.resize(n+1);
	int mx = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		mx = max(mx,a[i]);
	}
	for(int i = 1; i <= n; i++){
		cin >> k[i];
	}
	if(mx > (1<<8) or n <= 5000){
		vector <int> dp(n+1,1);
		int mx = 0, ind = 1;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j < i; j++){
				if(bitcount(a[i] & a[j]) == k[i]){
					dp[i] = max(dp[i],dp[j] + 1);
				}
			}
			if(mx < dp[i]) ind = i;
			mx = max(mx,dp[i]);
		}
		cout << mx << '\n';
		vector <int> v;
		while(1){
			v.push_back(ind);
			if(dp[ind] == 1) break;
			for(int i = ind; i >= 1; i--){
				if(bitcount(a[ind] & a[i]) == k[ind] and dp[i] == dp[ind]-1){
					ind = i;
					break;
				}
			}
		}
		reverse(v.begin(), v.end());
		for(auto i : v){
			cout << i << ' ';
		}
		return 0;
	}
	int ans = 1, ind = 1;
	for(int i = 1; i <= n; i++){
		// cout << i << ' ' << k[i] << '\n';
		int yz = f(a[i],k[i],i);
		m[a[i]] = max(yz,m[a[i]]);
		b[i] = yz;
		if(m[a[i]] > ans){
			ind = i;
		}
		ans = max(ans,m[a[i]]);
		// cout << i << ' ' << m[a[i]] << '\n';
	}
	cout << ans << '\n';
	vector <int> v;
	while(1){
		v.push_back(ind);
		if(m[a[ind]] == 1 or ind == 1) break;
		for(int i = ind-1; i >= 1; i--){
			if(bitcount(a[ind] & a[i]) == k[ind] and b[i] == b[ind]-1){
				ind = i;
				break;
			}
		}
	}
	reverse(v.begin(), v.end());
	for(auto i : v){
		cout << i << ' ';
	}
}

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