제출 #1321700

#제출 시각아이디문제언어결과실행 시간메모리
1321700LudisseyLongest beautiful sequence (IZhO17_subsequence)C++20
40 / 100
3378 ms327680 KiB
#include <bits/stdc++.h> #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() using namespace std; const int LOG=10; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); vector<int> k(n); vector<int> v(n); vector<int> prev(n,-1); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> k[i]; vector<vector<unordered_map<int,pair<int,int>>>> dp((1<<LOG), vector<unordered_map<int,pair<int,int>>>(LOG+1)); for (int i = 0; i < n; i++) { int aL=a[i]%((1<<LOG)); int aR=a[i]/((1<<LOG)); v[i]=1; for (int b = 0; b < (1<<LOG); b++) { int bp=__builtin_popcount(aR&b); if(bp>k[i]||k[i]-bp>LOG) continue; int vl=dp[aL][k[i]-bp][b].first+1; if(vl>v[i]) prev[i]=dp[aL][k[i]-bp][b].second; v[i]=max(v[i],vl); } for (int b = 0; b < (1<<LOG); b++) { int bp=__builtin_popcount(aL&b); if(v[i]>dp[b][bp][aR].first) dp[b][bp][aR]={v[i],i}; } } int x=max_element(all(v))-v.begin(); cout << v[x] << "\n"; vector<int> outp; while(x>=0){ outp.push_back(x); x=prev[x]; } for (int i = sz(outp)-1; i >= 0; i--) cout << outp[i]+1 << " "; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...