Overview

There are \(N\) types of exercises, each of which can be performed \(A_i\) times. In one training session, you perform exactly \(K\) repetitions of any single exercise. The problem asks whether it is possible to complete a total of \(M\) training sessions.

Key Insight

The key point of this problem is that we can independently consider “how many training sessions each exercise can contribute to.”

Given that exercise \(i\) has \(A_i\) remaining repetitions, and each training session consumes \(K\) repetitions, we can determine the maximum number of training sessions from this exercise as follows: - When \(A_i < K\): 0 sessions - When \(A_i \geq K\): \(\lfloor A_i / K \rfloor\) sessions (the quotient of \(A_i\) divided by \(K\))

For example, if \(A_i = 10, K = 3\), then \(10 \div 3 = 3\) remainder \(1\), so a maximum of 3 training sessions are possible from this exercise. The remaining 1 repetition is less than \(K\), so it cannot be used for another training session.

If Takahashi wants to perform a total of \(M\) training sessions, he can achieve his goal if the sum of “possible training sessions” across all types of exercises is at least \(M\).

Algorithm

1. Initialize a variable total_possible_sessions to \(0\) to keep track of the total possible sessions.
2. For each exercise \(i = 1, 2, \ldots, N\), repeat the following:
   • Compute the quotient of \(A_i\) divided by \(K\) (rounded down) and add it to total_possible_sessions.
3. If the final total_possible_sessions is at least \(M\), output Yes; otherwise, output No.

Complexity

• Time complexity: \(O(N)\)
  • We loop once through each of the \(N\) exercises, so the processing completes in linear time.
• Space complexity: \(O(N)\)
  • \(O(N)\) is required if the values \(A_i\) are stored in a list or similar structure. If the input is read and processed one at a time, this can be reduced to \(O(1)\).

Implementation Notes

• Handling large numbers: The values of \(M, K, A_i\) can be as large as \(10^9\), but in languages like Python, arbitrary-precision integers are supported natively, so there is no need to worry about overflow.

• Integer division: When computing \(A_i / K\), we need the integer quotient (floor division). In Python, this can be concisely written using the // operator.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 1行目の N, M, K を取得します
    # N: エクササイズの種類数
    # M: トレーニングを行いたい日数
    # K: 1回のトレーニングで減る回数
    n = int(input_data[0])
    m = int(input_data[1])
    k = int(input_data[2])
    
    # 2行目の A_1, A_2, ..., A_N を順番に処理します
    # 各エクササイズ i について、最大で floor(A_i / K) 回のトレーニングが可能です
    total_possible_sessions = 0
    for i in range(n):
        # A_i は input_data のインデックス 3 以降に格納されています
        a_i = int(input_data[3 + i])
        total_possible_sessions += a_i // k
        
    # 合計の可能回数が M 回以上であれば、M 日間トレーニングを続けることができます
    if total_possible_sessions >= m:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    solve()

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