Overview

This is a problem to determine whether \(N\) drivers (each with a carrying capacity limit of \(K\)) can deliver all \(\sum A_i\) packages across a total of \(M\) destinations.

Analysis

The key point of this problem is the rule that “packages can be freely split on a per-item basis and assigned to drivers.”

Specifically, the following conditions are allowed: - Packages for the same destination can be split among multiple drivers. - A single driver can carry a combination of packages from different destinations.

If the condition were “packages cannot be split (all packages for one destination must be carried by a single driver),” this would become an extremely difficult problem known as the “bin packing problem.” However, since packages can be split up and carried individually in this problem, there is no need to consider complex combinations.

The total capacity that all drivers can carry is \(N \times K\) packages. On the other hand, the total number of packages that need to be delivered is \(A_1 + A_2 + \dots + A_M\). Since packages can be freely distributed, “the total number of packages being less than or equal to the total capacity of all drivers” is the necessary and sufficient condition for all packages to be deliverable.

Algorithm

1. Calculate the total number of packages \(S = \sum_{i=1}^{M} A_i\).
2. Calculate the total driver capacity \(C = N \times K\).
3. If \(S \le C\), output Yes; otherwise, output No.

Complexity

• Time complexity: \(O(M)\)
  • A single pass through the list is needed to compute the sum of package counts \(A_i\).
• Space complexity: \(O(M)\)
  • Memory is used to store the \(M\) input package data values.

Implementation Notes

• Handling large numbers: \(N, K, A_i\) can be up to \(10^9\), and their sums and products can reach the order of \(10^{18}\). Python natively supports arbitrary-precision integers (big integers), so calculations can be performed without worrying about overflow.

• Fast input: Since \(M\) can be as large as \(10^5\), which is relatively large, using methods like sys.stdin.read().split() to read all input at once can reduce execution time.

  Source Code

import sys

def solve():
    # Read all input at once and split it into tokens based on whitespace.
    # This is efficient for the given constraints (M up to 10^5).
    input_data = sys.stdin.read().split()
    
    # Check if we have at least the initial parameters N, M, and K.
    if len(input_data) < 3:
        return
    
    # N: Number of drivers
    # M: Number of destinations
    # K: Maximum number of items each driver can carry
    n = int(input_data[0])
    m = int(input_data[1])
    k = int(input_data[2])
    
    # Each destination i requires A_i items.
    # The problem states that items for the same destination can be split
    # among multiple drivers and that each driver can carry items for
    # multiple destinations. The only constraint is that each driver
    # can carry at most K items in total, and items are discrete units.
    
    # Calculate the total number of items to be delivered by summing all A_i.
    # The A_i values are the remaining tokens from index 3 to 3+m-1.
    # Python's sum and map functions are optimized for this kind of operation.
    total_items = sum(map(int, input_data[3:3+m]))
    
    # Calculate the total capacity of all N drivers combined.
    # Python handles large integers (up to 10^18 in this case) automatically.
    total_capacity = n * k
    
    # Since any item can be assigned to any driver as long as their capacity 
    # of K is not exceeded, the condition for success is simply that the 
    # total number of items does not exceed the total combined capacity.
    if total_items <= total_capacity:
        print("Yes")
    else:
        print("No")

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.