Submission #968876

#TimeUsernameProblemLanguageResultExecution timeMemory
968876starchanLongest beautiful sequence (IZhO17_subsequence)C++17
0 / 100
9 ms9308 KiB
#include<bits/stdc++.h> using namespace std; #define in array<int, 2> #define pb push_back #define pob pop_back #define INF (int)1e17 #define fast() ios_base::sync_with_stdio(false); cin.tie(NULL) const int N = 1<<10; const int LOGM = 21; const int MX = 1e5+3; int cnt[N][N]; void pre() { cnt[0][0] = 0; for(int i = 0; i < N; i++) { for(int j = (i == 0); j < N; j++) cnt[i][j] = cnt[i/2][j/2]+(i*j)%2; } return; } in ans; in dp[LOGM][N][N]; int p[MX]; signed main() { fast(); pre(); int n; cin >> n; vector<int> a(n+1); for(int i = 1; i <= n; i++) cin >> a[i]; vector<int> k(n+1); for(int i = 1; i <= n; i++) cin >> k[i]; for(int i = 1; i <= n; i++) { in val = {0,0}; for(int j = 0; j < N; j++) { int d = cnt[a[i]/n][j]; if(k[i] >= d) val = max(val, dp[k[i]-d][j][a[i]%N]); } p[i] = val[1]; ans = max(ans, {++val[0], i}); for(int j = 0; j < N; j++) dp[cnt[j][a[i]%N]][a[i]/N][j] = max(dp[cnt[j][a[i]%N]][a[i]/N][j], {val[0], i}); } vector<int> v; int x = ans[1]; while(x) { v.pb(x); x = p[x]; } reverse(v.begin(), v.end()); cout << v.size() << "\n"; for(auto x: v) cout << x << " "; cout << "\n"; 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...