Submission #1254415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254415		kerem	Longest beautiful sequence (IZhO17_subsequence)	C++20	7 / 100	163 ms	81900 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
//~ #define int long long
#define fr first
#define sc second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e15
#define N 1024
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;

int dp[N][N][20];
void solve(){
	int n;
	cin >> n;
	int a[n],k[n],d[n];
	for(int i=0;i<n;i++) cin >> a[i];
	for(int i=0;i<n;i++) cin >> k[i];
	for(int i=0;i<n;i++){
		d[i]=1;
		int L=a[i]>>10,R=a[i]%N;
		for(int iL=0;iL<N;iL++){
			int t=__builtin_popcount(iL&L);
			if(t>k[i]) continue;
			d[i]=max(d[i],dp[iL][R][k[i]-t]+1);
		}
		for(int iR=0;iR<N;iR++){
			int t=__builtin_popcount(iR&R);
			dp[L][iR][t]=max(dp[L][iR][t],d[i]);
		}
	}
	int mx=0,j;
	for(int i=0;i<n;i++)
		if(mx<d[i])
			mx=d[i],j=i;
	cout << mx << endl;
	vector<int> v;
	v.pb(j);
	for(int i=j-1;i>=0;i--){
		if(d[i]+1==d[j] && __builtin_popcount(a[i]&a[j])==k[j]){
			j=i;v.pb(j);
		}
	}
	reverse(all(v));
	for(auto i:v)
		cout << i+1 << " ";
}
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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