Submission #474063

#	Time	Username	Problem	Language	Result	Execution time	Memory
474063		ogibogi2004	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	4655 ms	97184 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+6;
const int MAXA=(1<<20);
const int MAXHALF=(1<<10);
int n;
int a[MAXN];
int k[MAXN];
int maxlen[MAXHALF][MAXHALF][22];
int cntbits[MAXHALF][MAXHALF];
int dp[MAXN];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i)cin>>k[i];
    for(int i1=0;i1<MAXHALF;++i1)
    {
        for(int i2=0;i2<MAXHALF;++i2)
        {
            cntbits[i1][i2]=__builtin_popcount(i1&i2);
        }
    }
    int maxdp=0;
    for(int i=1;i<=n;++i)
    {
        dp[i]=1;
        int a1=a[i]/MAXHALF,a2=a[i]%MAXHALF;
        for(int j=0;j<MAXHALF;++j)
        {
            int t=cntbits[a1][j];
            if(t>k[i])continue;
            dp[i]=max(dp[i],maxlen[j][a2][k[i]-t]+1);
        }
        for(int j=0;j<MAXHALF;++j)
        {
            maxlen[a1][j][cntbits[j][a2]]=max(maxlen[a1][j][cntbits[j][a2]],dp[i]);
        }
        maxdp=max(maxdp,dp[i]);
    }
    cout<<maxdp<<'\n';
    vector<int>v;
    for(int i=n;i>=1;i--)
    {
        if(dp[i]==maxdp)
        {
            v.push_back(i);
            break;
        }
    }
    for(int i=v.back()-1;i>0;i--)
    {
        if(dp[i]==dp[v.back()]-1&&__builtin_popcount(a[i]&a[v.back()])==k[v.back()])
        {
            v.push_back(i);
        }
    }
    reverse(v.begin(),v.end());
    for(auto xd:v)
    {
        cout<<xd<<" ";
    }
    cout<<'\n';
return 0;
}

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