Submission #1101664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101664		orcslop	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	6042 ms	2472 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")

int main() {
    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]; }

    vector<int> dp(n, 1);
    int ans = 1;
    // best_i: most optimal index to end on
    int best_i = 0;
    // prv[i] = optimal index to include right before i
    vector<int> prv(n);
    // intially, prv[i] = i
    iota(prv.begin(), prv.end(), 0);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            // bc[a[j]][a[i]] == k[i]
            if (__builtin_popcount(a[j] & a[i]) == k[i]) {
                if (dp[j] + 1 > dp[i]) {
                    prv[i] = j;
                    dp[i] = dp[j] + 1;
                }
            }
        }
        if (dp[i] > ans) {
            ans = dp[i];
            best_i = 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: 0 / 17
• Subtask 4: 0 / 60