Submission #1159392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159392		PieArmy	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	1372 ms	51452 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;

int n;
int arr[100023],k[100023];
int bit[1024][1024],dp[1024][1024][11];
int par[100023],ans[100023];
int mx=1;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	for(int i=1;i<=n;i++){
		cin>>k[i];
	}
	for(int i=0;i<1024;i++){
		for(int j=0;j<1024;j++){
			for(int l=0;l<10;l++){
				bit[i][j]+=!!((1<<l)&(i&j));
			}
		}
	}
	for(int i=1;i<=n;i++){
		int a=(arr[i]>>10),b=(arr[i]&1023);
		ans[i]=1;
		for(int j=0;j<1024;j++){
			int need=k[i]-bit[a][j];
			if(need<0||need>10)continue;
			if(ans[dp[j][b][need]]+1>ans[i]){
				par[i]=dp[j][b][need];
				ans[i]=ans[par[i]]+1;
			}
		}
		for(int j=0;j<1024;j++){
			if(ans[i]>ans[dp[a][j][bit[b][j]]]){
				dp[a][j][bit[b][j]]=i;
			}
		}
		if(ans[i]>ans[mx])mx=i;
	}
	vector<int>v;
	cout<<ans[mx]<<endl;
	while(mx){
		v.push_back(mx);
		mx=par[mx];
	}
	while(v.size()){
		cout<<v.back()<<" ";
		v.pop_back();
	}
}

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