제출 #1068878

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1068878		DucNguyen2007	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3043 ms	105456 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=1e5+5;
const ll inf=2e18;
int n,a[maxN+1],k,dp[maxN+1],f[(1LL<<10)+1][(1LL<<10)+1][25],trace[maxN+1];
vector<int> v;
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        dp[i]=1;
    }
    memset(f,0,sizeof(f));
    memset(trace,-1,sizeof(trace));
    for(int i=1;i<=n;i++)
    {
        cin>>k;
        int tmp1=(a[i]>>10);
        int tmp2=a[i]-(tmp1<<10);
        for(int mask=0;mask<(1LL<<10);mask++)
        {
            int x=(mask&tmp2);
            x=__builtin_popcount(x);
            if(x>k)
            {
                continue;
            }
            int tmp=f[tmp1][mask][k-x];
            if(dp[i]<dp[tmp]+1)
            {
                dp[i]=dp[tmp]+1;
                trace[i]=tmp;
            }
        }
        for(int mask=0;mask<(1LL<<10);mask++)
        {
            int x=(mask&tmp1);
            x=__builtin_popcount(x);
            if(dp[f[mask][tmp2][x]]<dp[i])
            {
                f[mask][tmp2][x]=i;
            }
        }
        //cout<<i<<" "<<tmp1<<" "<<tmp2<<" "<<dp[i]<<'\n';
    }
    int mx=0,pos;
    for(int i=1;i<=n;i++)
    {
        if(mx<dp[i])
        {
            mx=dp[i];
            pos=i;
        }
    }
    while(pos!=-1)
    {
        v.push_back(pos);
        pos=trace[pos];
    }
    reverse(v.begin(),v.end());
    cout<<mx<<'\n';
    for(auto i:v)
    {
        cout<<i<<" ";
    }
}
/*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