Submission #1254970

#TimeUsernameProblemLanguageResultExecution timeMemory
1254970ThunnusLongest beautiful sequence (IZhO17_subsequence)C++17
40 / 100
6098 ms182360 KiB
#include<bits/stdc++.h> using namespace std; using i64 = long long; //#define int i64 #define vi vector<int> #define vvi vector<vi> #define vb vector<bool> #define fi first #define se second #define pii pair<int, int> #define sz(x) (int)(x).size() const int LG = 10; inline void solve(){ int n; cin >> n; vi a(n), k(n); for(int &i : a){ cin >> i; } for(int &i : k){ cin >> i; } vector<vvi> dp(1 << LG, vvi(1 << LG, vi(LG + 1))), par(1 << LG, vvi(1 << LG, vi(LG + 1, -1))); vi from(n, -1); int ans = INT32_MIN, lst = -1; for(int i = 0; i < n; i++){ int le = 0, ri = 0, lbs = 1; for(int bit = 0; bit < 2 * LG; bit++){ if(a[i] & (1 << bit)){ if(bit < LG){ le |= (1 << bit); } else{ ri |= (1 << (bit - LG)); } } } for(int mask = 0; mask < (1 << LG); mask++){ int new_mask = mask & ri; int bc = __builtin_popcountll(new_mask); if(bc > k[i] || k[i] - bc > LG) continue; if(dp[le][mask][k[i] - bc] + 1 > lbs){ from[i] = par[le][mask][k[i] - bc]; } lbs = max(lbs, dp[le][mask][k[i] - bc] + 1); } for(int mask = 0; mask < (1 << LG); mask++){ int new_mask = mask & le; int bc = __builtin_popcountll(new_mask); if(lbs > dp[mask][ri][bc]){ par[mask][ri][bc] = i; } dp[mask][ri][bc] = max(dp[mask][ri][bc], lbs); } if(lbs > ans){ ans = lbs; lst = i; } } cout << ans << "\n"; vi lbs; while(from[lst] != -1){ lbs.emplace_back(lst + 1); lst = from[lst]; } lbs.emplace_back(lst + 1); reverse(lbs.begin(), lbs.end()); for(int &i : lbs){ cout << i << " "; } cout << "\n"; return; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; //cin >> t; while(t--){ solve(); } 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...