제출 #855129

#제출 시각아이디문제언어결과실행 시간메모리
855129AlfraganusLongest beautiful sequence (IZhO17_subsequence)C++17
23 / 100
199 ms1628 KiB
#include <bits/stdc++.h> using namespace std; #define fs first #define ss second #define endl '\n' #define all(a) a.begin(), a.end() #define print(a) \ for (auto x : a) \ cout << x << ' '; \ cout << endl; #define printmp(a) \ for (auto x : a) \ cout << x.fs << ' ' << x.ss << endl; int BitCount(int n){ int ans = 0; while(n){ if((n & 1)) ans ++; n >>= 1; } return ans; } void solve() { int n; cin >> n; vector<int> a(n), k(n); for(int i = 0; i < n; i ++) cin >> a[i]; for(int j = 0; j < n; j ++) cin >> k[j]; if(n <= 5000){ vector<int> dp(n), maxs(n); int ans = 0, in = 0; for(int i = 0; i < n; i ++){ int mx = 0, index = -1; for(int j = i - 1; j >= 0; j --){ if(BitCount(a[i] & a[j]) == k[i] and mx < maxs[j] + 1){ mx = maxs[j] + 1; index = j; } } dp[i] = index; maxs[i] = mx; if(ans < mx){ ans = mx; in = i; } } cout << ans + 1 << endl; vector<int> p; while(in != -1) p.push_back(in + 1), in = dp[in]; reverse(all(p)); print(p) } } signed main() { ios::sync_with_stdio(0); cin.tie(0); // freopen("subsequence.in", "r", stdin); // freopen("subsequence.out", "w", stdout); int t = 1; // cin >> t; while (t--) { solve(); cout << endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...