Overview

Given the number of sweets \(S_i\) required to satisfy each child, maximize the “number of children that can be satisfied” using at most \(P\) sweets in total.

Analysis

The key observation is: “If we want to maximize the number of children, it is optimal to satisfy children in order of smallest requirement first.”

• To satisfy one child, you must give them all \(S_i\) sweets (giving only a partial amount is meaningless).
• Therefore, to select as many children as possible within a limited budget \(P\), it is natural to prioritize those with the smallest cost (required number of sweets).

Concrete example: - When \(P=10\), \(S=[6,6,2,2]\):
Choosing in descending order gives \(6+6=12\), so we can satisfy at most 1 child.
Choosing in ascending order gives \(2+2+6=10\), so we can satisfy 3 children.

Naively “exhaustively searching all subsets of children to satisfy” would involve \(2^N\) combinations, which is completely infeasible for \(N \le 2\times 10^5\) (TLE).
This problem can be solved optimally by simply “greedily selecting in ascending order.”

Why the greedy approach is correct (intuition): - In any solution, if a child with a larger requirement is selected while there exists an unselected child with a smaller requirement, we can swap them to reduce the total number of sweets used (while maintaining the count of children). - If we can reduce the total, we increase the possibility of adding yet another child, which is advantageous for maximizing the count. - Therefore, the form of “packing children starting from the smallest requirement” is optimal.

Algorithm

1. Sort the array \(S\) in ascending order.
2. Iterate from the smallest, adding \(S_i\) to a running total total, and accept the child as long as it does not exceed \(P\).
3. Once total + S_i > P is reached, all subsequent children have even larger requirements and cannot possibly be accepted, so we can break early.
4. Output the number of children accepted.

Complexity

• Time complexity: Dominated by sorting, \(O(N \log N)\)
• Space complexity: \(O(N)\) for storing the array

Implementation Notes

• Since \(P \le 10^{18}\), the running total total can become very large. In Python, arbitrary-precision integers handle this safely, but in other languages, use long long or equivalent.

• It is important to break as soon as total + x > P (since all subsequent values are also impossible).

• Since the input size can be large, using sys.stdin.readline in Python ensures stable performance.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, P = map(int, input().split())
    S = list(map(int, input().split()))
    S.sort()
    total = 0
    ans = 0
    for x in S:
        if total + x > P:
            break
        total += x
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.