Submission #136864

#	Time	Username	Problem	Language	Result	Execution time	Memory
136864		darkkcyan	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	426 ms	262148 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
using namespace std::placeholders;

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rand(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64

#define maxn 101010
#define maxk 25
#define halfk 10
int n;
int a[maxn], k[maxn];
int trace[maxn];

pair<int, int> dp[1 << halfk][1 << halfk][halfk + 1];

template<class T>
inline T maximize(T& x, T y) {
    if (x < y) x = y;
    return x;
}
int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> k[i];

    rep(i, (1 << halfk))
    rep(f, (1 << halfk))
    rep(diff, halfk) 
        dp[i][f][diff] = {0, -1};

    pair<int, int> ans(0, -1);
    rep(i, n) {
        int first_half = a[i] & ((1 << 10) - 1);
        int second_half = a[i] >> 10;
        pair<int, int> cur_ans(0, -1);
        rep(prev_first_half, (1 << 10)) {
            int first_half_diff = __builtin_popcount(prev_first_half & first_half);
            if (first_half_diff > k[i]) continue;
            int second_half_diff = k[i] - first_half_diff;
            cur_ans = max(cur_ans, dp[prev_first_half][second_half][second_half_diff]);
        }

        trace[i] = cur_ans.yy;
        ++cur_ans.xx;
        cur_ans.yy = i;
        ans = max(ans, cur_ans);

        rep(next_second_half, (1 << 10)) {
            int second_half_diff = __builtin_popcount(next_second_half & second_half);
            maximize(dp[first_half][next_second_half][second_half_diff], cur_ans);
        }
    }

    cout << ans.xx << '\n';
    // clog << ans.yy << endl;
    vector<int> rev_i(1, ans.yy);
    while (trace[rev_i.back()] != -1) {
        rev_i.push_back(trace[rev_i.back()]);
        // clog << rev_i.back() << endl;
    }
    for (int i = ans.xx; i--; ) cout << rev_i[i] + 1 << ' ';

    return 0;
}

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