Submission #735774

#	Time	Username	Problem	Language	Result	Execution time	Memory
735774		stevancv	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3659 ms	80644 KiB

subsequence

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int M = 1024;
const int inf = 2e9 + 2;
pair<int, int> dp[N], mx[21][M][M];
int a[N], k[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    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 v = a[i];
        for (int f = 0; f < M; f++) {
            int c = __builtin_popcount(v & f);
            if (k[i] < c) continue;
            pair<int, int> o = mx[k[i] - c][f][v >> 10];
            o.first += 1;
            smax(dp[i], o);
        }
        for (int f = 0; f < M; f++) {
            int c = __builtin_popcount((v >> 10) & f);
            if (dp[i].first > mx[c][v & (M - 1)][f].first)
                mx[c][v & (M - 1)][f] = {dp[i].first, i};
        }
    }
    int i = 1;
    for (int j = 2; j <= n; j++) if (dp[i].first < dp[j].first) i = j;
    cout << dp[i].first << en;
    vector<int> sol;
    while (i > 0) {
        sol.push_back(i);
        i = dp[i].second;
    }
    for (i = sol.size() - 1; i >= 0; i--) cout << sol[i] << sp;
    cout << en;
    return 0;
}

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