Submission #1254975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254975		Thunnus	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	6096 ms	182372 KiB

subsequence

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
using i64 = long long;
//#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define fi first
#define se second
#define pii pair<int, int>
#define sz(x) (int)(x).size()

const int LG = 10;

inline void solve(){
    int n;
    cin >> n;
    vi a(n), k(n);
    for(int &i : a){
        cin >> i;
    }
    for(int &i : k){
        cin >> i;
    }

    vector<vvi> dp(1 << LG, vvi(1 << LG, vi(LG + 1))), par(1 << LG, vvi(1 << LG, vi(LG + 1, -1)));
    vi from(n, -1);
    int ans = INT32_MIN, lst = -1;
    for(int i = 0; i < n; i++){
        int le = a[i] >> LG, ri = a[i] % (1 << LG), lbs = 1;
        for(int mask = 0; mask < (1 << LG); mask++){
            int new_mask = mask & ri;
            int bc = __builtin_popcountll(new_mask);
            if(bc > k[i] || k[i] - bc > LG) continue;
            if(dp[le][mask][k[i] - bc] + 1 > lbs){
                from[i] = par[le][mask][k[i] - bc];
            }
            lbs = max(lbs, dp[le][mask][k[i] - bc] + 1);
        }
        for(int mask = 0; mask < (1 << LG); mask++){
            int new_mask = mask & le;
            int bc = __builtin_popcountll(new_mask);
            if(lbs > dp[mask][ri][bc]){
                par[mask][ri][bc] = i;
            }
            dp[mask][ri][bc] = max(dp[mask][ri][bc], lbs);
        }
        if(lbs > ans){
            ans = lbs;
            lst = i;
        }
    }
    cout << ans << "\n";
    vi lbs;
    while(from[lst] != -1){
        lbs.emplace_back(lst + 1);
        lst = from[lst];
    }
    lbs.emplace_back(lst + 1);
    for(int i = sz(lbs) - 1; i >= 0; i--){
        cout << lbs[i] << " ";
    }
    cout << "\n";
    return;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

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