Submission #1257244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257244		dosts	Longest beautiful sequence (IZhO17_subsequence)	C++20	0 / 100	72 ms	180832 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;
const int lim = (1<<10);
pii tut[lim][lim][11];//solu böyle sağı şuna bu uzaklıkta

bool chmax(pii& p1,pii p2) {
    if (p2.ff > p1.ff) p1 = p2;
    else if (p1.ff == p2.ff && p2.ss < p1.ss) p1 = p2;
    return (p1 == p2);
}

void solve() {  
    int n;
    cin >> n;
    vi a(n+1);
    for (int i=1;i<=n;i++) cin >> a[i];
    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,inf};
    vector<pii> dp(n+1);
    for (int i=1;i<=n;i++) dp[i] = {1,i};
    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;
            chmax(dp[i],{tut[j][sag][rem].ff+1,tut[j][sag][rem].ss});
        }
        for (int j = 0;j<lim;j++) {
            int ortak = __builtin_popcountll(sag&j);
            chmax(tut[sol][j][ortak],{dp[i].ff,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].ff == 1) break;
        ptr = dp[ptr].ss;
    }
    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