Submission #475179

#	Time	Username	Problem	Language	Result	Execution time	Memory
475179		TheScrasse	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5423 ms	97220 KiB

subsequence

#pragma GCC optimize("Ofast")

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

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (int)1e9
#define mod 998244353
#define maxn 100010
#define maxb 1024
#define maxs 1048576
#define maxp 11

int i, i1, j, k, k1, t, n, m, flag[10], a[maxn], b[maxn];
int mk1, mk2, mk3, cr, pr[maxn], pc[maxs];
array<int, 2> dp[maxb][maxb][maxp], res;
array<int, 5> rs;
vector<int> rsv;

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

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    for (i = 0; i < maxs; i++) pc[i] = __builtin_popcount(i);

    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (i = 1; i <= n; i++) {
        cin >> b[i];
    }

    for (i = 1; i <= n; i++) {
        mk1 = (a[i] >> 10); mk2 = a[i] - (1 << 10) * mk1;
        // cout << "mk1, mk2 = " << mk1 _ mk2 << nl;

        rs = {1, 0, 0, 0, 0};
        for (mk3 = 0; mk3 < (1 << 10); mk3++) {
            m = b[i] - pc[mk1 & mk3];
            if (m < 0 || m > 10) continue;
            rs = max(rs, {dp[mk3][mk2][m][0] + 1, dp[mk3][mk2][m][1], mk3, mk2, m});

            // cout << "query" _ mk3 _ mk2 _ m _ dp[mk3][mk2][m][0] + 1 << nl;
        }
        res = max(res, {rs[0], i}); pr[i] = rs[1];

        for (mk3 = 0; mk3 < (1 << 10); mk3++) {
            m = pc[mk2 & mk3];
            if (rs[0] > dp[mk1][mk3][m][0]) {
                dp[mk1][mk3][m] = {rs[0], i};
            }

            // cout << "upd" _ mk1 _ mk3 _ m _ dp[mk1][mk3][m][0] << nl;
        }
    }

    /* for (i = 1; i <= n; i++) cout << pr[i] << ' ';
    cout << nl; */

    cout << res[0] << nl;
    cr = res[1];
    while (cr != 0) {
        rsv.pb(cr); cr = pr[cr];
    }

    reverse(rsv.begin(), rsv.end());
    for (auto u : rsv) cout << u << ' ';
    cout << nl;

    return 0;
}

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