Submission #1333114

#TimeUsernameProblemLanguageResultExecution timeMemory
1333114aaaaaaaaLongest beautiful sequence (IZhO17_subsequence)C++20
23 / 100
6093 ms3396 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> a(n + 5, 0), b(n + 5, 0), dp(n + 5, 1), par(n + 5, -1);

    for(int i = 1; i <= n; ++i){
        cin >> a[i];
    }

    for(int i = 1; i <= n; ++i){
        cin >> b[i];
    }

    pair<int, int> mx = {0, 0};

    for(int i = 1; i <= n; ++i){
        for(int j = i - 1; j >= 1; --j){
            if(__builtin_popcount(a[i] & a[j]) == b[i] && dp[i] < dp[j] + 1){
                dp[i] = dp[j] + 1;
                par[i] = j;
            }
        }
        mx = max(mx, {dp[i], i});
    }

vector<int> ans;
int i = mx.second;


while(i != -1){
    ans.push_back(i);
    i = par[i];
}


    cout << (int) ans.size() << "\n";
reverse(ans.begin(), ans.end());
    for(auto it : ans) cout << it << " ";

    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...