제출 #1333117

#제출 시각아이디문제언어결과실행 시간메모리
1333117aaaaaaaaLongest beautiful sequence (IZhO17_subsequence)C++20
0 / 100
1 ms344 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((1 << 10), 1), pos((1 << 10), -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_dp = {0, -1};

    for(int i = 1; i <= n; ++i){
        pair<int, int> mx = {0, -1};
        for(int j = 0; j < (1 << 8); ++j){
            if(__builtin_popcount(a[i] & j) == b[i] && pos[j] != -1){
                mx = max(mx, {dp[j] + 1, pos[j]});
            }
        }
        dp[a[i]] = max(dp[a[i]], mx.first);
        par[i] = mx.second;
        mx_dp = max(mx_dp, {dp[a[i]], i});
        pos[a[i]] = i;
    }


vector<int> ans;
int i = mx_dp.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...