Overview

This is a problem where we count how many times each exercise can be chosen, and determine whether a total of \(M\) training sessions are possible.

Analysis

In one training session, the remaining count of the chosen exercise decreases by exactly \(K\), so the number of times exercise \(i\) can be chosen is: - It can only be chosen while \(A_i \ge K\) - Each time it is chosen, the count decreases by \(K\)

Therefore, the maximum number of times is [ \left\lfloor \frac{A_i}{K} \right\rfloor ]

The key insight here is that regardless of the order in which exercises are chosen, the “total number of possible training sessions” does not change. This is because each exercise independently has its upper limit determined solely by “how many times \(K\) can be subtracted.”

A naive approach of “simulating one day at a time for \(M\) days” would require up to \(10^9\) operations in the worst case since \(M \le 10^9\), which would not finish in time (causing TLE).

Instead, we simply compute \(\left\lfloor A_i/K \right\rfloor\) for each \(i\), sum them up, and check whether the total is at least \(M\).

For example, when \(K=3,\ A=[7,2,8]\): - \(7//3=2\) times - \(2//3=0\) times - \(8//3=2\) times

The total is \(4\) times, so if \(M \le 4\), the answer is Yes.

Algorithm

1. Read \(N, M, K\) and the array \(A\) as input.
2. Initialize a counter cnt=0.
3. For each \(a \in A\), perform cnt += a // K (add the number of times that exercise can be performed).
4. If cnt >= M at any point, output Yes and terminate (early termination).
5. If cnt < M after processing all elements, output No.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (excluding the input array; \(O(N)\) if the array is stored)

Implementation Notes

• Since the number of possible times is always an integer, we use a // K (floor division).

• Once cnt reaches \(M\), there is no need for further computation, so early termination improves speed.

• \(A_i, K, M\) can be up to \(10^9\), and the total sum can be as large as \(N \times 10^9\). Since Python integers do not overflow, we can safely perform the addition.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    cnt = 0
    for a in A:
        cnt += a // K
        if cnt >= M:
            print("Yes")
            return
    print("No")

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.