제출 #890386

#제출 시각아이디문제언어결과실행 시간메모리
89038612345678Longest beautiful sequence (IZhO17_subsequence)C++17
23 / 100
6034 ms2432 KiB
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;
int n, dp[nx], v[nx], k[nx], l[nx];
pair<int, int> t;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>v[i], l[i]=i;
    for (int i=1; i<=n; i++) cin>>k[i];
    t={1, 1};
    for (int i=1; i<=n; i++)
    {
        dp[i]=1;
        for (int j=i-1; j>=1; j--) if (__builtin_popcount(v[j]&v[i])==k[i]&&dp[j]+1>dp[i]) dp[i]=dp[j]+1, l[i]=j, t=max(t, {dp[i], i});
        //cout<<i<<' '<<dp[i]<<' '<<l[i]<<'\n';
    }
    cout<<t.first<<'\n';
    vector<int> res;
    while (l[t.second]!=t.second) res.push_back(t.second), t.second=l[t.second];
    res.push_back(t.second);
    reverse(res.begin(), res.end());
    for (auto x:res) cout<<x<<' ';
}

/*
4
1 2 3 4
10 0 1 0

5
5 3 5 3 5
10 1 20 1 20
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...