Overview

This is a problem of determining whether it is possible to distribute \(K\) distinct types of snacks to each of the \(N\) members. The key lies in how to handle the stock quantities of snacks and the constraint that “you cannot give 2 or more of the same type to one person.”

Analysis

1. Required Total Number

First, for all members to receive \(K\) snacks each, a total of \(N \times K\) snacks are needed overall. However, simply having enough total snacks is not sufficient.

2. “Effective Upper Limit” for Each Type of Snack

The most important constraint of this problem is that “you must not give 2 or more of the same type of snack to the same member.” Since there are only \(N\) members, no matter how many snacks of a particular type \(i\) there are (e.g., \(C_i = 10^{12}\)), the maximum number of people who can receive that type of snack is \(N\).

In other words, the number of snacks of type \(i\) that can actually be distributed is as follows: - When the stock \(C_i\) is at most \(N\): all of the stock (\(C_i\) snacks) can be distributed. - When the stock \(C_i\) is greater than \(N\): the limit is distributing 1 to each of \(N\) people, so at most \(N\) can be distributed.

To summarize, the maximum number of snacks of type \(i\) that can contribute to the overall distribution is \(\min(N, C_i)\).

3. Judgment Condition

If the sum of these “effective quantities” across all types of snacks is at least the required total \(N \times K\), then it is possible to distribute \(K\) snacks to each person.

\[ \sum_{i=1}^{M} \min(N, C_i) \geq N \times K \]

When this condition holds, output Yes; otherwise, output No. *Note: The sufficiency of this condition can be proven by considering a constructive method such as “sorting snacks in descending order of stock and assigning them to each member in turn.”

Algorithm

1. Calculate the required total \(Target = N \times K\).
2. For each type of snack with quantity \(C_i\), compute \(\min(N, C_i)\) and find the total sum \(Total\).
3. If \(Total \geq Target\), output Yes; otherwise, output No.

Complexity

• Time Complexity: \(O(M)\) This is because we check each \(C_i\) in a single loop over the \(M\) types of snacks. The actual values of \(N\) or \(C_i\) do not affect the time complexity.
• Space Complexity: \(O(M)\) This is the memory required to store the input snack quantities \(C_1, \ldots, C_M\) in a list.

Implementation Notes

• Handling Large Values: \(N\) and \(C_i\) can be up to \(10^9\), and their product \(N \times K\) can be up to around \(10^{14}\). In Python, this is automatically handled as arbitrary-precision integers, but when using other languages (such as C++), you need to use 64-bit integer types like long long.

• Early Termination: If the running sum exceeds \(N \times K\) during the computation, you can break out of the loop for a slight efficiency gain (though the worst-case complexity remains \(O(M)\)).

  Source Code

import sys

def solve():
    # 入力を取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    K = int(input_data[2])
    C = list(map(int, input_data[3:]))
    
    # 判定条件: 各種類のお菓子は最大 N 人にしか配れないため、
    # i 番目のお菓子が寄与できる最大数は min(N, C_i) となる。
    # すべてのメンバーに K 個ずつ配るためには、合計で N * K 個必要。
    # したがって、 sum(min(N, C_i)) >= N * K であれば可能。
    
    total_capacity = 0
    for count in C:
        if count < N:
            total_capacity += count
        else:
            total_capacity += N
            
    if total_capacity >= N * K:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    solve()

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