Submission #1314112

#TimeUsernameProblemLanguageResultExecution timeMemory
1314112boclobanchatLongest beautiful sequence (IZhO17_subsequence)C++20
23 / 100
1540 ms166128 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int sqr=320;
int A[MAXN],B[MAXN],dp[MAXN],trace[MAXN];
pair<int,int> F[1024][1024][20];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>A[i];
	for(int i=1;i<=n;i++) cin>>B[i];
	int pre=1;
	for(int i=0;i<1024;i++) for(int j=0;j<1024;j++) for(int k=0;k<=10;k++) F[i][j][k]={-1,-1};
	for(int i=1;i<=n;i++)
	{
		dp[i]=1;
		for(int j=pre;j<i;j++) if(__builtin_popcount(A[i]&A[j])==B[i]&&dp[i]<dp[j]+1) dp[i]=dp[j]+1,trace[i]=j;
		for(int j=0;j<1024;j++)
		{
			int res=B[i]-__builtin_popcount((j<<10)&A[i]);
			if(res<0) continue;
			if(dp[i]<F[j][A[i]&1023][res].first+1) dp[i]=F[j][A[i]&1023][res].first+1,trace[i]=F[j][A[i]&1023][res].second;
		}
		if(i%sqr==0)
		{
			for(int j=pre;j<=i;j++) for(int k=0;k<1024;k++)
				F[A[j]>>10][k][__builtin_popcount(k&A[j])]=max(F[A[j]>>10][k][__builtin_popcount(k&A[j])],{dp[j],j});
			pre=i+1;
		}
	}
	int ans=0,pos=0;
	for(int i=1;i<=n;i++) if(ans<dp[i]) ans=dp[i],pos=i;
	cout<<ans<<"\n";
	vector<int> vi;
	while(ans--) vi.push_back(pos),pos=trace[pos];
	reverse(vi.begin(),vi.end());
	for(auto v:vi) cout<<v<<" ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...