Overview

We use meet-in-the-middle by dividing the sweets into the first half and the second half, and for each subset, enumerating the “number of chosen items” and the “sum of satisfaction values”. By sorting the sum of values for the second half, we can count the number of valid combinations using binary search.

Analysis

If we check all possible choices directly, there are up to \(2^{36}\) subsets. This is approximately \(68.7\) billion, which will not run within the time limit if fully enumerated.

Also, dynamic programming with the total satisfaction as a state would require an excessively large array, as \(A_i\) can be up to \(10^9\).

Therefore, we split the \(N\) sweets into the first half and the second half as follows:

• The number of sweets in the first half: \(n_1\)
• The number of sweets in the second half: \(n_2\)

Since each half contains roughly \(N/2\) sweets, the number of subsets on each side is at most around \(2^{18}\). This can be comfortably enumerated.

For each subset, we record the following two values:

• How many sweets were chosen
• The sum of satisfaction values

When choosing \(l\) sweets from the first half and \(r\) sweets from the second half, to choose exactly \(K\) sweets in total, we need:

\( l+r=K \)

Furthermore, letting \(s_L\) be the total satisfaction from the first half and \(s_R\) be the total satisfaction from the second half, the required condition is:

\( s_L+s_R \geq X \)

This can be rewritten as:

\( s_R \geq X-s_L \)

Thus, by sorting the total values when choosing \(r\) sweets from the second half in advance, we can quickly count how many total values are greater than or equal to \(X-s_L\) using lower_bound.

For example, if the total values in the second half are

\([1,3,4,8]\)

and the sum from the first half is \(7\) with \(X=10\), then the second half needs at least

\(10-7=3\)

Finding the position of the first \(3\) using binary search reveals that there are \(3\) values satisfying the condition: \(3,4,8\).

Algorithm

1. Split the sweets into the first half \(n_1=N/2\) and the second half \(n_2=N-n_1\).
2. Enumerate all subsets of the first half.
   • Let \(c\) be the number of chosen sweets.
   • Let \(s\) be the total satisfaction.
   • Add \(s\) to left[c].
3. Similarly, enumerate all subsets of the second half and add the sum to right[c].
4. Sort each right[c] in ascending order.
5. Iterate through all possible number of chosen sweets from the first half, leftCount.
   • Set the number of sweets to choose from the second half as rightCount = K - leftCount.
   • Ignore if rightCount is out of bounds.
6. For each sum leftSum in left[leftCount], the second half requires a sum of at least \(X-\mathrm{leftSum}\).
7. Perform lower_bound on right[rightCount] and add the number of elements from that position to the end to the answer.
8. Output the final sum.

Since each way of choosing \(K\) items uniquely decomposes into “a subset chosen from the first half” and “a subset chosen from the second half”, there is no double counting.

Complexity

Let \(m=\lceil N/2\rceil\).

• Time Complexity: \(O(N2^m)\)
• Space Complexity: \(O(2^m)\)

Even including the enumeration of subsets, sorting the sums for the second half, and binary searching for each subset of the first half, this is sufficiently fast when \(N\leq 36\).

Implementation Points

• The sum of satisfaction values can reach up to \(36\times 10^9\), so use long long.

• The answer can also be close to \(2^{36}\), so long long is required instead of int.

• It is important to store total values separately for each number of chosen items. This allows us to count only the combinations where the sum of items chosen from both halves equals exactly \(K\).

• The number of elements from the position returned by lower_bound to the end is the count of valid second-half subsets.

  Source Code

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

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

    int N, K;
    long long X;
    cin >> N >> K >> X;

    vector<long long> A(N);
    for (auto& a : A) cin >> a;

    int n1 = N / 2;
    int n2 = N - n1;

    vector<vector<long long>> left(n1 + 1), right(n2 + 1);

    for (int mask = 0; mask < (1 << n1); ++mask) {
        long long sum = 0;
        int count = 0;
        for (int i = 0; i < n1; ++i) {
            if (mask >> i & 1) {
                sum += A[i];
                ++count;
            }
        }
        left[count].push_back(sum);
    }

    for (int mask = 0; mask < (1 << n2); ++mask) {
        long long sum = 0;
        int count = 0;
        for (int i = 0; i < n2; ++i) {
            if (mask >> i & 1) {
                sum += A[n1 + i];
                ++count;
            }
        }
        right[count].push_back(sum);
    }

    for (auto& sums : right) {
        sort(sums.begin(), sums.end());
    }

    long long answer = 0;

    for (int leftCount = 0; leftCount <= n1; ++leftCount) {
        int rightCount = K - leftCount;
        if (rightCount < 0 || rightCount > n2) continue;

        const auto& rightSums = right[rightCount];
        for (long long leftSum : left[leftCount]) {
            auto it = lower_bound(
                rightSums.begin(), rightSums.end(), X - leftSum
            );
            answer += rightSums.end() - it;
        }
    }

    cout << answer << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.6-sol-high.