Submission #1122521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122521		Muhammet	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2245 ms	50896 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

const int M = 1024;

int n, dp[M+1][M+1][12];

int main(){
	cin >> n;
	vector <int> a(n+1), k(n+1), b(M+1);
	for(int i = 0; i <= M; i++){
		b[i] = __builtin_popcount(i);
	}
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	for(int i = 1; i <= n; i++){
		cin >> k[i];
	}
	vector <int> ans(n+1,0);
	int an = 1;
	for(int i = 1; i <= n; i++){
		int pref_a = (a[i]/M), suf_a = (a[i]-(pref_a*M));
		ans[i] = 1;
		if(suf_a < 0) continue;
		for(int j = 0; j <= M; j++){
			int x = (k[i] - b[pref_a&j]);
			if((x < 0) or (x > 10)) continue;
			ans[i] = max(ans[dp[j][suf_a][x]]+1,ans[i]);
		}
		for(int j = 0; j <= M; j++){
			if(ans[dp[pref_a][j][b[j&suf_a]]] < ans[i]) dp[pref_a][j][b[j&suf_a]] = i;
		}
		an = max(an, ans[i]);
	}
	cout << an << '\n';
	vector <int> c;
	int ind = 0;
	for(int i = n; i >= 1; i--){
		if(ans[i] == an){
			ind = i;
			// break;
		}
	}
	c.push_back(ind);
	for(int i = ind-1; i >= 1; i--){
		if(an == 0) break;
		if(ans[i] == an-1 and __builtin_popcount(a[i]&a[ind]) == k[ind]){
			ind = i;
			an--;
			c.push_back(i);
		}
	}
	sort(c.begin(), c.end());
	for(auto i : c){
		cout << i << " ";
	}

	return 0;
}

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