제출 #1122515

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

subsequence

#include <bits/stdc++.h>

using namespace std;

const int M = 1024;

int n;

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 <vector <vector <int>>> dp(M+1, vector <vector <int>> (M+1, vector <int> (12,0)));
	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));
		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;
			// cout << j << ' ' << suf_a << ' ' << x << '\n';
			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(ans[i] == an-1 and b[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: 0 / 7
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60