제출 #1127949

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127949		FucKanh	Longest beautiful sequence (IZhO17_subsequence)	C++20	40 / 100	6097 ms	96016 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 = 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;
            if (len < dp[state][r][k[i] - bc[l][state]].first + 1) {
                len = dp[state][r][k[i] - bc[l][state]].first + 1;
                trace[i] = dp[state][r][k[i] - bc[l][state]].second;
            }
        }

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

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