Submission #862433

#TimeUsernameProblemLanguageResultExecution timeMemory
862433KK_1729Longest beautiful sequence (IZhO17_subsequence)C++17
0 / 100
0 ms456 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define pb push_back #define all(a) a.begin(), a.end() #define endl "\n" void printVector(vector<int> a){ for (auto x: a) cout << x << " "; cout << endl; } void solve(){ int n; cin >> n; vector<int> a(n); FOR(i,0,n) cin >> a[i]; vector<int> k(n); FOR(i,0,n) cin >> k[i]; vector<int> dp(n, 1); vector<int> prev(n, -1); dp[0] = 1; for (int i = 1; i < n; ++i){ for (int j = 0; j < i; ++j){ if (__builtin_popcount(a[i]&a[j]) == k[i]){ if (dp[j]+1 > dp[i]) prev[i] = j; dp[i] = dp[j]+1; } } } int ans = 0; int best = -1; FOR(i,0,n){ if (dp[i] > ans){ ans = dp[i]; best = i; } } vector<int> items; while (prev[best] != -1){ items.pb(best+1); best = prev[best]; } items.pb(best+1); reverse(all(items)); cout << ans << endl; printVector(items); } int32_t main(){ ios::sync_with_stdio(false); cin.tie(0); int t = 1; while (t--) 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...