Overview

Given a single rope of length \(L\), cut it at most \(K\) times (producing at most \(K+1\) pieces) and distribute pieces to students who each require length \(A_i\). Find the maximum number of students that can be served.

Analysis

The key observation is that there are two constraints:

1. Piece count constraint: Since the rope can be cut at most \(K\) times, the maximum number of pieces (= number of students that can receive a piece) is at most \(K+1\).
   Therefore, the number of students served is at most \(K+1\).

2. Total length constraint: Since we are dividing a single rope, the sum of the lengths of all distributed pieces must be at most \(L\).

Also, since student \(i\) only needs a piece of length “\(A_i\) or more,” in an optimal solution we can assume each student receives exactly \(A_i\) (giving any extra would only reduce the length available for other students, with no benefit).

To maximize the number of students, if we are going to serve the same number of students, it is optimal to prioritize students with shorter required lengths first.
If we were to select students with longer requirements first, the total would tend to be larger for the same number of pieces, potentially exceeding \(L\) and forcing us to reduce the count.

Therefore: - Sort \(A\) in ascending order - Starting from the beginning, count up to at most \(K+1\) students while the cumulative sum of required lengths does not exceed \(L\)

This gives us the answer.

Naively enumerating all subsets of students to distribute to would require checking \(2^N\) combinations, which is infeasible. DP on the length is also impossible since \(L\) can be up to \(10^9\).
The observation of “greedily picking in ascending order” solves the problem immediately.

Concrete example: - \(L=10,\ K=2\) (at most 3 pieces can be distributed) - Sorting \(A=[6,2,4,7,3]\) in ascending order gives \([2,3,4,6,7]\) - Summing from the front: \(2+3+4=9 \le 10\), so 3 students can participate. Adding the next gives \(+6\) resulting in \(15>10\), so we stop.
→ The answer is 3

Algorithm

1. Sort array \(A\) in ascending order
2. The maximum number of students that can be served due to the piece count constraint is \(limit = \min(N, K+1)\)
3. For \(i=0\) to \(limit-1\), update the cumulative sum \(s += A[i]\):
   • If \(s \le L\), update the tentative answer to \(i+1\)
   • If \(s > L\), all subsequent sums will also exceed \(L\), so break early
4. Output the resulting number of students

Complexity

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

Implementation Notes

• The number of students served is always at most \(K+1\), so the loop only needs to go up to min(N, K+1)

• The cumulative sum can reach up to approximately \(2\times 10^5 \times 10^9 = 2\times 10^{14}\), so in Python this is handled automatically, but in other languages a 64-bit integer (long long) is required

• Breaking as soon as the cumulative sum exceeds \(L\) avoids unnecessary work (since the array is sorted, all subsequent sums will also exceed \(L\))

  Source Code

import sys

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

    limit = min(N, K + 1)
    s = 0
    ans = 0
    for i in range(limit):
        s += A[i]
        if s <= L:
            ans = i + 1
        else:
            break
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.