Submission #334779

#TimeUsernameProblemLanguageResultExecution timeMemory
334779limabeansLongest beautiful sequence (IZhO17_subsequence)C++17
40 / 100
6084 ms56096 KiB
#include <bits/stdc++.h> using namespace std; template<typename T> void out(T x) { cout << x << endl; exit(0); } #define watch(x) cout << (#x) << " is " << (x) << endl using ll = long long; const int maxn = 1e6 + 5; int n; int a[maxn]; int k[maxn]; int dp[maxn], p[maxn]; int store[1024][1024][12]; int count(int mask) { return __builtin_popcount(mask); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for (int i=1; i<=n; i++) { cin>>a[i]; } for (int i=1; i<=n; i++) { cin>>k[i]; } memset(p,-1,sizeof(p)); //store[mask][mask2][cnt]: best index if our top10bits=mask, and we merge with someone whose lower10bits=mask2, // and we need cnt bits in the top10 for (int i=1; i<=n; i++) { int l = (a[i]>>10); int r = (a[i]&1023); //qry int best = 0; for (int mask=0; mask<1024; mask++) { int need = k[i] - count(mask&r); if (need>10 || need<0) continue; if (dp[best]<dp[store[l][mask][need]]) { best=store[l][mask][need]; } } dp[i]=1+dp[best]; p[i]=best; //insert for (int mask=0; mask<1024; mask++) { int cnt = count(mask&l); if (dp[store[mask][r][cnt]] < dp[i]) { store[mask][r][cnt] = i; } } } int at = 1; for (int i=1; i<=n; i++) { if (dp[at]<dp[i]) at=i; } vector<int> ans; while (at) { ans.push_back(at); at=p[at]; } sort(ans.begin(),ans.end()); cout<<ans.size()<<endl; for (int i: ans) cout<<i<<" "; cout<<endl; 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...