Submission #1257226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257226		dosts	Longest beautiful sequence (IZhO17_subsequence)	C++20	0 / 100	70 ms	180808 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];//ilk kısmı böyle ikinci kısmı buna şu uzaklıkta

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<1<<10;i++) for (int j = 0;j<1<<10;j++) for (int k = 0;k<=10;k++) tut[i][j][k] ={0,-1};
    vi dp(n+1,1),go(n+1,-1);
    for (int i=1;i<=n;i++) {
        int k;
        cin >> k;
        for (int j = 0;j<(1<<10);j++){
            int diff = __builtin_popcountll(j&(a[i]&1023));
            int rem = k-diff;
            if (rem < 0) continue;
            if (tut[j][a[i]>>10][rem].ff+1 > dp[i]) {
                dp[i] = tut[j][a[i]>>10][rem].ff+1;
                go[i] = tut[j][a[i]>>10][rem].ss;
            }
        }
        for (int j = 0;j<(1<<10);j++) {
            int ortak = __builtin_popcountll((a[i]>>10)&j);
            int& tutt = tut[a[i]&1023][j][ortak].ff;
            if (dp[i] > tutt) {
                tutt = dp[i],tut[a[i]&1023][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 (go[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