Submission #1220265

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220265		vanea	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	2552 ms	96008 KiB

subsequence

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

const int B = 10;

int bc[1 << B][1 << B];
array<int, 2> dp[1 << B][1 << B][11];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < (1 << B); i++) {
        for(int j = 0; j < (1 << B); j++) {
            bc[i][j] = __builtin_popcount(i&j);
        }
    }
    vector<int> a(n), k(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> k[i];
    }
    vector<int> prv(n);
    iota(prv.begin(), prv.end(), 0);
    int ans = 1, best_i = 0;
    for(int i = 0; i < n; i++) {
        int l = a[i] >> B;
        int r = a[i] % (1 << B);
        int lbs = 1;
        for(int j = 0; j < (1 << B); j++) {
            if(k[i] - bc[j][l] < 0 || k[i] - bc[j][l] > B) continue;
            array<int, 2> last = dp[j][r][k[i]-bc[j][l]];
            if(last[0] + 1 > lbs) {
                lbs = last[0]+1;
                prv[i] = last[1];
            }
        }
        if(lbs > ans) {
            ans = lbs;
            best_i = i;
        }
        for(int j = 0; j < (1 << B); j++) {
            array<int, 2> &nxt = dp[l][j][bc[r][j]];
            if(lbs > nxt[0]) {
                nxt[0] = lbs;
                nxt[1] = i;
            }
        }
    }
    cout << ans << '\n';
    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(auto it : res) {
        cout << it+1 << ' ';
    }
    return 0;
}

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