Submission #1127721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127721		tudor_costin	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	4794 ms	175456 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;
const int Nmax=1e5+5,Kmax=21;
int a[Nmax],k[Nmax];
int dp[(1<<10)+5][(1<<10)+5][Kmax];
int ind[(1<<10)+5][(1<<10)+5][Kmax];
int prv[Nmax],len[Nmax];
int left_mask(int x)
{
    return (x>>10);
}
int right_mask(int x)
{
    return (x&((1<<10)-1));
}
void reconst(int x)
{
    if(x==-1) return;
    reconst(prv[x]);
    cout<<x<<' ';
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>k[i];
    }
    int best=0;
    for(int i=1;i<=n;i++)
    {
        int l=left_mask(a[i]);
        int r=right_mask(a[i]);
        len[i]=1;
        prv[i]=-1;
        for(int lmask=0;lmask<(1<<10);lmask++)
        {
            int bits=__builtin_popcount(lmask&l);
            if(k[i]>=bits && k[i]-bits<=__builtin_popcount(r))
            {
                int curlen=dp[lmask][r][k[i]-bits]+1;
                if(curlen>len[i])
                {
                    len[i]=curlen;
                    prv[i]=ind[lmask][r][k[i]-bits];
                }
            }
        }
        for(int rmask=0;rmask<(1<<10);rmask++)
        {
            int bits=__builtin_popcount(rmask&r);
            if(len[i]>dp[l][rmask][bits])
            {
                dp[l][rmask][bits]=len[i];
                ind[l][rmask][bits]=i;
            }
        }
        if(len[i]>len[best]) best=i;
    }
    cout<<len[best]<<'\n';
    reconst(best);
    return 0;
}

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