Submission #1177544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177544		AlgorithmWarrior	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	1800 ms	55396 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

int const MAX=1e5+5;
int len[MAX],bef[MAX];
int dp[1<<10][1<<10][13];
int n;
int v[MAX];
int comun[MAX];

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i];
    for(i=1;i<=n;++i)
        cin>>comun[i];
}

void get_dp(){
    int i;
    for(i=1;i<=n;++i){
        int nr1=(v[i]>>10);
        int nr2=(v[i]^(nr1<<10));
        int nr;
        int best=0;
        for(nr=0;nr<(1<<10);++nr){
            int nrb=__builtin_popcount(nr&nr1);
            if(nrb<=comun[i] && comun[i]-nrb<=10){
                int cand=dp[nr][nr2][comun[i]-nrb];
                if(len[best]<len[cand])
                    best=cand;
            }
        }
        len[i]=len[best]+1;
        bef[i]=best;
        for(nr=0;nr<(1<<10);++nr){
            int nrb=__builtin_popcount(nr&nr2);
            if(len[i]>len[dp[nr1][nr][nrb]])
                dp[nr1][nr][nrb]=i;
        }
    }
}

void write(){
    int best=0;
    int i;
    for(i=1;i<=n;++i)
        if(len[i]>len[best])
            best=i;
    cout<<len[best]<<'\n';
    vector<int>ans;
    while(best){
        ans.push_back(best);
        best=bef[best];
    }
    reverse(ans.begin(),ans.end());
    for(auto ind : ans)
        cout<<ind<<' ';
}

int main()
{
    read();
    get_dp();
    write();
    return 0;
}

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