제출 #1307132

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

subsequence

#include <bits/stdc++.h>

using namespace std;

struct state {
    int len = -1, end = -1;

    state(int l = -1, int e = -1) : len(l), end(e) {}
};

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];

    for (int i = 0; i < n; i++)
        prev[i] = i;

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

    vector<state> dp1(1 << 8);
    dp1[a[0]] = {1, 0};

    int best_m = 1, m_idx = 0;

    for (int i = 1; i < n; i++) {
        if (dp1[a[i]].len == -1)
            dp1[a[i]] = {1, i};

        for (int mask = 0; mask < (1 << 8); mask++) {
            if (1 + dp1[mask].len > dp1[a[i]].len && bc[mask][a[i]] == k[i]) {
                dp1[a[i]] = {1 + dp1[mask].len, i};
                prev[i] = dp1[mask].end;
            }
        }

        if (dp1[a[i]].len > best_m) {
            best_m = dp1[a[i]].len;
            m_idx = i;
        }
    }

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

    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: 0 / 7
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60