Overview

This is a problem where you sum up how many times each exercise can be used for training, and determine whether that total is at least \(M\).

Analysis

Key Insight

In one day of training, you choose one exercise and reduce its remaining count by exactly \(K\). In other words, exercise \(i\) can be used for training at most \(\lfloor A_i / K \rfloor\) times (the quotient of \(A_i\) divided by \(K\)).

For example, when \(K = 3\): - If \(A_i = 10\), it can be used \(\lfloor 10 / 3 \rfloor = 3\) times (remaining count decreases as \(10 \to 7 \to 4 \to 1\)) - If \(A_i = 6\), it can be used \(\lfloor 6 / 3 \rfloor = 2\) times - If \(A_i = 2\), it can be used \(\lfloor 2 / 3 \rfloor = 0\) times (since it’s less than \(K\), it can never be chosen)

The order in which exercises are chosen on each day doesn’t matter

Since you simply choose one exercise each day, the order is flexible. What matters is only the total number of training sessions possible across all exercises.

You just need to check whether the sum of \(\lfloor A_i / K \rfloor\) over all exercises is sufficient for \(M\) days of training.

Why naive simulation is dangerous

Since \(M\) can be up to \(10^9\), simulating day by day would be \(O(M)\) and result in TLE. However, based on the analysis above, we can directly compute the number of times each exercise can be used via division, so simulation is unnecessary.

Algorithm

1. For each exercise \(i\), compute \(\lfloor A_i / K \rfloor\).
2. Sum all of these values and call it \(\text{total}\).
3. If \(\text{total} \geq M\), output Yes; otherwise, output No.

Concrete Example (Input: \(N=3, M=5, K=3, A=[10, 6, 2]\))

Exercise	\(A_i\)	\(\lfloor A_i / K \rfloor\)
1	10	3
2	6	2
3	2	0

Total \(= 3 + 2 + 0 = 5 \geq 5\), so the answer is Yes.

Complexity

• Time complexity: \(O(N)\) (one division per exercise, then summing them up)
• Space complexity: \(O(N)\) (storing the array \(A\))

Implementation Notes

• Since \(M\) and \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the total can be as large as approximately \(2 \times 10^{14}\). In Python, there is no need to worry about integer overflow, but when implementing in C++ or similar languages, you need to use the long long type.

• Python’s // operator performs floor division, so \(\lfloor A_i / K \rfloor\) can be computed directly.

  Source Code

N, M, K = map(int, input().split())
A = list(map(int, input().split()))

total = sum(a // K for a in A)
print("Yes" if total >= M else "No")

---

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