제출 #1232599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232599		erering	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2620 ms	175368 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define endl '\n'
//#define int long long
const int N=1e5+5,inf=2e9,MOD=1e9+7;
int a[N],k[N],ans[N],cnt[N],par[N];
pair<int,int> dp[(1<<10)+5][(1<<10)+5][21];
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for(int i=0;i<(1<<10);i++){
        int x=i;
        while(x>0){
            if(x%2)cnt[i]++;
            x/=2;
        }
    }
    int n; cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        par[i]=-1;
    }
    for(int i=0;i<n;i++)cin>>k[i];
    int sol=0;
    for(int i=0;i<n;i++){
        ans[i]=1;
        for(int mask=0;mask<(1<<10);mask++){
            int need=k[i]-cnt[a[i]&mask];
            if(ans[i]<dp[mask][(a[i]>>10)][need].first+1){
                ans[i]=dp[mask][(a[i]>>10)][need].first+1;
                par[i]=dp[mask][(a[i]>>10)][need].second;
            }
        }
        for(int mask=0;mask<(1<<10);mask++){
            int ones=(1<<10)-1;
            dp[a[i]&ones][mask][cnt[mask&(a[i]>>10)]]=max(dp[a[i]&ones][mask][cnt[mask&(a[i]>>10)]],{ans[i],i});
        }
        sol=max(sol,ans[i]);
    }
    vector<int> final;
    for(int i=n-1;i>=0;i--){
        if(ans[i]==sol){
            int x=i;
            while(par[x]!=-1){
                final.pb(x+1);
                x=par[x];
            }
            final.pb(x+1);
            break;
        }
    }
    cout<<sol<<endl;
    for(int i=final.size()-1;i>=0;i--)cout<<final[i]<<' ';
}

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