Submission #172359

#TimeUsernameProblemLanguageResultExecution timeMemory
172359LightningLongest beautiful sequence (IZhO17_subsequence)C++14
23 / 100
140 ms2044 KiB
#include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <set> #include <map> #include <iomanip> #include <stack> #include <queue> #include <deque> using namespace std; typedef long long ll; typedef pair <int, int> pii; #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define pb push_back #define ppb pop_back #define mkp make_pair #define F first #define S second #define show(a) cerr << #a <<" -> "<< a <<"\n" #define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d)) #define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d)) //#define int ll const int N = 2e5 + 5; const int INF = 1e9 + 5; int n, a[N], k[N], dp[N], p[N], posans, pos[N]; int main () { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i = 1; i <= n; ++i) { cin >> a[i]; } for(int i = 1; i <= n; ++i) { cin >> k[i]; } int ans = 0, posans = 0; for(int i = 1; i <= n; ++i) { int mx = 0; if(n <= 5000) { for(int j = 1; j < i; ++j) { if(__builtin_popcount((a[i] & a[j])) == k[i]) { if(mx < dp[j]) { mx = dp[j]; p[i] = j; } } } } else { for(int j = 0; j < (1 << 8); ++j) { if(pos[j] != 0 && __builtin_popcount((a[i] & j)) == k[i]) { if(mx < dp[pos[j]]) { mx = dp[pos[j]]; p[i] = pos[j]; } } } pos[a[i]] = i; } dp[i] = mx + 1; if(ans < dp[i]) { ans = dp[i]; posans = i; } } vector <int> vec; while(posans) {vec.pb(posans); posans = p[posans];} reverse(all(vec)); cout << ans <<'\n'; for(int it : vec) cout << it <<' '; return 0; } /* 4 1 2 3 4 10 0 1 0 5 5 3 5 3 5 10 1 20 1 20 */ /* ------------------------------------------------------------------------------------------- If you only do what you can do, You will never be more than you are now! ------------------------------------------------------------------------------------------- We must all suffer from one of two pains: the pain of discipline or the pain of regret. The difference is discipline weighs grams while regret weighs tons. ------------------------------------------------------------------------------------------- */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...