Overview

This is a problem where \(N\) items of cargo are loaded onto \(M\) trucks without changing their order, and we need to determine whether it is possible to keep the load (total weight) of every truck at most \(K\).

Analysis

The question “Can the maximum load be kept at most \(K\)?” can be rephrased as “Can all cargo be transported using at most \(M\) trucks while keeping each truck’s load at most \(K\)?”

Since the order of cargo cannot be changed, a greedy approach of processing from the beginning and “loading as many items as possible onto the same truck without exceeding a load of \(K\)” is optimal. By loading each truck to its limit, we minimize the number of trucks needed for the remaining cargo.

A naive approach of trying all possible partitions (e.g., depth-first search) would cause a combinatorial explosion in the number of partitions, which would certainly result in TLE (Time Limit Exceeded) for the constraint \(N \le 10^6\). However, using this greedy approach, we only need to examine each item once from the beginning, allowing us to solve the problem efficiently.

Also, as an important edge case, if a single item’s weight exceeds \(K\), then no matter how we partition the cargo, the load will exceed \(K\), so we can immediately determine that it is impossible.

Algorithm

1. Initialize a variable count representing the number of trucks needed to \(1\), and the current truck’s load current_sum to \(0\).
2. Examine the weight \(A_i\) of each item sequentially from the beginning.
3. If \(A_i > K\), it is definitively impossible at that point, so output Yes and terminate.
4. If current_sum + A_i > K, the current truck can no longer hold more cargo. Therefore, prepare a new truck (increment count by \(1\)) and set current_sum = A_i as the first item on that truck.
5. Otherwise, the item can be loaded onto the current truck, so add \(A_i\) to current_sum.
6. After examining all items, if the number of trucks used count is greater than \(M\), output Yes (impossible); if it is at most \(M\), output No (possible).

Complexity

• Time complexity: \(O(N)\) Since we only perform one comparison and one addition per item, the processing completes in time proportional to the number of items \(N\).
• Space complexity: \(O(N)\) Since we store the input data as a list all at once, memory usage is proportional to \(N\).

Implementation Notes

• Be careful with Yes / No output: According to the problem statement, output Yes if “the maximum load exceeds \(K\) (impossible)” and No if “the load can be kept at most \(K\) (possible)”. This is easy to mix up since it is counterintuitive to the notions of possible and impossible, so make sure to get the output mapping correct.

• Fast input: Since the input size can be as large as \(N = 10^6\), in Python, instead of calling input() in a loop, use sys.stdin.read().split() to read all input at once, preventing TLE caused by I/O overhead.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    M = int(input_data[1])
    K = int(input_data[2])
    
    count = 1
    current_sum = 0
    
    for s in input_data[3:]:
        a = int(s)
        if a > K:
            print("Yes")
            return
        current_sum += a
        if current_sum > K:
            count += 1
            current_sum = a

    if count > M:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.