제출 #757866

#제출 시각아이디문제언어결과실행 시간메모리
757866shadow_samiLongest beautiful sequence (IZhO17_subsequence)C++17
0 / 100
1 ms468 KiB
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; const int B = 8; struct State { int len, end; }; int main() { // preprocess: // bc[i][j] = bit_count(i & j) vector<vector<int>> bc(1 << B, vector<int>(1 << B)); for (int i = 0; i < (1 << B); i++) { for (int j = 0; j < (1 << B); j++) { bc[i][j] = __builtin_popcount(i & j); } } int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<int> k(n); for (int i = 0; i < n; i++) cin >> k[i]; int ans = 1; // best_i: most optimal index to end on int best_i = 0; vector<int> prv(n); // prv[i]: best index to include before i iota(prv.begin(), prv.end(), 0); // prv[i] = i vector<State> dp1(1 << B, State{-1, -1}); for (int i = 0; i < n; i++) { if (dp1[a[i]].len == -1) { dp1[a[i]].len = 1; dp1[a[i]].end = i; } for (int j = 0; j < (1 << B); j++) { if (bc[j][a[i]] == k[i] && dp1[j].len + 1 > dp1[a[i]].len) { dp1[a[i]].len = dp1[j].len + 1; dp1[a[i]].end = i; prv[i] = dp1[j].end; } } if (dp1[a[i]].len > ans) { ans = dp1[a[i]].len; best_i = i; } } cout << ans << endl; vector<int> res; while (prv[best_i] != best_i) { res.push_back(best_i); best_i = prv[best_i]; } res.push_back(best_i); reverse(res.begin(), res.end()); for (int x : res) { cout << x + 1 << " "; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...