제출 #1306388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306388		coolboy19521	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	5562 ms	190980 KiB

subsequence

#include "bits/stdc++.h"

#define FOR(i,a,b)for(int i=(a);i<(b);i++)
#define F0R(i,a)FOR(i,0,a)
#define ROF(i,a,b)for(int i=(b)-1;i>=(a);i--)
#define R0F(i,a)ROF(i,0,a)
#define REP(a)F0R(_,a)

using namespace std;

const int mxn=1e5+20,mxb=21,b=11;

int a[mxn],k[mxn],dp[1<<b][1<<b][mxb],pos[1<<b][1<<b][mxb],bc[1<<b][1<<b],prv[mxn];

int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	F0R(i,1<<b)FOR(j,i,1<<b)bc[i][j]=bc[j][i]=__builtin_popcount(i&j);
	int n;cin>>n;
	F0R(i,n)cin>>a[i];
	F0R(i,n)cin>>k[i];
	int ans=1,en=0;
	F0R(i,n){
		int l=a[i]>>b,r=a[i]%(1<<b),loc=1;
		prv[i]=-1;
		F0R(j,1<<b){
			int need=k[i]-bc[l][j];
			if(need<0 or need>b)continue;
			if(dp[j][r][need]+1>loc){
				loc=dp[j][r][need]+1;
				prv[i]=pos[j][r][need];
			}
		}
		if(loc>ans)ans=loc,en=i;
		F0R(j,1<<b)if(loc>dp[l][j][bc[r][j]]){
			dp[l][j][bc[r][j]]=loc;
			pos[l][j][bc[r][j]]=i;
		}
	}
	cout<<ans<<'\n';
	vector<int>res;
	for(;~en;en=prv[en])res.push_back(en);
	reverse(begin(res),end(res));
	for(int i:res)cout<<i+1<<' ';cout<<'\n';
}

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