Submission #950510

#	Time	Username	Problem	Language	Result	Execution time	Memory
950510		BF001	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2754 ms	97360 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define fi first
#define se second
#define M 10

typedef pair<int, int> ii;

int n, a[N], k[N], cbit[(1 << M) + 1][(1 << M) + 1], par[N];
ii dp[(1 << M) + 1][(1 << M) + 1][M + 1];

int get(int msk){
    int rt = 0;
    for (int pos = 0; pos < M; pos++) rt += (msk >> pos) & 1;
    return rt;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
        
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int j = 1; j <= n; j++) cin >> k[j];

    for (int msk = 0; msk < 1 << M; msk++){
        for (int msk2 = 0; msk2 < 1 << M; msk2++){
            int cur = msk & msk2;
            cbit[msk][msk2] = get(cur);
        }
    }

    ii res = {0, 0};

    for (int i = 1; i <= n; i++){
        ii best = {0, 0};
        int l = a[i] >> M;
        int r = a[i] % (1 << M);
        for (int msk = 0; msk < 1 << M; msk++){
            int cal = k[i] - cbit[l][msk];
            if  (cal < 0 || cal > M) continue;
            if (dp[msk][r][cal].fi > best.fi){
                best = dp[msk][r][cal];
            }
        }
        best.fi++;
        par[i] = best.se;
        best.se = i;
        for (int msk = 0; msk < 1 << M; msk++){
            int cur = cbit[msk][r];
            if (cur < 0 || cur > M) continue;
            if (dp[l][msk][cur].fi < best.fi){
                dp[l][msk][cur] = best;
            }
        }
        res = max(res, best);
    }


    vector<int> ans;
    int pos = res.se;
    while (pos){
        ans.push_back(pos);
        pos = par[pos];
    }


    cout << ans.size() << "\n";
    for (int i = (int) ans.size() - 1; i >= 0; i--) cout << ans[i] << " " ;

    return 0;
}     

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