제출 #1006665

#제출 시각아이디문제언어결과실행 시간메모리
1006665emad234Longest beautiful sequence (IZhO17_subsequence)C++17
23 / 100
99 ms31060 KiB
#include "bits/stdc++.h" #define F first #define S second #define ll long long #define pii pair<ll,ll> const ll mxN = 5e5 + 5; const ll mod = 1e9 + 7; using namespace std; int a[mxN],b[mxN]; int dp[mxN]; int opt[mxN],opid[mxN]; vector<int>op[256]; int prv[mxN]; signed main(){ ios_base::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]; } if(n > 5000){ for(int i = 1;i <= n;i++){ for(int x = 0;x <= 256;x++){ if(__builtin_popcount(a[i] & x) == b[i]) op[i].push_back(x); } } } int ans = 1; int mxid = 1; dp[1] = 1; if(n > 5000){ opt[a[1]] = 1; opid[a[1]] = 1; for(int i = 2;i <= n;i++){ dp[i] = 1; for(auto x : op[i]){ if(opt[x] >= dp[i]){ dp[i] = opt[x] + 1; prv[i] = opid[x]; } } if(opt[a[i]] < dp[i]){ opt[a[i]] = dp[i]; opid[a[i]] = i; } if(dp[i] > ans){ ans = dp[i]; mxid = i; } } }else{ for(int i = 2;i <= n;i++){ dp[i] = 1; for(int j = 1;j < i;j++){ if(__builtin_popcount(a[i] & a[j]) == b[i]) { if(dp[j] + 1 > dp[i]){ dp[i] = dp[j] + 1; prv[i] = j; } } } if(dp[i] > ans){ ans = dp[i]; mxid = i; } } } cout<< ans<<'\n'; vector<int>v; while(mxid){ v.push_back(mxid); mxid = prv[mxid]; } reverse(v.begin(),v.end()); for(auto x : v) cout<<x<<' '; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...