제출 #919812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
919812		LOLOLO	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4672 ms	199648 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 1e5 + 100;
const int M = 1025;
int a[N], k[N], f[N], trace[N], cnt[M];
pair <int, int> dp[M][M][24];

void maximize(pair <int, int> &a, pair <int, int> b) {
    if (a < b)
        a = b;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for (int i = 0; i < M; i++)
        cnt[i] = cntbit(i);

    int n;
    cin >> n;

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

    for (int i = 1; i <= n; i++)
        cin >> k[i];

    for (int i = 1; i <= n; i++) {
        int pr = 0, suff = 0;
        for (int j = 0; j < 10; j++) {
            if (a[i] & (1 << j)) {
                pr |= (1 << j);
            }

            if (a[i] & (1 << (j + 10))) {
                suff |= (1 << j);
            }
        }

        f[i] = 1;

        for (int mask = 0; mask < M; mask++) {
            int cc = cnt[mask & pr];
            if (cc <= k[i] && f[i] < dp[mask][suff][k[i] - cc].f + 1) {
                f[i] = dp[mask][suff][k[i] - cc].f + 1;
                trace[i] = dp[mask][suff][k[i] - cc].s;
            }
        }

        for (int mask = 0; mask < M; mask++) {
            maximize(dp[pr][mask][cnt[suff & mask]], make_pair(f[i], i));
        }
    }

    int id = 1;
    for (int i = 1; i <= n; i++)
        if (f[i] > f[id])
            id = i;

    cout << f[id] << "\n";
    vector <int> lst;

    while (id) {
        lst.pb(id);
        id = trace[id];
    }

    reverse(all(lst));
    for (auto x : lst)
        cout << x << " ";

    cout << '\n';

    return 0;
}

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