Submission #387493

#	Time	Username	Problem	Language	Result	Execution time	Memory
387493		Lam_lai_cuoc_doi	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4340 ms	183720 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 2e6 + 5;
int a[N], k[N];
int n, dp[1025][1025][22], par[1025][1025][22];
int ancestor[N], ans(0), piv, cnt[N];

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

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

void Solve()
{
    for (int i = 0; i < 1024; ++i)
        cnt[i] = __builtin_popcount(i);

    for (int i = 1; i <= n; ++i)
    {
        int pref = a[i] >> 10,
            suff = a[i] & ((1 << 10) - 1);

        int res(0);

        for (int j = 0; j < 1024; ++j)
            if (cnt[suff & j] <= k[i])
                if (res < dp[pref][j][k[i] - cnt[suff & j]])
                {
                    res = dp[pref][j][k[i] - cnt[suff & j]];
                    ancestor[i] = par[pref][j][k[i] - cnt[suff & j]];
                }

        ++res;

        if (ans < res)
        {
            ans = res;
            piv = i;
        }

        for (int j = 0; j < 1024; ++j)
            if (dp[j][suff][cnt[j & pref]] < res)
            {
                dp[j][suff][cnt[j & pref]] = res;
                par[j][suff][cnt[j & pref]] = i;
            }
    }

    cout << ans << "\n";

    vector<int> trace(ans);
    trace.clear();

    while (piv != 0)
    {
        trace.emplace_back(piv);
        piv = ancestor[piv];
    }

    for (auto i = trace.rbegin(); i != trace.rend(); ++i)
        cout << (*i) << " ";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

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