Overview

Given a number of sweets \(P\), the problem asks to satisfy as many children as possible (by distributing all the sweets each child needs).

Analysis

In this problem, each child \(i\) has a condition that “\(S_i\) sweets are needed.” To satisfy a child, you must give them all of their required sweets.

A straightforward approach would be: “Greedily distribute to children in order of least sweets needed first.” In other words, sort \(S_i\) in ascending order and keep selecting from the front as long as the total does not exceed \(P\).

However, for example, if there are 100,000 children, each requiring 100 million sweets, and the total exceeds 10 billion, a simple loop would be too slow (TLE). Therefore, we use prefix sums to quickly compute “the total number of sweets needed to satisfy the first \(k\) children,” and then use binary search to find “the maximum number of children that can be satisfied.”

In this way, instead of a simple loop, we can solve the problem efficiently by combining the classic techniques of sorting + prefix sums + binary search.

Algorithm

1. Sort each child’s required number of sweets \(S_i\) in ascending order.
2. Precompute the prefix sums of the sorted array. This allows us to obtain the total number of sweets needed to satisfy the first \(k\) children in \(O(1)\).
3. Use binary search to determine “how many children can be satisfied”:
   • If cumsum[k] <= P, then \(k\) children can be satisfied, so update the answer candidate and check if more children can be added (left = mid + 1).
   • If cumsum[k] > P, then \(k\) children cannot be satisfied, so reduce the number (right = mid - 1).
4. Output the maximum number of children obtained after the search completes.

Example

Input:

5 10
3 1 4 2 5

• After sorting: [1, 2, 3, 4, 5]
• Prefix sums: [0, 1, 3, 6, 10, 15]
• Binary search finds cumsum[4] = 10 <= 10 → A maximum of 4 children can be satisfied

Output: 4

Complexity

• Time complexity: \(O(N \log N)\) (sorting and binary search)
• Space complexity: \(O(N)\) (prefix sum array)

Implementation Notes

• By precomputing prefix sums, range sums can be obtained efficiently.

• The binary search range is from 0 to N.

• In Python, using sys.stdin.read allows for fast reading of large inputs.

  Source Code

import sys
import heapq

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    P = int(data[1])
    S = list(map(int, data[2:]))

    # 昇順にソート
    S.sort()
    
    # 累積和を計算
    cumsum = [0] * (N + 1)
    for i in range(N):
        cumsum[i + 1] = cumsum[i] + S[i]
    
    # 満足できる最大人数を二分探索
    left, right = 0, N
    answer = 0
    while left <= right:
        mid = (left + right) // 2
        if cumsum[mid] <= P:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
    
    print(answer)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.