Submission #659295

#	Time	Username	Problem	Language	Result	Execution time	Memory
659295		ono_de206	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2120 ms	51448 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
 
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
 
//#define int long long
 
template<typename T>
void mxx(T &a, T b){if(b>a) a=b;}
template<typename T>
void mnn(T &a, T b){if(b<a) a=b;}
 
const int mxn=11,mxxa=1e5+10;
 
int dp[1<<mxn][1<<mxn][mxn];
int cm[mxxa],dd[mxxa];
 
int a[mxxa],k[mxxa];
int kkk[1<<mxn];

signed main(){
	fast;
	int n,m;
	cin>>n;
  	for(int i=0; i<(1<<10); i++) kkk[i]=__builtin_popcount(i);
	for(int i=1; i<=n; i++){
		cin>>a[i];
	}
	for(int i=1; i<=n; i++){
		cin>>k[i];
	}
	for(int i=1; i<=n; i++){
		cm[i]=i;
		dd[i]=1;
	}
	for(int i=1; i<=n; i++){
		int l=(a[i]>>10);
		int r=((1<<10)-1)&a[i];
		for(int j=0; j<(1<<10); j++){
			int gg=(j&l);
			gg=kkk[gg];
			if(gg>k[i]) continue;
			gg=k[i]-gg;
          	if(gg>10) continue;
			if(dd[dp[j][r][gg]]+1>dd[i]){
				dd[i]=dd[dp[j][r][gg]]+1;
				cm[i]=dp[j][r][gg];
			}
		}
		for(int j=0; j<(1<<10); j++){
			int gg=(j&r);
			gg=kkk[gg];
			if(dd[i]>dd[dp[l][j][gg]]){
				dp[l][j][gg]=i;
			}
		}
	}
//	for(int i=1; i<=n; i++){
//		cout<<dd[i]<<' ';
//	}
//	cout<<'\n';
	int idx=0;
	int mx=0;
	for(int i=1; i<=n; i++) if(dd[i]>mx){
		mx=dd[i];
		idx=i;
	} 
	vector<int> ans;
	while(cm[idx]!=idx){
		ans.pb(idx);
		idx=cm[idx];
	}
	if(idx!=0) ans.pb(idx);
	reverse(all(ans));
	cout<<mx<<'\n';
	for(int x : ans){
		cout<<x<<' ';
	}
	return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:29:8: warning: unused variable 'm' [-Wunused-variable]
   29 |  int n,m;
      |        ^

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