Submission #1126039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126039		Chris_Black	Longest beautiful sequence (IZhO17_subsequence)	C++20	0 / 100	10 ms	1864 KiB

subsequence

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORR(i, a, b) for(int i = a; i >= b; --i)
#define vi vector<int>
#define vb vector<bool>
#define pb push_back
#define vvi vector<vi>

using namespace std;
const int N = 1e5 + 9, B = 10;
const int Inf = 0x3f3f3f3f;

int n, a[N], k[N], len[N], f[N];
int dp[(1 << B) + 2][(1 << B) + 2][B + 2];
int t[(1 << B) + 2][(1 << B) + 2][B + 2];

int get_left(int x)
{
    return x >> 10;
}
int get_right(int x)
{
    return x & ((1 << 10) - 1);
}

void solve()
{
    cin >> n;
    FOR(i, 1, n)cin >> a[i];
    FOR(i, 1, n)cin >> k[i];

    FOR(i, 1, n)
    {
        len[i] = 1;
        f[i] = 0;

        int l = get_left(a[i]), r = get_right(a[i]);

        for(int ll = 0; ll < (1 << 10); ++ll)
            if(k[i] >= __builtin_popcount(l & ll) &&
               len[i] < dp[ll][r][k[i] - __builtin_popcount(l & ll)] + 1)
        {
            len[i] = dp[ll][r][k[i] - __builtin_popcount(l & ll)] + 1;
            f[i] = t[ll][r][k[i] - __builtin_popcount(l & ll)];
        }

        for(int rr = 0; rr < (1 << 10); ++rr)
            if(dp[l][rr][__builtin_popcount(r & rr)] <= len[i])
        {
            dp[l][rr][__builtin_popcount(r & rr)] = len[i];
            t[l][rr][__builtin_popcount(r & rr)] = i;
        }
    }

    int bst = 1;
    FOR(i, 2, n)
        if(len[i] > len[bst])
            bst = i;

    cout << len[bst] << '\n';
    vi res;
    for(int x = bst; x; x = f[x])
        res.pb(x);
    reverse(res.begin(), res.end());

    for(auto e : res)cout << e << ' ';
    cout << '\n';
}

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

    int t = 1;
//    cin >> t;
    while(t --)
        solve();
    return 0;
}

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