Submission #1257328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257328		proofy	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	1148 ms	53540 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long


const int M = 1 << 10;

int low(int x) {
    return (x & (M - 1));
}

int high(int x) {
    return x >> 10;
}

int pop[M];

vector<int> G[M][11];

void precompute() {
    for (int mask = 1; mask < M; mask++)
        pop[mask] = 1 + pop[mask - (mask & -mask)];

    for (int mask = 0; mask < M; mask++) {
        for (int x = 0; x < M; x++) G[mask][pop[x & mask]].push_back(x);
    }
}

int B[M][M][11]; 
// B[x][y][r] = longest subsequence ending at k such that low(k) = x,
// and popcount(high(k) & y) = r

const int N = 1e5 + 9;
int D[N], P[N], a[N], k[N], n;

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

    precompute();

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

    int ans = 0;

    for (int i = 1; i <= n; i++) {
        int x = a[i];

        D[i] = 1;

        for (int r = 0; r <= k[i]; r++) {
            int t = k[i] - r;
            if (t <= 10 && r <= 10)
                for (int y : G[low(x)][t]) 
                    if (1 + D[B[y][high(x)][r]] > D[i]) {
                        D[i] = D[B[y][high(x)][r]] + 1;
                        P[i] = B[y][high(x)][r];
                    }
        }
        ans = max(ans, D[i]);

        for (int r = 0; r <= 10; r++)
            for (int y : G[high(x)][r]) 
                if (D[B[low(x)][y][r]] < D[i]) 
                    B[low(x)][y][r] = i;
    }

    cout << ans << "\n";
    function<void(int)> print = [&](int i) {
        if (i == 0) return;
        print(P[i]);
        cout << i << " ";
    };
    for (int i = 1; i <= n; i++) if (D[i] == ans)
        return print(i), 0;
}

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