Submission #714539

#	Time	Username	Problem	Language	Result	Execution time	Memory
714539		egregious	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2892 ms	96960 KiB

subsequence

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using pii = pair<int, int>;
const int N = 1e5;
const int B = 10;
int bc[1 << B][1 << B]; // bc[i][j] = bit_count(i & j)
pii dp[1 << B][1 << B][B + 1];
// define l(x) = 10 leftmost bits of x, 
// and r(x) = 10 rightmost bits of x
// dp[i][j][k].f:
// longest subsequence that ends in x, where x satisfies:
// 1) l(x) = i
// 2) bit_count(r(x) & j) = k
// dp[i][j][k].s:
// index of the most optimal x

int main() {
    // preprocess: 
    for (int i = 0; i < (1 << B); i++) {
        for (int j = 0; j < (1 << B); j++) {
            bc[i][j] = __builtin_popcount(i & j);
        }
    }

	int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> k(n);
    for (int i = 0; i < n; i++) cin >> k[i];
    int ans = 1, best_i = 0; // best_i: best index to end subsequence at
    vector<int> prv(n); // prv[i]: best index to include before i
    iota(prv.begin(), prv.end(), 0); // prv[i] = i

    for (int i = 0; i < n; i++) {
        int l = a[i] >> 10, r = a[i] % (1 << 10); // l(a[i]), r(a[i])
        int lbs = 1; // length of lbs

        // enumerate all possibilities for l(prev_num)
        for (int j = 0; j < (1 << B); j++) {
            int needed = k[i] - bc[j][l];
            if (needed < 0 || needed > 10) continue;
            if (dp[j][r][needed].f + 1 > lbs) {
                lbs = dp[j][r][needed].f + 1;
                prv[i] = dp[j][r][needed].s;
            }
        }

        if (lbs > ans) {
            ans = lbs;
            best_i = i;
        }

        // update all answers a[i] affects
        for (int j = 0; j < (1 << B); j++) {
            pii& new_state = dp[l][j][bc[r][j]];
            if (lbs > new_state.f) {
                new_state.f = lbs;
                new_state.s = i;
            }
        }
    }
    cout << ans << endl;
    vector<int> res;
    while (prv[best_i] != best_i) {
        res.push_back(best_i);
        best_i = prv[best_i];
    }
    res.push_back(best_i);
    reverse(res.begin(), res.end());
    for (int x : res) cout << x + 1 << " ";
}

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