제출 #334736

#제출 시각아이디문제언어결과실행 시간메모리
334736limabeansLongest beautiful sequence (IZhO17_subsequence)C++17
23 / 100
6049 ms2564 KiB
#include <bits/stdc++.h> using namespace std; template<typename T> void out(T x) { cout << x << endl; exit(0); } #define watch(x) cout << (#x) << " is " << (x) << endl using ll = long long; const int maxn = 1e6 + 5; int n; int a[maxn]; int k[maxn]; int dp[maxn], p[maxn]; bool compat(int i, int j) { return __builtin_popcount(a[i]&a[j]) == k[j]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for (int i=0; i<n; i++) { cin>>a[i]; } for (int i=0; i<n; i++) { cin>>k[i]; } for (int i=0; i<n; i++) { dp[i]=1; p[i]=-1; for (int j=i-1; j>=0; j--) { if (compat(j,i) && 1+dp[j]>dp[i]) { dp[i]=1+dp[j]; p[i]=j; } } } int at=n-1; for (int i=0; i<n; i++) { if (dp[i]>dp[at]) at=i; } vector<int> ans; while (~at) { ans.push_back(at); at=p[at]; } sort(ans.begin(),ans.end()); cout<<ans.size()<<"\n"; for (int i: ans) cout<<i+1<<" "; cout<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...