Overview

This is a problem where we divide items into M trucks while preserving their order, and determine whether the minimum possible value of the maximum load S is greater than K.

Analysis

If we try to exhaustively search all ways to divide the items, the computational complexity explodes. The key observation is that binary search can be applied to the value of S. When we fix a candidate value X for S, we can use a greedy method to check “whether all items can be transported using at most M trucks while keeping each truck’s load at most X.” By performing binary search using this check function, we can efficiently find S.

Algorithm

1. Use binary search to find S (the minimum possible value of the maximum load)
2. The lower bound of the search range is the maximum weight among all items (the case where only one item fits per truck), and the upper bound is a sufficiently large value
3. For each candidate value mid, execute the check function:
   • Load items onto trucks from the beginning in order, greedily adding items as long as the load does not exceed mid
   • If it would exceed mid, use a new truck
   • Return True if all items can be transported within M trucks, False otherwise
4. Compare the obtained S with K, and output “Yes” if S > K, otherwise output “No”

Complexity

• Time complexity: \(O(N \log(\sum A_i))\)
  • The number of binary search iterations is \(O(\log(\sum A_i))\)
  • Each iteration takes \(O(N)\) time for the greedy check
• Space complexity: \(O(N)\)
  • Only an array to store the weights of items is used

Implementation Notes

• Setting initial values for binary search: the lower bound is the maximum weight among all items, and the upper bound is a sufficiently large value (\(10^{18}\))

• In the greedy check, sequentially determine whether the current truck’s load would exceed the limit

• Optimize by immediately returning False as soon as the number of trucks used exceeds M

• Be careful of integer overflow (K and loads can be as large as \(10^{15}\))

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    A = list(map(int, data[3:3+N]))
    
    left = max(A)
    right = 10**18
    
    def check(limit):
        count = 1
        current = 0
        for a in A:
            if current + a <= limit:
                current += a
            else:
                count += 1
                current = a
                if count > M:
                    return False
        return True
    
    low = left
    high = right
    while low < high:
        mid = (low + high) // 2
        if check(mid):
            high = mid
        else:
            low = mid + 1
    S = low
    
    if S > K:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.