Submission #314283

#	Time	Username	Problem	Language	Result	Execution time	Memory
314283		kshitij_sodani	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5433 ms	93524 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n' 
#define cot __builtin_popcount
int it[100001];
int kk[100001];
int n;
int dp[1024][1024][11];
int back[1024][1024][11];
int back2[100001];
int dp2[100001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>it[i];
	}
	for(int i=0;i<n;i++){
		cin>>kk[i];
	}
	for(int i=0;i<n;i++){
		int aa=1;
		int val=it[i]&1023;
		int val2=(it[i]-val)/1024;
		//cout<<val<<":"<<val2<<endl;
		back2[i]=-1;
		for(int j=0;j<1024;j++){
			if(cot(j&val)>kk[i]){
				continue;
			}
			if(kk[i]-cot(j&val)>10){
				continue;
			}
			if(dp[j][val2][kk[i]-cot(j&val)]+1>aa){
				back2[i]=back[j][val2][kk[i]-cot(j&val)];
			}
			aa=max(aa,dp[j][val2][kk[i]-cot(j&val)]+1);
		}

	//	cout<<aa<<":"<<endl;
		dp2[i]=aa;
		//ans=max(ans,aa);
		for(int j=0;j<1024;j++){
			if(aa>dp[val][j][cot(j&val2)]){
				back[val][j][cot(j&val2)]=i;
			}
			dp[val][j][cot(j&val2)]=max(dp[val][j][cot(j&val2)],aa);
		}
	}
	int ma=0;
	int ind=-1;
	for(int i=0;i<n;i++){
		if(dp2[i]>ma){
			ma=dp2[i];
			ind=i;
		}
	}
	vector<int> ans;
	ans.pb(ind);
	while(true){
		ind=back2[ind];
		if(ind==-1){
			break;
		}
		ans.pb(ind);
	}
	cout<<ma<<endl;
	while(ans.size()){
		cout<<ans.back()+1<<" ";
		ans.pop_back();
	}
	cout<<endl;








	return 0;
}

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