제출 #1345387

#제출 시각아이디문제언어결과실행 시간메모리
1345387domiLongest beautiful sequence (IZhO17_subsequence)C++20
100 / 100
1159 ms129464 KiB
#include <bits/stdc++.h>

// #define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 1e5;
const int B = 10;
const int P = (1LL << B);

using namespace std;

int prec[P + 5][P + 5], dp[P + 5][P + 5][B + 5], unde[P + 5][P + 5][B + 5];
int a[NMAX + 5], k[NMAX + 5], bck[NMAX + 5], n;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;

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

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

    for (int i = 0; i < (1LL << B); ++i) {
        for (int j = 0; j < (1LL << B); ++j)
            prec[i][j] = __builtin_popcountll(i & j);
    }

    int ans = INT_MIN, start_idx = -1;
    for (int i = 1; i <= n; ++i) {
        int l = (a[i] >> B);
        int r = a[i] % (1LL << B);
        int best = 1;

        for (int l_prv = 0; l_prv < (1LL << B); ++l_prv) {
            int need = k[i] - prec[l_prv][l];

            if (need < 0 || need > B) continue;

            if (dp[l_prv][r][need] + 1 > best) {
                best = dp[l_prv][r][need] + 1;
                bck[i] = unde[l_prv][r][need];
            }
        }

        for (int j = 0; j < (1LL << B); ++j) {
            if (best > dp[l][j][prec[r][j]]) {
                dp[l][j][prec[r][j]] = best;
                unde[l][j][prec[r][j]] = i;
            }
        }

        if (best > ans) {
            ans = best;
            start_idx = i;
        }
    }

    vector<int> sol;
    while (start_idx != 0) {
        sol.push_back(start_idx);
        start_idx = bck[start_idx];
    }

    reverse(all(sol));
    cout << sz(sol) << '\n';
    for (auto &it : sol)
        cout << it << " \n"[it == sol.back()];
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...