제출 #1279055

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279055		patpro28	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	2708 ms	100504 KiB

subsequence

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

static inline int pc10(unsigned x) { return __builtin_popcount(x); }

struct Node {
    int val; // best dp
    int idx; // argmax index (1-based)
    Node(int v = INT_MIN/4, int i = -1): val(v), idx(i) {}
    inline void upd(int v, int i) {
        if (v > val) { val = v; idx = i; }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; 
    if (!(cin >> n)) return 0;
    const int W = 10;
    const int LIM = 1 << W; // 1024

    vector<unsigned int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<int> k(n);
    for (int i = 0; i < n; ++i) cin >> k[i];

    // F[L][R]: best (dp, idx) for exact pair (L,R)
    static Node F[1<<10][1<<10];
    // M[AR][cr][L]: best aggregated over all R such that popcount(R & AR) = cr
    // Dimensions: 1024 * 11 * 1024 ~ 11M entries
    static Node M[1<<10][11][1<<10];

    vector<int> dp(n, 1), prv(n, -1);

    for (int j = 0; j < n; ++j) {
        unsigned A = a[j];
        int AL = (int)(A >> 10);
        int AR = (int)(A & (LIM - 1));
        int need = k[j];

        // Query
        int bestVal = 0; // if none -> dp = 1
        int bestIdx = -1;
        for (int L = 0; L < LIM; ++L) {
            int cl = pc10((unsigned)L & (unsigned)AL);
            int cr = need - cl;
            if (cr < 0 || cr > 10) continue;
            const Node &cand = M[AR][cr][L];
            if (cand.val > bestVal) { // since dp = 1 + cand.val
                bestVal = cand.val;
                bestIdx  = cand.idx;
            }
        }
        if (bestIdx != -1) {
            dp[j] = bestVal + 1;
            prv[j] = bestIdx;
        } else {
            dp[j] = 1;
            prv[j] = -1;
        }

        // Update with current element
        int L0 = (int)(A >> 10);
        int R0 = (int)(A & (LIM - 1));
        // Update F
        if (dp[j] > F[L0][R0].val) {
            F[L0][R0].val = dp[j];
            F[L0][R0].idx = j + 1; // store 1-based
        }
        // Push into all AR buckets
        for (int ARx = 0; ARx < LIM; ++ARx) {
            int cr = pc10((unsigned)R0 & (unsigned)ARx);
            M[ARx][cr][L0].upd(dp[j], j + 1);
        }
    }

    // Find answer and reconstruct
    int bestEnd = 0;
    for (int i = 1; i < n; ++i) if (dp[i] > dp[bestEnd]) bestEnd = i;

    cout << dp[bestEnd] << "\n";
    vector<int> seq;
    for (int x = bestEnd; x != -1; x = (prv[x] == -1 ? -1 : prv[x] - 1)) {
        seq.push_back(x + 1);
        if (prv[x] == -1) break;
    }
    reverse(seq.begin(), seq.end());
    for (int i = 0; i < (int)seq.size(); ++i) {
        if (i) cout << ' ';
        cout << seq[i];
    }
    cout << "\n";
    return 0;
}

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