Submission #1303899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303899		ChottuF	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	3086 ms	91960 KiB

subsequence

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

pair<int,int> best[1<<10][1<<10][11];
//xhigh, mask, resulting pop
//stores {max length ending here and the index of the guy this was donated from}
const int MAXN = 1e5+5;
int prv[MAXN];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 0; i<MAXN; i++){
        prv[i] = -1;
    }
    
    int n;
    cin >> n;
    int arr[n];
    int k[n];
    for (int i = 0; i<n; i++){
        cin >> arr[i];
    }
    for (int i = 0; i<n; i++){
        cin >> k[i];
    }
    int allmx = 0;
    int st = -1;
    for (int i = 0; i<n; i++){
        int x = arr[i];
        
        int xhigh = x >> 10;
        int xlow = x & 1023;
        
        int mx = 0;
        int bf = -1;
        //first query
        
        for (int h = 0; h<1024; h++){
            int hpop = __builtin_popcount(xhigh & h);
            int lft = k[i] - hpop;
            if (lft < 0 || lft > 10) continue;
            auto [cr,idx] = best[h][xlow][lft];
            if (cr != 0){
                //actually exists
                if (cr > mx){
                    mx = cr;
                    bf = idx;
                }
            }
        }
        mx++;
        if (mx > allmx){
            allmx = mx;
            st = i;
        }
        prv[i] = bf;
        //update
        for (int mask = 0; mask<1024; mask++){
            int plow = __builtin_popcount(xlow & mask);
            pair<int,int> res = {mx,i};
            best[xhigh][mask][plow] = max(best[xhigh][mask][plow], res);
        }
    }
    cout << allmx << '\n';
    vector<int> ss;
    ss.push_back(st);
    while (prv[st] != -1){
        ss.push_back(prv[st]);
        st = prv[st];
    }
    reverse(ss.begin(),ss.end());
    for (auto u : ss){
        cout << u+1 << " ";
    }
    return 0;
}

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