#include <bits/stdc++.h>
using namespace std;
//dp[N] = longest subsequence ending with Nth number (so im = N)
const int maxn = 5e3+5;
int N;
int from[maxn];
int a[maxn], k[maxn],dp[maxn];
int main() {
cin>>N;
for(int i = 1;i<=N;i++) cin>>a[i];
for(int i = 1;i<=N;i++) cin>>k[i];
for(int i = 1;i<=N;i++){
dp[i] = 1;
}
dp[1] = 1;
for(int i = 2;i<=N;i++){
for(int j = 1;j<=i-1;j++){
if(__builtin_popcount(a[i]&a[j]) == k[i]){
if(dp[j]+1 > dp[i]){
dp[i] = dp[j]+1;
from[i] = j;
}
}
}
}
// for(int i = 1;i<=N;i++) cout<<from[i]<<" ";
// cout<<endl;
int idx = 1;
for(int i = 2;i<=N;i++){
if(dp[i] > dp[idx]) idx = i;
}
vector<int> ans;
// cout<<idx<<endl;
while(dp[idx]!=1){
ans.push_back(idx);
idx = from[idx];
}
ans.push_back(idx);
reverse(ans.begin(),ans.end());
cout<<ans.size()<<endl;
for(auto i: ans) cout<<i<<" ";
// for(int i = 1;i<=N;i++){
// cout<<ans[i]<<" ";
// }
// your code goes here
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |