제출 #1333121

#제출 시각아이디문제언어결과실행 시간메모리
1333121aaaaaaaaLongest beautiful sequence (IZhO17_subsequence)C++20
0 / 100
0 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 + 1), b(n + 1), par(n + 1, 0);
    vector<int> dp(1 << 8, 0), pos(1 << 8, 0);

    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, 0};

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

    vector<int> ans;
    int i = mx_dp.second;
    while(i > 0){
        ans.push_back(i);
        i = par[i];
    }
    reverse(ans.begin(), ans.end());

    cout << ans.size() << "\n";
    for(auto it : ans) cout << it << " ";
    cout << "\n";

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