Overview

This problem asks us to find the number of ways to select exactly \(K\) items out of \(N\) sweets such that the total sum of their satisfaction values is at least \(X\). Noticing the constraint \(N \le 36\), we can solve this efficiently using meet-in-the-middle.

Analysis

Naive Approach (Exhaustive Search) and Its Limitations

First, let’s consider naively searching all combinations of selecting \(K\) sweets from \(N\) sweets. The maximum number of combinations to choose is \(\binom{36}{18} = 9,075,135,300 \approx 9 \times 10^9\). Since a standard computer can perform around \(10^8\) operations per second, a simple exhaustive search will result in Time Limit Exceeded (TLE).

Solution using Meet-in-the-Middle

The constraint \(N \le 36\) is a typical sign to apply meet-in-the-middle in competitive programming. Let’s divide the array into two halves: the first half of size \(N_1 = \lfloor N/2 \rfloor\) and the second half of size \(N_2 = N - N_1\).

• \(N_1\) and \(N_2\) are at most \(18\).
• There are only \(2^{18} = 262,144\) possible subsets (choose / do not choose) for 18 elements.

If we precalculate the “number of selected items” and “the sum of satisfaction values” for both the first half and the second half, we can efficiently count the pairs satisfying the condition using binary search.

Algorithm

Specifically, we can solve the problem with the following steps:

1. Divide the array: Divide the sweets into the first \(N_1 = \lfloor N / 2 \rfloor\) sweets and the remaining \(N_2 = N - N_1\) sweets.

2. Enumerate the first half: Using bit brute-force, explore all \(2^{N_1}\) patterns of choosing or not choosing each sweet in the first half \(N_1\). Record the total satisfaction value into a dynamic array S1[c1] for each “number of selected sweets \(c_1\)”.

3. Enumerate the second half: Similarly, explore all \(2^{N_2}\) patterns for the second half \(N_2\) and record the total satisfaction value into S2[c2] for each “number of selected sweets \(c_2\)”.

4. Sort the second half data: To enable binary search, sort each list S2[c2] in ascending order.

5. Count the pairs: Fix the number of selected sweets in the first half \(c_1\) (\(0 \le c_1 \le N_1\)). The number of sweets to select from the second half to make the total equal to \(K\) is uniquely determined as \(c_2 = K - c_1\) (skip if \(c_2\) is outside \(0 \le c_2 \le N_2\)).

For each satisfaction sum \(s_1\) in S1[c1], the condition that the overall sum is at least \(X\) can be rewritten as: $\(s_1 + s_2 \ge X \iff s_2 \ge X - s_1\)$

Therefore, we can use binary search (std::lower_bound) to quickly count how many elements in sorted S2[c2] are greater than or equal to \(X - s_1\), and add this count to the answer.

Complexity

• Time Complexity: \(O(N \cdot 2^{N/2})\)

  • Enumerating the first and second halves takes \(O(N_1 2^{N_1} + N_2 2^{N_2}) = O(N \cdot 2^{N/2})\).
  • Sorting the second half takes \(O(N \cdot 2^{N/2})\).
  • Performing binary searches for each element in the first half takes \(O(N_1 \cdot 2^{N_1}) = O(N \cdot 2^{N/2})\).
  • For \(N = 36\), \(N/2 = 18\), which requires around \(18 \times 2^{18} \approx 4.7 \times 10^6\) operations, making it well within time limits.

• Space Complexity: \(O(2^{N/2})\)

  • Memory used to store the enumerated results of the first and second halves is \(O(2^{N_1} + 2^{N_2}) = O(2^{N/2})\). Storing \(2^{18}\) long long variables requires only a few megabytes, which is well within the memory limit.

Implementation Points

• Beware of integer overflow: The satisfaction values \(A_i\) can be up to \(10^9\), so the sum of 36 items can reach up to \(3.6 \times 10^{10}\). Since this overflows a standard 32-bit integer (int), use 64-bit integers (long long in C++) for satisfaction sums, the input \(X\), and the variable holding the final answer.

• Group elements by the number of selected items: If you simply group all sums together, you cannot satisfy the constraint of “choosing exactly \(K\) items in total”. Therefore, it is essential to categorize the sums by the number of items selected (\(c_1, c_2\)).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    long long X;
    if (!(cin >> N >> K >> X)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    int N1 = N / 2;
    int N2 = N - N1;

    vector<vector<long long>> S1(N1 + 1);
    for (int mask = 0; mask < (1 << N1); ++mask) {
        int cnt = 0;
        long long sum = 0;
        for (int i = 0; i < N1; ++i) {
            if ((mask >> i) & 1) {
                cnt++;
                sum += A[i];
            }
        }
        S1[cnt].push_back(sum);
    }

    vector<vector<long long>> S2(N2 + 1);
    for (int mask = 0; mask < (1 << N2); ++mask) {
        int cnt = 0;
        long long sum = 0;
        for (int i = 0; i < N2; ++i) {
            if ((mask >> i) & 1) {
                cnt++;
                sum += A[N1 + i];
            }
        }
        S2[cnt].push_back(sum);
    }

    for (int i = 0; i <= N2; ++i) {
        sort(S2[i].begin(), S2[i].end());
    }

    long long ans = 0;
    for (int c1 = 0; c1 <= N1; ++c1) {
        int c2 = K - c1;
        if (c2 < 0 || c2 > N2) continue;

        for (long long s1 : S1[c1]) {
            long long target = X - s1;
            auto it = lower_bound(S2[c2].begin(), S2[c2].end(), target);
            ans += distance(it, S2[c2].end());
        }
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.6-flash-high.