Submission #1127654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127654		mirciu	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	3568 ms	92908 KiB

subsequence

#include <iostream>
#include <vector>

using namespace std;

const int BMAX = 10;        // Number of bits for each part (left/right)
const int NMAX = 1 << BMAX; // 2^10, maximum number of combinations for 10 bits

// DP tables
int dp[NMAX + 1][NMAX + 1][BMAX + 1]; // Stores max length of sequence for state
int t[NMAX + 1][NMAX + 1][BMAX + 1];  // Tracks the index contributing to each state

inline int get_left(const int x)
{
    return x >> 10;
}

inline int get_right(const int x)
{
    return x & ((1 << 10) - 1);
}

vector<int> f;

void print(int x)
{
    if (x == 0)
        return;

    print(f[x]);
    cout << x << ' ';
}

// Function to solve the problem
void solve()
{
    int n;
    cin >> n;

    vector<int> a(n + 1), k(n + 1), len(n + 1, 1);
    f = vector<int>(n + 1, 0);

    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)
    {
        // Get the left and right parts of the current number
        int l = get_left(a[i]);
        int r = get_right(a[i]);

        // Check all possible left masks for compatibility
        for (int left_mask = 0; left_mask < (1 << 10); ++left_mask)
        {
            // Calculate the number of 1-bits in the overlap of left_mask and l
            int bit_count = __builtin_popcount(l & left_mask);

            // Verify if k[i] can be satisfied with this left_mask
            if (k[i] >= bit_count && k[i] - bit_count <= 10)
            {
                // Calculate the length of the sequence if extended
                int crt_len = dp[left_mask][r][k[i] - bit_count] + 1;

                // Update the current element's length if this sequence is longer
                if (crt_len > len[i])
                {
                    len[i] = crt_len;                         // Update length
                    f[i] = t[left_mask][r][k[i] - bit_count]; // Track predecessor
                }
            }
        }

        // Update DP table with the current element's data
        for (int right_mask = 0; right_mask < (1 << 10); ++right_mask)
        {
            // Calculate the number of 1-bits in the overlap of r and right_mask
            int bit_count = __builtin_popcount(r & right_mask);

            // Update DP table if the current sequence is longer
            if (dp[l][right_mask][bit_count] < len[i])
            {
                dp[l][right_mask][bit_count] = len[i]; // Update max length
                t[l][right_mask][bit_count] = i;       // Track the index
            }
        }
    }

    int bst = 1;
    for (int i = 2; i <= n; ++i)
        if (len[i] > len[bst])
            bst = i;

    cout << len[bst] << '\n';

    print(bst);

    cout << '\n';
}

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

    solve();

    return 0;
}

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