Submission #844730

#	Time	Username	Problem	Language	Result	Execution time	Memory
844730		Pa_sha	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5723 ms	184764 KiB

subsequence

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
constexpr int mod=1e9+7;
array<int,2>dp[(1ll<<10)][(1ll<<10)][11];
void solve()
{
    int n;
    cin>>n;
    int a[n],k[n];
    int to[n]={0},ans=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i=0;i<n;i++)
    {
        to[i]=-1;
        cin>>k[i];
    }
    vector<int>res;
    int q=0;
    for(int i=0;i<n;i++)
    {
        int l=(a[i]>>10);
        int r=a[i]%(1ll<<10);
        int rs=1;
        for(int j=0;j<(1ll<<10);j++)
        {
            int nd=k[i]-__builtin_popcount(j&l);
            if(nd<0||nd>10)
            {
                continue;
            }
            if(dp[j][r][nd][0]+1>rs)
            {
                rs=dp[j][r][nd][0]+1;
                to[i]=dp[j][r][nd][1];
            }
        }
        if(rs>ans)
        {
            ans=rs;
            q=i;
        }
        for(int j=0;j<(1ll<<10);j++)
        {
            if(rs>dp[l][j][__builtin_popcount(r&j)][0])
            {
                dp[l][j][__builtin_popcount(r&j)][0]=rs;
                dp[l][j][__builtin_popcount(r&j)][1]=i;
            }
        }
    }
    while(q>-1)
    {
        res.push_back(q+1);
        q=to[q];
    }
    reverse(res.begin(),res.end());
    cout<<res.size()<<endl;
    for(int&i:res)
    {
        cout<<i<<" ";
    }
    cout<<endl;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t=1;
//    cin>>t;
    while(t--)
    {
        solve();
    }
}

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