제출 #1091972

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1091972		ULTRABIG7	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	4 ms	5980 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;

#define ff first
#define ss second
#define pb push_back
#define all(x) begin(x),end(x)

#define FOR(i,a,b) for(int i = (a);i<(b);i++)
#define F0R(i,a) FOR(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for(auto& a:x)
#define sz(x) (int)size(x)
#define vi vector<int>
const int MOD = 1e9+7;
const db PI = acos((db)-1);

const int N = 1e5;
const int B = 10;
int bc[1<<B][1<<B];

struct state{
    int len;
    int end;
} dp[1<<B][1<<B][B+1];



int main(){
    cin.tie(0)->sync_with_stdio(0);

    FOR(i,0,1<<B){
        FOR(j,0,1<<B){
            bc[i][j] = __builtin_popcount(i&j);
        }
    }

    int n; cin>>n;

    vi A(n), K(n);
    int mx = -1;
    FOR(i,0,n){
        cin>>A[i];
        mx = max(mx,A[i]);
    }

    FOR(i,0,n){
        cin>>K[i];
    }

    int ans = 1;
    int best_i = 0;
    vi ant(n);

    iota(all(ant),0);

    FOR(i,0,n){
        int l = A[i]>>B;
        int r = A[i] % (1<<B);
        int lbs = 1;

        FOR(j,0,1<<B){



            int needed = K[i] - bc[j][l];
            if(needed<0 || needed>B) continue;

            if(dp[j][r][needed].len + 1 > lbs){
                lbs = dp[j][r][needed].len + 1;
                ant[i] = dp[l][r][needed].end;
            }
        }

        if(lbs>ans){
            ans = lbs;
            best_i = i;
        }


        FOR(j,0,1<<B){
            state& new_state = dp[l][j][bc[r][j]];
            if(lbs>new_state.len){
                new_state.len = lbs;
                new_state.end = i;
            }
        }
    }


    cout<<ans<<"\n";

    vi res;
    while(ant[best_i]!=best_i){
        res.pb(best_i);
        best_i = ant[best_i];
    }

    res.pb(best_i);

    reverse(all(res));

    each(x,res){
        cout<<x+1<<" ";
    }
    
    return 0;
}

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