Submission #1007282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007282		SulA	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2833 ms	60716 KiB

subsequence

#include <bits/stdc++.h>
#pragma GCC target("popcnt")
using namespace std;

int b[21][1<<10][1<<10], bindex[21][1<<10][1<<10];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);


    int n; cin >> n;
    int a[n], k[n];
    for (int& x : a) cin >> x;
    for (int& x : k) cin >> x;
    int bitcnt[1<<20];
    for (int i = 0; i < 1 << 20; i++) {
        bitcnt[i] = __builtin_popcount(i);
    }
    int dp[n];
    int pre[n];
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        pre[i] = i;
        int U = a[i] >> 10, L = a[i] & 1023;
         for (int x = 0; x < 1 << 10; x++) {
             if (k[i] - bitcnt[x & L] < 0) continue;
             if (b[k[i] - bitcnt[x & L]][U][x] + 1 > dp[i]) {
                 dp[i] = b[k[i] - bitcnt[x & L]][U][x] + 1;
                 pre[i] = bindex[k[i] - bitcnt[x & L]][U][x];
             }
         }
         for (int x = 0; x < 1 << 10; x++) {
             if (dp[i] > b[bitcnt[U & x]][x][L]) {
                 b[bitcnt[U & x]][x][L] = dp[i];
                 bindex[bitcnt[U & x]][x][L] = i;
             }
         }
    }

    int final = max_element(dp, dp+n) - dp;
    vector<int> subs;
    while (final != pre[final]) {
        subs.push_back(final);
        final = pre[final];
    }
    subs.push_back(final);
    reverse(subs.begin(), subs.end());
    cout << subs.size() << "\n";
    for (int x : subs) cout << x+1 << " ";
}

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