제출 #1006701

#제출 시각아이디문제언어결과실행 시간메모리
1006701SulALongest beautiful sequence (IZhO17_subsequence)C++17
40 / 100
6009 ms6748 KiB
#include <bits/stdc++.h> using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; int a[n+1], k[n+1], bitcount[1<<20]; 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 << 20; i++) { bitcount[i] = __builtin_popcount(i); } int dp[n+1] = {}, pre[n+1]; for (int i = 1; i <= n; i++) { dp[i] = 1; pre[i] = i; for (int j = 1; j < i; j++) if (bitcount[a[i] & a[j]] == k[i]) { if (dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; pre[i] = j; } } } int final = max_element(dp, dp+n+1) - dp; vector<int> ans; while (pre[final] != final) { ans.push_back(final); final = pre[final]; } ans.push_back(final); reverse(ans.begin(), ans.end()); cout << ans.size() << '\n'; for (int i : ans) cout << i << " "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...