Overview

This is a problem where you determine whether \(N\) drivers (each capable of carrying at most \(K\) packages) can deliver all packages to \(M\) destinations. Since packages to the same destination can be split among multiple drivers, it can be solved by simply comparing the total number of packages to the total capacity.

Analysis

Key Insight: Packages Can Be Freely Split

The most important point of this problem is the condition that packages to the same destination can be split among multiple drivers.

For example, if \(K = 5\) (each driver can carry at most 5) and a destination has 12 packages, they can be split as: Driver A carries 5, Driver B carries 5, and Driver C carries 2.

Why This Doesn’t Become a Bin Packing Problem

If there were a constraint that “all packages for a single destination must be carried by a single driver,” this would become a bin packing problem (NP-hard). However, this problem has no such constraint.

Since packages can be freely split in integer units and assigned to drivers, it is possible to fill each driver’s capacity of \(K\) without any gaps.

Verification with a Concrete Example

• \(N = 3\), \(K = 5\) (total capacity \(15\)), \(A = [7, 4, 3]\) (total packages \(14\))
  • Driver 1: 5 from destination 1 → 5 packages
  • Driver 2: 2 from destination 1 + 3 from destination 2 → 5 packages
  • Driver 3: 1 from destination 2 + 3 from destination 3 → 4 packages
  • Total packages \(14 \leq 15\), so Yes

As shown, when splitting is allowed, packages can be packed without gaps, so the判定 condition is simply total number of packages ≤ total driver capacity.

Decision Condition

\[\sum_{i=1}^{M} A_i \leq N \times K\]

If this holds, output Yes; otherwise, output No.

Algorithm

1. Read \(N\), \(M\), \(K\)
2. Read \(A_1, A_2, \ldots, A_M\) and compute the total \(\text{total} = \sum A_i\)
3. If \(\text{total} \leq N \times K\), output Yes; otherwise, output No

Complexity

• Time complexity: \(O(M)\) (just computing the sum of \(A_i\))
• Space complexity: \(O(M)\) (for storing array \(A\); can be reduced to \(O(1)\) by accumulating on the fly)

Implementation Notes

• \(N\) and \(K\) can each be up to \(10^9\), so \(N \times K\) can reach up to \(10^{18}\). In C++ and similar languages, you need to use long long, but in Python there is no need to worry about integer overflow.

• \(\sum A_i\) can also be as large as \(M \times \max(A_i) = 10^5 \times 10^9 = 10^{14}\), so similarly, care must be taken when handling large integers (no issue in Python).

  Source Code

import math

def main():
    N, M, K = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    
    # Each A_i requires ceil(A_i / K) drivers at minimum
    # Total drivers needed is sum of ceil(A_i / K)
    # But we can also pack multiple destinations into one driver's capacity
    # 
    # Actually, since items from different destinations can share a driver,
    # the minimum number of drivers needed is:
    # max(ceil(sum(A) / K), max over i of ceil(A_i / K))
    # Wait, no. Since we can split a destination across multiple drivers,
    # the constraint is simply: sum(A) <= N * K
    # But also, each A_i <= N * K (which is implied if sum(A) <= N * K when A_i <= sum(A))
    # Actually no: A_i could be larger than N*K if N*K < A_i.
    # But if sum(A) <= N*K, then A_i <= sum(A) <= N*K, so that's fine.
    # 
    # Hmm wait, let me reconsider. Each driver can carry at most K items total.
    # We have N drivers. Total capacity is N*K.
    # Since items can be freely split (in integer units) across drivers,
    # the only constraint is sum(A) <= N * K.
    # 
    # Actually, is there a bin-packing issue? No, because items from the same
    # destination CAN be split. So each A_i can be divided into chunks that
    # fit into any driver's remaining capacity. This is essentially a 
    # continuous/divisible bin packing problem, so the answer is simply
    # whether sum(A) <= N * K.
    
    total = sum(A)
    if total <= N * K:
        print("Yes")
    else:
        print("No")

main()

---

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