제출 #1307202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307202		1an	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	3122 ms	137304 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

struct state {
    int len, end;
};

int main () {
    int n;
    cin >> n;

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

    for (int i = 0; i < n; i++) {
        cin >> k[i];
        prev[i] = i;
    }

    vector<int> l(1 << 20), r(1 << 20);
    for (int i = 0; i < (1 << 20); i++) {
        r[i] = i >> 10;
        l[i] = i & ((1 << 10) - 1);
    }

    vector<vector<int>> bc(1 << 10, vector<int>(1 << 10));
    for (int i = 0; i < (1 << 10); i++)
        for (int j = 0; j < (1 << 10); j++)
            bc[i][j] = __builtin_popcount(i & j);

    int ans = 1, m_idx = 0;
    vector<vector<vector<state>>> dp(1 << 10, vector<vector<state>>(1 << 10, vector<state>(11)));
    for (int i = 0; i < n; i++) {
        int cn = a[i];
        int right = l[cn];
        int left = r[cn];
        int lbs = 1;

        for (int pn = 0; pn < (1 << 10); pn++) {
            int needed = k[i] - bc[left][pn];

            if (needed < 0 || needed > 10)
                continue;

            if (dp[pn][right][needed].len + 1 > lbs) {
                lbs = dp[pn][right][needed].len + 1;
                prev[i] = dp[pn][right][needed].end;
            }
        }

        if (lbs > ans) {
            ans = lbs;
            m_idx = i;
        }

        for (int pn = 0; pn < (1 << 10); pn++) {
            if (lbs > dp[left][pn][bc[right][pn]].len) {
                dp[left][pn][bc[right][pn]] = {lbs, i};
            }
        }
    }

    printf("%d\n", ans);

    stack<int> st;
    while (true) {
        st.push(m_idx);

        if (prev[m_idx] == m_idx)
            break;

        m_idx = prev[m_idx];
    }

    while (!st.empty()) {
        printf("%d ", st.top() + 1);
        st.pop();
    }
}

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