Submission #1127303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127303		Gray	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	3376 ms	47212 KiB

subsequence

#ifndef LOCAL
#pragma GCC target("sse3")
#pragma GCC optimize("Ofast")
#endif
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define popcnt __builtin_popcount
void solve(){
    ll n; cin >> n;
    int a[n], k[n];
    for (ll i=0; i<n; i++){
        cin >> a[i];
    }
    for (ll i=0; i<n; i++){
        cin >> k[i];
    }
    int past[1<<10][1<<10][11];
    for (ll i=0; i<(1<<10); i++){
        for (ll j=0; j<(1<<10); j++){
            for (ll l=0; l<11; l++) past[i][j][l]=-1;
        }
    }
    int ldp[n], dep[n];
    for (ll i=0; i<n; i++){
        ldp[i]=1; dep[i]=-1;
    }
    for (ll i=0; i<n; i++){
        ll l = a[i]>>10, r=a[i]&((1<<10)-1);
        for (ll j=0; j<(1<<10); j++){
            if (k[i]>=popcnt(j&l) and k[i]-popcnt(j&l)<=10 and past[j][r][k[i]-popcnt(j&l)]!=-1 and ldp[i]<ldp[past[j][r][k[i]-popcnt(j&l)]]+1){
                ldp[i]=ldp[past[j][r][k[i]-popcnt(j&l)]]+1;
                dep[i]=past[j][r][k[i]-popcnt(j&l)];
            }
        }
        for (ll j=0; j<(1<<10); j++){
            if (past[l][j][popcnt(r&j)]==-1 or ldp[past[l][j][popcnt(r&j)]]<ldp[i]){
                past[l][j][popcnt(r&j)]=i;
            }
        }
    }
    ll mx = *max_element(ldp, ldp+n);
    cout << mx << ln;
    for (ll i=0; i<n; i++){
        if (ldp[i]==mx){
            ll cur = i;
            vector<ll> res;
            while (cur!=-1){
                res.push_back(cur+1);
                cur=dep[cur];
            }
            reverse(res.begin(), res.end());
            for (auto ch:res) cout << ch << " ";
            cout << ln; break;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifndef LOCAL
    // freopen("subsequence.in", "r", stdin);
    // freopen("subsequence.out", "w", stdout);
    #endif
    auto start = chrono::high_resolution_clock::now();
    ll t=1;
    // cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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