Submission #520648

#TimeUsernameProblemLanguageResultExecution timeMemory
520648CantfindmeLongest beautiful sequence (IZhO17_subsequence)C++17
7 / 100
259 ms163512 KiB
#include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int> pi; #define f first #define s second #define FAST ios_base::sync_with_stdio(0); cin.tie(0); #define all(x) x.begin(),x.end() const int maxn = 100010; const int INF = LLONG_MAX/2; const int mod = 1e9+7; int n; int A[maxn], K[maxn]; pi dp[1<<10][1<<10][10]; //L, all BM, match between BM and R int trace[maxn]; int32_t main() { FAST cin >> n; for (int i =1;i<=n;i++) cin >> A[i]; for (int i =1;i<=n;i++) cin >> K[i]; pi rans = pi(0,0); for (int i =1;i<=n;i++) { int L = A[i] >> 10; int R = A[i] & ((1<<10)-1); pi best = pi(0,0); for (int prevl = 0; prevl < (1 << 10); prevl++) { int need = K[i] - __builtin_popcount(prevl & L); if (need < 0 or need > 10) continue; best = max(best, dp[prevl][R][need]); } best.f += 1; trace[i] = best.s; rans = max(rans, pi(best.f, i)); for (int bm = 0; bm < (1<<10);bm++) { int match = __builtin_popcount(R & bm); dp[L][bm][match] = max(dp[L][bm][match], pi(best.f, i)); } } vector <int> ans; int indx = rans.s; while (indx != 0) { ans.push_back(indx); indx = trace[indx]; } reverse(all(ans)); cout << ans.size() << "\n"; for (auto i: ans) cout << i << " "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...