Overview

We split the list of packages into exactly \(M\) contiguous intervals while preserving order, and determine whether the minimum possible value \(S\) of the “maximum interval sum” exceeds \(K\) (i.e., whether \(S > K\)).

Analysis

Key Insight

We rephrase this as the decision problem: “Can we make the maximum load at most \(K\)?”

• If there exists some partition where every truck’s load (interval sum) is at most \(K\) \(\Rightarrow S \le K\) (answer is No)
• If for every partition, some truck exceeds \(K\) \(\Rightarrow S > K\) (answer is Yes)

Furthermore, the condition requires “exactly \(M\) trucks,” but since \(A_i \ge 1\) (positive weights):

• If a partition with all loads at most \(K\) can be made with \(M\) or fewer parts, then we can split intervals further to increase the count (while maintaining contiguity), which only decreases each interval sum, so we can also achieve exactly \(M\) parts.

Therefore, “exactly \(M\) parts” can be replaced with:

Is the minimum number of trucks needed to keep all loads at most \(K\) less than or equal to \(M\)?

Why Brute Force Doesn’t Work

The number of ways to choose partition points is \(\binom{N-1}{M-1}\), selecting \(M-1\) positions from \(N-1\) possible ones, which explodes combinatorially. This is infeasible for \(N \le 10^6\).

Solution Approach

The minimum number of trucks needed to keep the maximum load at most \(K\) can be found with a greedy algorithm that packs items from left to right as much as possible.

• If adding the next package to the current truck keeps the sum at most \(K\), load it
• Otherwise, start a new truck

This method maximizes the load on each truck, thereby minimizing the number of trucks.

Additionally, if any package has \(A_i > K\), then even that single package alone exceeds \(K\), so it’s immediately impossible (\(S > K\)).

Algorithm

1. Read input.
2. If any package satisfies \(A_i > K\), output Yes and terminate.
3. Start with cnt=1 (number of trucks used) and s=0 (current truck’s load).
4. Process packages from left to right:
   • If \(s + A_i \le K\), then s += A_i
   • Otherwise, switch to a new truck: cnt += 1, s = A_i
5. At the end, if cnt <= M, then \(S \le K\) so output No; otherwise output Yes.

Example

For \(A=[4,2,3,4]\), \(M=2\), \(K=6\): - Truck 1: \(4+2=6\) (packed to the limit) - Next item \(3\) doesn’t fit, so start truck 2: \(3\) - Next item \(4\) gives \(3+4=7\) which exceeds \(K\), so a 3rd truck is needed Therefore the minimum number of trucks is cnt=3. Since \(3 > M(=2)\), the answer is Yes (\(S>K\)).

Complexity

• Time complexity: \(O(N)\) (single pass)
• Space complexity: \(O(1)\) (can process sequentially without storing the array)

Implementation Notes

• Since \(N \le 10^6\), fast input is important in Python. The code uses sys.stdin.buffer.read() to parse integers for speedup.

• Sums and \(K\) can reach up to around \(10^{15}\), but using Python’s integers, which don’t overflow, keeps things safe.

• The fact that when cnt <= M we can achieve “exactly \(M\) trucks” relies on the property that since package weights are positive, splitting intervals to increase the count never increases the maximum sum.

  Source Code

import sys

def int_iter():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        num = 0
        while i < n and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        yield num

it = int_iter()
N = next(it)
M = next(it)
K = next(it)

cnt = 1
s = 0

for _ in range(N):
    a = next(it)
    if a > K:
        print("Yes")
        sys.exit(0)
    if s + a <= K:
        s += a
    else:
        cnt += 1
        s = a

print("No" if cnt <= M else "Yes")

---

This editorial was generated by gpt-5.2-high.