Overview

We use Meet-in-the-Middle by splitting the sweets into a first half and a second half, and enumerating the “number of chosen items” and “sum of satisfaction values” for all subsets of each half. If \(l\) items are chosen from the first half, we count the combinations of choosing \(K-l\) items from the second half using binary search.

Analysis

Directly checking all ways of choosing yields at most

\[{N \choose K}\]

combinations. Especially around \(N=36,\ K=18\), the number of combinations is extremely large, so a brute-force search will not finish in time. Additionally, enumerating all subsets takes \(O(2^N)\) time, and \(2^{36}\) is far too large.

Therefore, we divide the sweets into the first half and the second half as follows:

• First half: approximately \(N/2\) items
• Second half: the remaining approximately \(N/2\) items

The number of subsets for each half is at most around \(2^{18}\), which is small enough to enumerate completely.

However, in this problem, we need to choose exactly \(K\) sweets in addition to tracking the total satisfaction. Thus, we categorize the sum of satisfaction values of each subset by the number of chosen items.

Suppose we choose \(l\) items from the first half with a total satisfaction of \(s\). In this case, we must choose \(K-l\) items from the second half. Letting \(t\) be the total satisfaction from the second half, the condition is

\[s+t \geq X\]

Therefore, we need to count the number of subsets in the second half that satisfy

\[t \geq X-s\]

By sorting the total sums of the second half for each count of chosen items, we can use binary search to find the first position where the sum is at least \(X-s\).

For example, if the sums when choosing the specified number of items from the second half are

\[[3,5,8,11]\]

and the sum from the first half is \(s=6\) with a target of \(X=14\), then for the second half we need

\[t \geq 14-6=8\]

The values that are at least \(8\) are \(8\) and \(11\), giving \(2\) ways.

Algorithm

1. Split the array of sweets into a first half and a second half.
2. For each half, enumerate all subsets and store the sum of satisfaction values categorized by the number of chosen items.
   • Store the total sums of subsets with exactly \(c\) items chosen in groups[c].
3. Sort each list in the second half in ascending order.
4. Let the number of items chosen from the first half be left_count.
   • The number of items to choose from the second half is right_count = K - left_count.
   • If right_count is out of the valid range of choices from the second half, ignore it.
5. For each total sum left_sum in the first half, the required sum from the second half is X - left_sum.
6. Use bisect_left to find the first position in the second half’s list of sums that is greater than or equal to X - left_sum.
7. Add the number of elements from that position onward to the answer.

When enumerating subset sums, process each sweet one by one and update the count of chosen items from larger to smaller values. Updating in descending order prevents using the same sweet multiple times during a single step.

Complexity

• Time Complexity: \(O\left(N2^{\lceil N/2\rceil}\right)\)
• Space Complexity: \(O\left(2^{\lceil N/2\rceil}\right)\)

The number of subsets in the first and second halves is at most \(2^{\lceil N/2\rceil}\) each. Including the sorting of the second half and the binary searches for each subset in the first half, the time complexity becomes as stated above.

Implementation Points

• You need to store subset sums categorized by the number of chosen items. Storing only the total sum makes it impossible to check the condition “exactly \(K\) items.”

• bisect_left(right_sums, X - left_sum) returns the first position that is greater than or equal to X - left_sum. Therefore, the count of elements satisfying the condition is len(right_sums) - pos.

• When updating subset sums, iterate through the number of chosen items from largest to smallest. If updated in ascending order, states where the currently processed sweet is chosen multiple times would be generated.

• The answer can be at most \({36 \choose 18}\), which does not fit in a 32-bit integer. Python integers have arbitrary precision, so they can handle this directly.

  Source Code

import sys
from bisect import bisect_left

def subset_sums_by_count(values):
    n = len(values)
    groups = [[] for _ in range(n + 1)]
    groups[0] = [0]
    used = 0

    for value in values:
        used += 1
        for count in range(used, 0, -1):
            groups[count].extend([s + value for s in groups[count - 1]])

    return groups

def main():
    input = sys.stdin.readline
    N, K, X = map(int, input().split())
    A = list(map(int, input().split()))

    mid = N // 2
    left = subset_sums_by_count(A[:mid])
    right = subset_sums_by_count(A[mid:])

    for sums in right:
        sums.sort()

    answer = 0
    for left_count, left_sums in enumerate(left):
        right_count = K - left_count
        if not (0 <= right_count < len(right)):
            continue

        right_sums = right[right_count]
        right_size = len(right_sums)

        for left_sum in left_sums:
            pos = bisect_left(right_sums, X - left_sum)
            answer += right_size - pos

    print(answer)

if __name__ == "__main__":
    main()

---

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