Submission #1127960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127960		FucKanh	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	6092 ms	130072 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 trace[maxn],arr[maxn];
int bc[(1<<half)+5][(1<<half)+5];
pii dp[(1<<half)+5][(1<<half)+5][half + 5];

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 state = 0; state < (1<<half); ++state) {
        for (int state2 = 0; state2 < (1<<half); ++state2) {
            for (int i = 0; i <= 10; i++) {
                if (dp[state][state2][i] != make_pair(-1,-1)) assert(0);
            }
        }
    }

    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;
        int r = a[i] & ((1<<half)-1);
        int l = a[i] >> half;
        for (int state = 0; state < (1<<half); ++state) {
            if (bc[l][state] > k[i] || k[i] - bc[l][state] > 10) continue;
            pii &tmp = dp[state][r][k[i] - bc[l][state]];
            if (len < tmp.first + 1) {
                len = tmp.first + 1;
                trace[i] = tmp.second;
            }
        }

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

        for (int state = 0; state < (1<<half); ++state) {
            pii &tmp = dp[l][state][bc[state][r]];
            if (tmp.first < len) {
                tmp.first = len;
                tmp.second = i;
            }
        }
    }
    cout << ans << '\n';
    int cnt = 0;
    while (trace[pos]) {
        arr[++cnt] = pos;
        pos = trace[pos];
        assert(pos != -1 && cnt <= n);
    }
    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: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 60