Overview

A problem where \(N\) packages are divided in order among \(M\) trucks, minimizing the maximum load across all trucks. We need to determine whether this minimum value is greater than a given value \(K\).

Analysis

This problem is a classic application of binary search for “minimizing the maximum value,” but in this case, we only need to determine whether that minimum value exceeds \(K\).

The key observation is the constraint that packages must be divided consecutively in order. In other words, you cannot skip packages or reorder them. Due to this constraint, greedy approaches like simply distributing heavy packages evenly cannot be used.

As a naive approach, if we consider trying all possible ways to divide the packages, the number of combinations is extremely large (\(\binom{N-1}{M-1}\) ways), making it impractical (TLE). However, for the decision problem “Can we distribute the packages such that each truck’s load is at most \(K\)?”, we can simulate the process from left to right.

Specifically, the optimal strategy is to greedily look at packages from left to right: if the current package can fit in the current truck, add it; otherwise, move to the next truck. This works because there is no benefit to packing later packages first — processing them in order is always optimal.

This decision is implemented as the function can_deliver_within_capacity. This function examines each package in order, checking whether the number of trucks exceeds \(M\), while also verifying that no individual package weight exceeds \(K\) (handling the case where staying within \(K\) is impossible).

Finally, based on the result of this decision, we output "No" or "Yes" as the answer.

Algorithm

1. Examine each package in order.
2. Determine whether the current package can be loaded onto the current truck:
   • If it cannot → switch to the next truck.
   • If the number of trucks exceeds \(M\), determine it is impossible.
3. If all packages can be distributed → \(S \leq K\) (output No)
4. If they cannot be distributed → \(S > K\) (output Yes)

This greedy decision simulates distributing packages such that each truck’s load does not exceed \(K\).

Complexity

• Time complexity: \(O(N)\)
  (Since constant-time operations are performed for each package)
• Space complexity: \(O(1)\)
  (No additional large memory is used aside from the input data)

Implementation Notes

• If any individual package weight exceeds \(K\), return False immediately (a division with all loads at most \(K\) is fundamentally impossible).

• If the number of trucks exceeds \(M\), return False immediately.

• If all packages have been loaded by the last truck, return True.

  Source Code

def can_deliver_within_capacity(A, M, K):
    trucks_needed = 1
    current_load = 0
    
    for weight in A:
        if weight > K:
            return False
        if current_load + weight > K:
            trucks_needed += 1
            current_load = weight
            if trucks_needed > M:
                return False
        else:
            current_load += weight
            
    return True

N, M, K = map(int, input().split())
A = list(map(int, input().split()))

if can_deliver_within_capacity(A, M, K):
    print("No")
else:
    print("Yes")

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