Submission #1215950

#TimeUsernameProblemLanguageResultExecution timeMemory
1215950akamizaneLongest beautiful sequence (IZhO17_subsequence)C++20
0 / 100
23 ms41544 KiB
#include<bits/stdc++.h> using namespace std; #ifdef LOCAL #include <debug.h> #else #define debug(...) 42 #endif #define int long long const int B = 10; int f[1 << 10][1 << 10][11]; vector<int> dp; int comp(int x, int y){ return dp[x] > dp[y] ? x : y; } void solve(){ int n; cin >> n; vector<int> a(n + 1), k(n + 1), par(n + 1); dp.resize(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> k[i]; debug(a, k); for (int i = 1; i <= n; i++){ int l = a[i] & ((1 << B) - 1); int r = a[i] >> B; for (int j = 0; j < (1 << B); j++){ int cur = k[i] - __builtin_popcount(j & r); if (cur >= 0){ par[i] = comp(par[i], f[l][j][cur]); } } dp[i] = dp[par[i]] + 1; for (int j = 0; j < (1 << B); j++){ f[j][r][__builtin_popcount(j & l)] = comp(f[j][r][__builtin_popcount(j & l)], i); } } int idx = max_element(dp.begin(), dp.end()) - dp.begin(); vector<int> path; while(true){ path.push_back(idx); idx = par[idx]; if (!idx) break; } reverse(path.begin(), path.end()); cout << path.size() << "\n"; for (auto x : path) cout << x << " "; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); int tt = 1; // cin >> tt; while(tt--) { 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...