제출 #842727

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
842727		zwezdinv	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3367 ms	48212 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()

const int Q = 1 << 10;
const int N = 1e5;

int n, a[N], k[N];
int dp[N], par[N];
int mx[Q][Q][11];

int qmx(int i, int j) {
    if (i == -1) return j;
    if (j == -1) return i;
    return dp[i] > dp[j] ? i : j;
}

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

    cin >> 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) {
        dp[i] = 1;
        par[i] = -1;
    }
    for (int i = 0; i < Q; ++i) {
        for (int j = 0; j < Q; ++j) {
            for (int c = 0; c <= 10; ++c) {
                mx[i][j][c] = -1;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        int x = a[i] / Q, y = a[i] % Q;
        for (int j = 0; j < Q; ++j) {
            int q = k[i] - __builtin_popcount(x & j);
            if (q < 0 || q > 10) continue;
            par[i] = qmx(par[i], mx[j][y][q]);
        }
        if (par[i] != -1) dp[i] = dp[par[i]] + 1;
        for (int j = 0; j < Q; ++j) {
            int q = __builtin_popcount(y & j);
            mx[x][j][q] = qmx(mx[x][j][q], i);
        }
    }
    vector<int> ans;
    int u = max_element(dp, dp + n) - dp;
    while (u != -1) {
        ans.push_back(u);
        u = par[u];
    }
    reverse(all(ans));
    cout << ans.size() << '\n';
    for (auto i : ans) cout << i + 1 << ' ';
}

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