Submission #1193367

#TimeUsernameProblemLanguageResultExecution timeMemory
1193367chaeryeongLongest beautiful sequence (IZhO17_subsequence)C++20
0 / 100
38 ms86596 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int B = 20; int f[1 << (B / 2)][1 << (B / 2)][B + 1]; const int MAXN = 1e5 + 25; int par[MAXN], dp[MAXN], n, a[MAXN], k[MAXN]; int comp (int x, int y) { return dp[x] < dp[y] ? y : x; } inline int popcount (int x) { return __builtin_popcount(x); } void solve () { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) { cin >> k[i]; } for (int i = 0; i < (1 << (B / 2)); i++) { for (int j = 0; j < (1 << (B / 2)); j++) { for (int k = 0; k <= B; k++) { f[i][j][k] = 1; } } } dp[1] = 1; for (int i = 2; i <= n; i++) { int x = (a[i]) & ((1 << (B / 2)) - 1); int y = (a[i] >> (B / 2)); for (int j = 0; j < (1 << (B / 2)); j++) { int s = k[i] - popcount(j & y); if (s >= 0) { par[i] = comp(par[i], f[x][j][s]); } } dp[i] = 1 + dp[par[i]]; for (int j = 0; j < (1 << (B / 2)); j++) { f[j][y][popcount(j & x)] = comp(f[j][y][popcount(j & x)], i); } } int pos = *max_element(dp + 1, dp + n + 1); vector <int> ii; while (pos) { ii.push_back(pos); pos = par[pos]; } reverse(ii.begin(), ii.end()); cout << (int)ii.size() << '\n'; for (auto i : ii) { cout << i << " "; } cout << '\n'; } signed main () { ios::sync_with_stdio(0); cin.tie(0); int tc = 1; //cin >> tc; while (tc--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...