Submission #1098598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098598		vjudge1	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2742 ms	51964 KiB

subsequence

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const ll maxn = 1e5 + 2, LG = 21, mod = 998244353, inf = 1e18;
int n, a[maxn], k, dp[maxn], trace[maxn], last[2048][2048][11];
vector<int> ok;
pair<int, int> res = {0, 0};
int main ()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        cin >> k;
        int l = a[i] & ((1 << 10) - 1), r = (a[i] >> 10) & ((1 << 10) - 1);
        for (int mask = 0; mask < (1 << 10); mask++)
        {
            int kk = k - __builtin_popcount(mask & r);
            if (kk < 0 || kk > 10) continue;
            if (dp[i] < dp[last[mask][l][kk]])
            {
                dp[i] = dp[last[mask][l][kk]];
                trace[i] = last[mask][l][kk];
            }
        }
        dp[i]++;
        for (int mask = 0; mask < (1 << 10); mask++)
        {
            int kk = __builtin_popcount(mask & l);
            if (dp[last[r][mask][kk]] < dp[i])
            {
                last[r][mask][kk] = i;
            }
        }
        res = max(res, {dp[i], i});
    }
    cout << res.first << '\n';
    while (res.second != 0)
    {
        ok.push_back(res.second);
        res.second = trace[res.second];
    }
    reverse(ok.begin(), ok.end());
    for (int i : ok) cout << i << " ";
}

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