Submission #700087

#	Time	Username	Problem	Language	Result	Execution time	Memory
700087		fdnfksd	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	4900 ms	51388 KiB

subsequence

#include<bits/stdc++.h>
#define TASKNAME "bieudo"
#define pb push_back
#define pli pair<int,int>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=1e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
int f[1024][1024][11]={0};
ll trace[maxN];
ll n,a[maxN],k[maxN];
ll pre[maxN],suf[maxN];
ll dp[maxN];
void solve()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) cin >> k[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<10;j++)
        {
            ll x=a[i]>>j&1;
            pre[i]+=(x<<j);
        }
        for(int j=10;j<20;j++)
        {
            ll x=a[i]>>j&1;
            suf[i]+=(x<<(j-10));
        }
    }
    dp[0]=-inf;
    ll ans=0;
    ll vt=0;
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        trace[i]=0;
        for(int j=0;j<(1<<10);j++)
        {
            ll chung=__builtin_popcount(pre[i]&j);
            ll can=k[i]-chung;
            if(can>10||can<0) continue;
            dp[i]=max(dp[i],dp[f[j][suf[i]][can]]+1);
            if(dp[i]==dp[f[j][suf[i]][can]]+1)
            {
                trace[i]=f[j][suf[i]][can];
            }
        }
        for(int j=0;j<(1<<10);j++)
        {
            ll c=__builtin_popcount(suf[i]&j);
            if(dp[f[pre[i]][j][c]]<dp[i])
            {
                f[pre[i]][j][c]=i;
            }
        }
        if(dp[i]>ans)
        {
            ans=dp[i];
            vt=i;
        }
        //cout << dp[i]<<' ';
    }
    //cout << trace[3]<<'\n';
    cout << ans << '\n';
    vector<ll> t;
    while(vt!=0)
    {
        t.pb(vt);
        vt=trace[vt];
    }
    reverse(t.begin(),t.end());
    for(auto zz:t) cout <<zz<<' ';
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

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