Submission #890386

#	Time	Username	Problem	Language	Result	Execution time	Memory
890386		12345678	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	6034 ms	2432 KiB

subsequence

#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
*/

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60