Submission #474057

#	Time	Username	Problem	Language	Result	Execution time	Memory
474057		ogibogi2004	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	6103 ms	186456 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];
pair<int,int> maxlen[MAXHALF][MAXHALF][22];
int cntbits[MAXHALF][MAXHALF];
pair<int,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);
        }
    }
    pair<int,int> maxdp;
    maxdp={0,0};
    for(int i=1;i<=n;++i)
    {
        dp[i]={1,0};
        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].first+1,maxlen[j][a2][k[i]-t].second});
        }
        for(int j=0;j<MAXHALF;++j)
        {
            maxlen[a1][j][cntbits[j][a2]]=max(maxlen[a1][j][cntbits[j][a2]],{dp[i].first,i});
        }
        maxdp=max(maxdp,{dp[i].first,i});
    }
    cout<<maxdp.first<<'\n';
    vector<int>v;
    v.push_back(maxdp.second);
    while(dp[v.back()].second!=0)
    {
        v.push_back(dp[v.back()].second);
    }
    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: 0 / 60