Overview

A problem to determine whether it is possible to distribute sweets to \(N\) members, selecting at most 1 of each type from \(M\) types of sweets, so that each person receives exactly \(K\) sweets.

Analysis

In this problem, we need to distribute \(K\) sweets to each member. However, each person can receive at most 1 sweet of the same type, and each type of sweet has an upper limit \(C_i\).

Naive Approach

For example, one might consider exploring combinations of sweets available for each member, or applying flow-based graph algorithms. However, since the constraints are very large (\(N\) can be up to \(10^9\)), such approaches cannot solve the problem within the time limit.

Key Observation

The key insight is to think about “how many people can each type of sweet be distributed to at most?” The \(i\)-th sweet has \(C_i\) pieces, and since each person can receive at most 1, we can consider that “it can be distributed to at most \(\min(C_i, N)\) people.” This is an intuitive upper bound: if the number of people \(N\) is small, sweets may be left over, and conversely, if there are few sweets, they cannot cover all people.

Furthermore, the total number of sweets needed is \(N \times K\) (\(K\) per person × \(N\) people). Therefore, if the sum of the “upper limit on the number of people each sweet can be distributed to” is at least \(N \times K\), the condition can be satisfied.

Correctness of the Solution

This greedy approach works because, due to the constraint that each sweet can be given to a person at most once, each type of sweet can be treated independently. Also, by considering sweets in decreasing order of quantity, we can maximize the possibility of distributing to as many people as possible.

Algorithm

1. Sort the quantities \(C_i\) of each sweet in descending order (this is not actually necessary for correctness, but makes the approach more intuitive).
2. For each sweet \(i\), consider that it can be distributed to at most \(\min(C_i, N)\) people, and accumulate the total.
3. If the total reaches \(N \times K\), output Yes and terminate. If the total is still insufficient after checking all sweets, output No.

Complexity

• Time complexity: \(O(M)\)
• Space complexity: \(O(1)\) (excluding input)

※ If sorting is performed, the time complexity becomes \(O(M \log M)\), but it is not actually necessary.

Implementation Notes

• The distribution upper limit for each sweet is \(\min(C_i, N)\).

• Since we can terminate early once the total exceeds \(N \times K\), the solution runs efficiently even for large inputs.

• In Python, using sys.stdin.read() instead of input() allows for faster reading of large amounts of input.

  Source Code

import sys
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    C = list(map(int, data[3:3+M]))
    
    # 各お菓子の個数を降順にソートする
    C.sort(reverse=True)
    
    # 最大ヒープを用意する（Pythonでは最小ヒープなので負にして使う）
    # 各メンバーが持てる残りの必要なお菓子の数を管理する
    # 初期状態では、各メンバーがK個持つ必要がある
    # しかし、N人がそれぞれK個必要なので、合計 N*K 個が必要
    # それぞれの種類のお菓子を最大何人に配れるかを考える
    
    # 貪欲法：多い順にお菓子を見て、各お菓子を最大限配る
    # 各お菓子 i は C[i] 個あるので、最大 C[i] 人に配れる（1人1個まで）
    # 全体で N 人の人に K 個ずつ配る必要がある → 合計 N*K 個必要
    
    # 各お菓子を最大 min(C[i], N) 人に配ることができる（1人につき1個まで）
    # しかし、より正確には、今持っている最も需要の高い（残り少ない）人に優先的に配るべき
    
    # より効率的な方法：
    # 各お菓子 i について、最大 min(C[i], N) 人に配れる
    # つまり、合計で sum(min(C[i], N) for i in range(M)) 個配れる
    # これが N*K 以上であれば OK
    
    total = 0
    for c in C:
        total += min(c, N)
        if total >= N * K:
            print("Yes")
            return
    print("No")

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.