Overview

This problem asks us to find the total number of ways to choose \(K\) sweets out of \(N\) sweets such that the sum of their satisfaction values is at least \(X\).

Analysis

Let’s first consider a naive approach. We could enumerate all combinations of choosing \(K\) sweets out of \(N\) and check if the total sum is at least \(X\). However, for \(N \leq 36\), when \(K \approx N/2\), the number of combinations reaches \(\binom{36}{18} \approx 9 \times 10^9\), which is far too large and will not finish in time.

Similarly, enumerating all possible subsets (\(2^{36} \approx 6.9 \times 10^{10}\) possibilities) will also fail to finish in time.

Here, we have an important observation: “\(2^{36}\) is way too large, but \(2^{18}\) is around \(260{,}000\), which is sufficiently small.” This is where the Meet in the Middle technique comes in.

We divide the \(N\) sweets into two groups: the first half of size \(n_1\) and the second half of size \(n_2\). By enumerating all subsets for each group separately, each group requires at most around \(2^{18}\) operations. After that, we just need to efficiently combine the choices from the first half and the second half to count the valid combinations.

Algorithm

Split the sweets into the first half L (\(n_1 = N/2\) elements) and the second half R (\(n_2 = N - n_1\) elements).

Precomputing the Second Half

Enumerate all subsets of the second half R, and record the “sum of satisfaction values \(s\)” for each “number of chosen sweets \(c\)”. That is, store in right[c] the list of total satisfaction values when choosing \(c\) sweets from the second half. Sort each list, as we will use binary search later.

Enumerating the First Half and Combining

Enumerate all subsets of the first half L. When a subset yields count \(c_1\) and sum \(s_1\), to choose \(K\) sweets in total, we must choose \(c_2 = K - c_1\) sweets from the second half.

To make the total sum at least \(X\), the sum \(s_2\) from the second half must satisfy:

\[ s_2 \geq X - s_1 \]

Since right[c2] is sorted, we can quickly count the number of elements greater than or equal to \(X - s_1\) using binary search. Summing this up over all subsets of the first half gives the final answer.

As a concrete example, if \(K = 3\) and we choose \(c_1 = 1\) sweet (sum \(s_1\)) from the first half, we need to choose \(c_2 = 2\) sweets from the second half. Counting the elements in right[2] whose sum is at least \(X - s_1\) gives all valid combinations for this choice.

Note that if \(c_2 = K - c_1\) is less than \(0\) or greater than \(n_2\), no such choice exists, so we skip it.

Complexity

Here, \(n_1, n_2 \approx N/2 = 18\).

• Time Complexity: Enumerating the second half takes \(O(2^{n_2} \cdot n_2)\), sorting takes \(O(2^{n_2} \cdot n_2)\), and enumerating the first half along with binary search takes \(O(2^{n_1} \cdot (n_1 + \log(2^{n_2})))\). Overall, this gives \(O(2^{N/2} \cdot N)\). Even for \(N = 36\), this is roughly \(2.6 \times 10^5 \times 36\) operations, which is easily fast enough.
• Space Complexity: \(O(2^{N/2})\) to store the sum values of all subsets of the second half.

Implementation Points

• The key point is to group the list of sum values for the second half by the count \(c\). This allows us to uniquely determine the number of items to pick from the second half based on the count picked from the first half, satisfying the constraint of choosing \(K\) items in total.

• To count the number of elements in a sorted list that are greater than or equal to a target value, Python’s bisect_left is convenient. Setting need = X - s1, len(arr) - bisect_left(arr, need) gives the count of elements that are at least \(X - s_1\).

• The total sum of satisfaction values can reach up to \(36 \times 10^9\), but since Python handles arbitrarily large integers automatically, there is no risk of integer overflow.

  Source Code

import sys
from bisect import bisect_left

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0]); K = int(data[1]); X = int(data[2])
    A = [int(data[3+i]) for i in range(N)]

    n1 = N // 2
    n2 = N - n1
    L = A[:n1]
    R = A[n1:]

    # 右側: count -> ソート済み sum リスト
    right = [[] for _ in range(n2 + 1)]
    for mask in range(1 << n2):
        c = 0
        s = 0
        m = mask
        idx = 0
        while m:
            if m & 1:
                c += 1
                s += R[idx]
            m >>= 1
            idx += 1
        right[c].append(s)
    for c in range(n2 + 1):
        right[c].sort()

    ans = 0
    for mask in range(1 << n1):
        c1 = 0
        s1 = 0
        m = mask
        idx = 0
        while m:
            if m & 1:
                c1 += 1
                s1 += L[idx]
            m >>= 1
            idx += 1
        c2 = K - c1
        if c2 < 0 or c2 > n2:
            continue
        need = X - s1
        arr = right[c2]
        # sum >= need の個数
        pos = bisect_left(arr, need)
        ans += len(arr) - pos

    print(ans)

main()

---

This editorial was generated by claude4.8opus-high.