Overview

This is a problem where, given the remaining counts for each exercise, we need to determine whether training (once per day) can be sustained for M days. Each training session consumes K repetitions.

Analysis

For each exercise i, consider the maximum number of times it can be used for training. If exercise i has A_i remaining repetitions, the maximum number of times this exercise can be used for training is floor(A_i/K) (up to a maximum of M times). This is because each training session consumes K repetitions, so with A_i remaining repetitions, it can only be used at most A_i // K times.

If the total number of training sessions obtainable from all exercises is at least M, then M days of training can be achieved. Conversely, if the total is less than M, it cannot be achieved.

Algorithm

1. For each exercise i, calculate the available number of training sessions: min(A_i // K, M)
2. Sum up the available counts for all exercises
3. If the total is at least M, output “Yes”; otherwise, output “No”

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• When calculating the available count for each exercise, using the min function with M as the upper bound prevents unnecessary computation

• Efficient loop processing is used to handle cases where input values are large (up to \(2 \times 10^5\) elements)

  Source Code

def main():
    import sys
    data = sys.stdin.read().split()
    n = int(data[0])
    M = int(data[1])
    K = int(data[2])
    A = list(map(int, data[3:3+n]))
    
    total_possible = 0
    for a in A:
        total_possible += min(a // K, M)
    
    if total_possible >= M:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.