Submission #1127947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127947		FucKanh	Longest beautiful sequence (IZhO17_subsequence)	C++20	0 / 100	69 ms	94784 KiB

subsequence

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>

using namespace std;

const int half = 10;
const int maxn = 1e5 + 2;

int n;
int a[maxn], k[maxn];
int l[maxn], r[maxn];
int trace[maxn],arr[maxn];
int bc[1<<half][1<<half];
pii dp[1<<half][1<<half][half + 1];

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

    memset(dp,-1,sizeof(dp));

    for (int i = 1; i <= n; i++) {
        r[i] = a[i] & ((1<<half)-1);
        l[i] = (a[i] ^ r[i])>>half;
    }

    for (int i = 0; i < (1<<half); i++) {
        for (int j = 0; j < (1<<half); j++) {
            bc[i][j] = __builtin_popcount(i & j);
        }
    }
    int ans = 0, pos = 0;
    for (int i = 1; i <= n; i++) {
        int len = 1;
        for (int state = 0; state < (1<<half); ++state) {
            if (bc[l[i]][state] > k[i] || k[i] - bc[l[i]][state] > 10) continue;
            if (len < dp[state][r[i]][k[i] - bc[l[i]][state]].first + 1) {
                len = dp[state][r[i]][k[i] - bc[l[i]][state]].first + 1;
                trace[i] = dp[state][r[i]][k[i] - bc[l[i]][state]].second;
            }
        }

        if (ans < len) {
            ans = len;
            pos = i;
        }

        for (int state = 0; state < (1<<half); ++state) {
            if (dp[l[i]][state][bc[state][r[i]]].first < len) {
                dp[l[i]][state][bc[state][r[i]]].first = len;
                dp[l[i]][state][bc[state][r[i]]].second = i;
            }
        }
    }
    cout << ans << '\n';
    int cnt = 1;
    while (trace[pos]) {
        arr[++cnt] = pos;
        pos = trace[pos];
    }
    arr[++cnt] = pos;
    for (int i = cnt ; i >= 1; i--) {
        cout << arr[i] << " ";
    }
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    solve();
    return 0;
}

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