제출 #1125502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125502		Joseph0121	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2942 ms	95980 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int B = 10;
int bc[1<<B][1<<B];
struct State{
	int len = 0, end = 0;
}dp[1<<B][1<<B][B+1];

//dp[l][r][k]
int main() {
	int n; cin>>n;
	vector<int> a(n);
	for(auto &i: a) cin>>i;
	vector<int> k(n);
	for(auto &i: k) cin>>i;
	vector<int> prev(n);
	iota(prev.begin(),prev.end(),0);
	int ans = 1, best = 0;
	for(int i = 0;i<(1<<B);i++) for(int j = 0;j<(1<<B);j++) bc[i][j] = __builtin_popcount(i&j);
	for(int i = 0;i<n;i++){
		int l = a[i]>>B;
		int r = a[i]%(1<<B);
		//transitions
		int lbs = 1;
		for(int j = 0;j<(1<<B);j++){
			int need = k[i]-bc[j][l];
			if(need < 0 || need > B) continue;
			if(dp[j][r][need].len+1 > lbs){
				lbs = dp[j][r][need].len+1;
				prev[i] = dp[j][r][need].end;
			}
		}
		//finds lbs, now with updating states
		for(int j = 0;j<(1<<B);j++){
			//dp[l][r][k] means can transition from a[i] to r, with bc[a[i]][r] = k
			//therefore, I should enumerate r and find k
			if(dp[l][j][bc[r][j]].len < lbs){
				dp[l][j][bc[r][j]].len = lbs;
				dp[l][j][bc[r][j]].end = i;
			}
		}
		if(lbs > ans){
			ans = lbs;
			best = i;
		}
		
	}
	// for(int i = 0;i<n;i++) cout<<prev[i]<<" ";
	// cout<<endl;
	vector<int> output;
	while(prev[best]!=best){
		output.push_back(best);
		best = prev[best];
	}
	output.push_back(best);
	cout<<output.size()<<endl;
	reverse(output.begin(),output.end());
	for(auto i: output) cout<<i+1<<" ";
	
	
	// your code goes here
	return 0;
}

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