Submission #502290

#	Time	Username	Problem	Language	Result	Execution time	Memory
502290		luka1234	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2431 ms	47548 KiB

subsequence

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;
int n;
int a[100001];
int b[100001];
int dp1[100001];
int dp2[1024][1024][11];
int bits[1024];
int p[100001];
int main(){
	cin>>n;
	for(int k=1;k<=n;k++)
	    cin>>a[k];
	for(int k=1;k<=n;k++)
	    cin>>b[k];
	for(int k=0;k<1024;k++){
		bits[k]=__builtin_popcount(k);
	}
	for(int i=1;i<=n;i++){
		int left=(a[i]>>10);
		int right=(a[i]&1023);
		int ind=0;
		for(int k=0;k<1024;k++){
			int sxv=b[i]-bits[(right&k)];
			if(sxv<0||sxv>10)
			   continue;
			if(dp1[dp2[left][k][sxv]]>dp1[ind]){
				ind=dp2[left][k][sxv];
			}
		}
		dp1[i]=dp1[ind]+1;
		p[i]=ind;
		for(int k=0;k<1024;k++){
			int sxv=bits[(left&k)];
			if(sxv<0||sxv>10)
			   continue;
			if(dp1[dp2[k][right][sxv]]<dp1[i]){
				dp2[k][right][sxv]=i;
			}
		}
	}
	int mx=0;
	int ind=0;
	for(int k=1;k<=n;k++){
		if(dp1[k]>mx){
			mx=dp1[k];
			ind=k;
		}
	}
	cout<<mx<<"\n";
	vector<int> ans;
	while(ind!=0){
		ans.push_back(ind);
		ind=p[ind];
	}
	reverse(ans.begin(),ans.end());
	for(int i:ans)
	    cout<<i<<' ';
	return 0;
}

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