Submission #1257231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257231		dosts	Longest beautiful sequence (IZhO17_subsequence)	C++20	0 / 100	69 ms	180996 KiB

subsequence

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define alperen_t int32_t
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 998244353, inf = 1e18;

const int N = 5e3+10;
pii tut[(1<<10)][(1<<10)][11];//solu böyle sağı şuna bu uzaklıkta

void solve() {  
    int n;
    cin >> n;
    vi a(n+1);
    for (int i=1;i<=n;i++) cin >> a[i];
    int lim = (1<<10);
    for (int i = 0;i<lim;i++) for (int j = 0;j<lim;j++) for (int k = 0;k<=10;k++) tut[i][j][k] ={-inf,-1};
    vi dp(n+1,1),go(n+1,-1);
    for (int i=1;i<=n;i++) {
        int k;
        cin >> k;
        int sol = a[i] >> 10;
        int sag = a[i]&1023;
        for (int j = 0;j<lim;j++){
            int ort = __builtin_popcountll(j&sol);
            int rem = k-ort;
            if (rem < 0) continue;
            if (tut[j][sag][rem].ff+1 > dp[i]) {
                dp[i] = tut[j][sag][rem].ff+1;
                go[i] = tut[j][sag][rem].ss;
            }
        }
        for (int j = 0;j<lim;j++) {
            int ortak = __builtin_popcountll(sag&j);
            if (dp[i] > tut[sol][j][ortak].ff) {
                tut[sol][j][ortak].ff = dp[i];
                tut[sol][j][ortak].ss = i;
            }
        }
    }
    vi lmao;
    auto mx = max_element(1+all(dp));
    int ptr = mx-dp.begin();
    vi v;
    while (1) {
        v.push_back(ptr);
        if (dp[ptr] == 1) break;
        ptr = go[ptr];
    }
    reverse(all(v));
    cout << big(v) << '\n';
    for (auto it : v) cout << it << ' ';
    cout << '\n';
    
}   

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
    #ifdef Dodi 
        cerr << "TIME TAKEN: " << (double)clock()/(double)CLOCKS_PER_SEC << "seconds!\n";
    #endif
}

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