Submission #1098593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098593		damwuan	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4622 ms	177028 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
#define int ll
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define for1(i,x,n) for(int i=x;i<=n;i++)
#define for2(i,x,n) for(int i=x;i>=n;i--)

typedef long long ll;
typedef pair<int,int> pii;

const ll maxn = 1e6 + 69;
const ll mod  = 1e9 + 7;
const ll inf  = 1e18;

int n,a[maxn],k[maxn],dp[maxn],f[(1<<10)][1<<10][21],trace[maxn];

void sol()
{
    cin >> n;
    for1(i,1,n) cin >> a[i];
    for1(i,1,n) cin >> k[i];
    for1(i,1,n)
    {
        dp[i]=1;
        int fl=((1<<10)-1)&a[i],fr=a[i]>>10;
        for1(mask,0,(1<<10)-1)
        {
//            cerr<< mask<<'\n';
            if (k[i]-__builtin_popcount(fl&mask)<0) continue;
            int j=f[mask][fr][k[i]-__builtin_popcount(fl&mask)];
            if (j!=0 && dp[j]+1>dp[i])
            {
                dp[i]=dp[j]+1;
                trace[i]=j;
            }
        }
        for1(mask,0,(1<<10)-1)
        {
//            cerr<< mask<<'\n';
            int j=f[fl][mask][__builtin_popcount(fr&mask)];
            if (j==0 || dp[i]>dp[j])
            {
                f[fl][mask][__builtin_popcount(fr&mask)]=i;
            }
        }
    }
    int mx=0;
    for1(i,1,n)
    {
        if (dp[mx]<dp[i]) mx=i;
    }
//    return;
    cout << dp[mx]<<'\n';
    vector<int> res;
    while (mx)
    {
        res.pb(mx);
        mx=trace[mx];
    }
    reverse(all(res));
    for(int v: res) cout << v<<' ';

}


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;//cin >> t;
    while (t--) sol();
}
/*
5
5 3 5 3 5
10 1 20 1 20
*/

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