Submission #1314114

#TimeUsernameProblemLanguageResultExecution timeMemory
1314114boclobanchatLongest beautiful sequence (IZhO17_subsequence)C++20
100 / 100
3501 ms174488 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][21]; 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<=20;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...