제출 #936036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
936036		atom	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	1 ms	604 KiB

subsequence

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif


const int M = 9;
signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    int n; cin >> n;
    vector <int> a(n + 5), k(n + 5);

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

    vector <pair <int, int>> dp(1 << M), nxt_dp(1 << M);
    vector <int> opt(n + 5, -1), f(n + 5, 1);
    int p = 0, ans = 0;
    
    for (int i = 1; i <= n; ++i) {
        nxt_dp[a[i]].first = max(nxt_dp[a[i]].first, 1);

        for (int msk = 0; msk < (1 << M); ++msk) {
            int cnt = __builtin_popcount(a[i] & msk);
            if (cnt == k[i] && nxt_dp[a[i]].first < dp[msk].first + 1) {
                nxt_dp[a[i]].first = dp[msk].first + 1;
                opt[i] = dp[msk].second;
            }
        }

        for (int msk = 0; msk < (1 << M); ++msk) {
            if (dp[msk].first != nxt_dp[msk].first)
                nxt_dp[msk].second = i;
            f[i] = max(f[i], nxt_dp[msk].first);
        }
        dp = nxt_dp;

        // debug(dp);
    }   

    for (int i = 1; i <= n; ++i) {
        if (ans < f[i]) {
            ans = f[i];
            p = i;
        }
    }

    // debug(opt);
    vector <int> ids;
    while (p != -1) {
        ids.push_back(p);
        p = opt[p];
    }
    reverse(ids.begin(), ids.end());
    cout << ans << "\n";
    for (int x : ids) cout << x << " ";
    cout << "\n"; 
}

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