Submission #533161

#	Time	Username	Problem	Language	Result	Execution time	Memory
533161		cookiemonster04	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	1928 ms	54196 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define MOD 1000000007
#define endl '\n'
#define MAXN 100005
#define SQ 1024

/* Date: 3/4/22
 * Link: https://oj.uz/problem/view/IZhO17_subsequence
 * Verdict: ?
 */

int bcnt[SQ];
int N;
pii dp[11][SQ][SQ];
int arr[MAXN];
int K[MAXN];
int best[MAXN];

inline void maxe(pii &a, pii b) {
    if (a.first < b.first) {
        a = b;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];
    for (int i = 0; i < N; i++) cin >> K[i];
    for (int i = 1; i < SQ; i++) {
        bcnt[i] = bcnt[i>>1]+(i&1);
    }
    for (int i = 0; i < N; i++) {
        int hi = arr[i] >> 10;
        int lo = arr[i] & (SQ-1);
        pii qans = mp(0, -1);
        int ck = K[i];
        for (int j = 0; j < SQ; j++) {
            int reqb = ck-bcnt[lo&j];
            if (reqb >= 0 && reqb <= 10) maxe(qans, dp[reqb][hi][j]);
        }
        best[i] = qans.second;
        qans.first++; qans.second = i;
        for (int j = 0; j < SQ; j++) {
            maxe(dp[bcnt[hi&j]][j][lo], qans);
        }
    }
    pii ans = mp(0, 0);
    for (int i = 0; i < 10; i++) for (int j = 0; j < SQ; j++) maxe(ans, dp[i][0][j]);
    cout << ans.first << endl;
    int cnode = ans.second;
    vector<int> v;
    while(cnode != -1) {
        v.pb(cnode+1);
        cnode = best[cnode];
    }
    for (int i = v.size()-1; i >= 0; i--) cout << v[i] << " ";
    cout << endl;
    return 0;
}

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