Overview

Given \(N\) packages to be divided among \(M\) trucks as contiguous segments, the problem asks whether the value \(S\)—the minimized maximum load (sum of each segment) across all trucks—is greater than \(K\). This can be reduced to the decision problem “Can the maximum load be kept at most \(K\)?”, which can be efficiently solved using a greedy approach.

Analysis

Rephrasing the Problem

We are asked whether \(S > K\), which is equivalent to the following question:

“Can all packages be transported using at most \(M\) trucks while keeping each truck’s load at most \(K\)?”

• If yes, then \(S \leq K\) (No)
• If no, then \(S > K\) (Yes)

Issues with a Naive Approach

If we try to enumerate all possible ways to divide the packages, there are \(\binom{N-1}{M-1}\) ways to choose the split points, which is far too many when \(N\) is up to \(10^6\).

Key Insight: Greedy is Optimal

Under the constraint “keep the maximum load at most \(K\)”, a greedy approach that packs as many packages as possible into each truck is optimal.

Specifically, we scan the packages from the beginning, adding each package to the current truck if the total does not exceed \(K\), and starting a new truck otherwise. This method minimizes the number of trucks used.

Why is greedy optimal? Leaving extra capacity in an earlier truck and pushing packages to the next truck will never reduce the number of trucks needed. Packing as much as possible into the earlier truck is always at least as good for the remaining trucks.

Algorithm

1. Initialize variable current_sum (current truck’s load) to \(0\) and trucks_needed (number of trucks required) to \(1\).
2. Scan the packages in order \(A_1, A_2, \ldots, A_N\):
   • If \(A_i > K\), a single package already exceeds \(K\), so no partition works → output Yes and terminate.
   • If current_sum \(+ A_i > K\), use a new truck: increment trucks_needed by \(1\) and set current_sum \(= A_i\).
   • Otherwise, add \(A_i\) to current_sum.
3. After scanning, if trucks_needed \(\leq M\), a partition with maximum load at most \(K\) exists, so output No; otherwise output Yes.

Worked Example

For \(N=5, M=3, K=6, A=[3, 2, 4, 1, 2]\):

Package	current_sum	Decision	trucks_needed
\(3\)	\(3\)	\(0+3 \leq 6\) → add	\(1\)
\(2\)	\(5\)	\(3+2 \leq 6\) → add	\(1\)
\(4\)	\(4\)	\(5+4 > 6\) → new truck	\(2\)
\(1\)	\(5\)	\(4+1 \leq 6\) → add	\(2\)
\(2\)	\(7\)	\(5+2 > 6\) → new truck	\(3\)

Since \(3 \leq 3\), output No (partition: \([3,2],[4,1],[2]\); maximum load \(5 \leq 6\)).

Complexity

• Time complexity: \(O(N)\) (single pass through the packages)
• Space complexity: \(O(N)\) (storing the array \(A\))

Implementation Notes

• Handling a single package exceeding \(K\): If even one \(A_i > K\), the truck containing that package will always exceed \(K\), so we must immediately return Yes. Forgetting this check leads to wrong answers.

• \(K\) can be as large as \(10^{15}\), so while this is not an issue in Python, languages like C++ require long long.

• This problem is essentially the decision subroutine extracted from the classic “binary search + greedy check” problem that finds \(S\) itself, making it an excellent stepping stone toward understanding the binary search component.

  Source Code

def solve():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Check if we can split into M groups with max sum <= K
    # Greedy: pack as many items as possible into each truck without exceeding K
    current_sum = 0
    trucks_needed = 1
    for a in A:
        if a > K:
            print("Yes")
            return
        if current_sum + a > K:
            trucks_needed += 1
            current_sum = a
        else:
            current_sum += a
    
    if trucks_needed <= M:
        print("No")
    else:
        print("Yes")

solve()

---

This editorial was generated by claude4.6opus-thinking.