Submission #765536

#	Time	Username	Problem	Language	Result	Execution time	Memory
765536		Ahmed57	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4292 ms	93028 KiB

subsequence

#include<bits/stdc++.h>

using namespace std;
pair<int,int> dp[(1<<10)][(1<<10)][11];
int a[100001],b[100001],telp[100001];
int main(){
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++)cin>>a[i];
    for(int i = 1;i<=n;i++)cin>>b[i];
    int ans = 0 , strt = 0;
    for(int i = 1;i<=n;i++){
        int fi = a[i]>>10 , se = a[i]&((1<<10)-1);
        int an = 1;
        for(int mask = 0;mask<(1<<10);mask++){
            int ne = __builtin_popcount(mask&fi);
            int neeeed = b[i]-ne;
            if(neeeed>=0&&neeeed<=10){
                if(an<dp[mask][se][neeeed].first+1){
                    an = dp[mask][se][neeeed].first+1;
                    telp[i] = dp[mask][se][neeeed].second;
                }
            }
        }
        for(int mask = 0;mask<(1<<10);mask++){
            int ne = __builtin_popcount(mask&se);
            if(dp[fi][mask][ne].first<an){
                dp[fi][mask][ne].first = an;
                dp[fi][mask][ne].second = i;
            }
        }
        if(ans<an){
            ans = an;
            strt = i;
        }
    }
    vector<int> tmp;
    while(strt>0){
        tmp.push_back(strt);
        strt = telp[strt];
    }
    reverse(tmp.begin(),tmp.end());
    cout<<ans<<endl;
    for(auto i:tmp){
        cout<<i<<" ";
    }
}

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