Submission #852784

#	Time	Username	Problem	Language	Result	Execution time	Memory
852784		tien9d2	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2559 ms	101960 KiB

subsequence

// Don't look at my code, you will be addicted!

#include <bits/stdc++.h>
#define ii pair <int, int>
#define F first
#define S second

using namespace std;

const int mod = 1e9 + 7;
const int N = 1e5 + 5;
const int M = 1026;

int dp[N], res[M][M][24], trace[N], bitcount[M];
int n, a[N];

void mush(int i, int t){
    if (dp[i] < dp[t] + 1){
        dp[i] = dp[t] + 1;
        trace[i] = t;
    }
}

void truyvet(int i){
    if (i == 0) return;
    truyvet(trace[i]);
    cout << i << ' ';
}

void solve(){
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    int lm = 1024;
    for (int i = 0; i < 1024; ++ i){
        for (int j = 0; j < 10; ++ j) bitcount[i] += ((i >> j) & 1);
    }

    int mx = 0;
    for (int i = 1; i <= n; ++ i){
        int k; cin >> k;
        int lft = a[i] >> 10;
        int rg = ((1 << 10) - 1) & a[i];
        for (int j = 0; j < lm; ++ j){
            int val = bitcount[lft & j];
            if (val > k) continue;
            int t = res[j][rg][k - val];
            mush(i, t);
        }

        for (int j = 0; j < lm; ++ j){
            int val = bitcount[rg & j];
            if (dp[i] > dp[res[lft][j][val]]) res[lft][j][val] = i;
        }

        mx = max(mx, dp[i]);
    }


    cout << mx << '\n';
    for (int i = n; i >= 1; -- i){
        if (dp[i] == mx){
            truyvet(i);
            break;
        }
    }
}

int main(){
    //freopen("code.inp", "r", stdin);
    //freopen("code.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while (t --) solve();

    return 0;
}

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