Overview

This is a problem where you need to find the minimum number of “additional assignments” required to bring the scores of all \(N\) subjects to at least \(T\) points, and determine whether that number is within the upper limit of \(M\).

Analysis

The key point of this problem is that “you can consider each subject independently and simply sum up the deficiencies”.

For Takahashi to avoid supplementary lessons, he needs to satisfy \(A_i \geq T\) for all subjects \(i\). - For subjects where \(A_i \geq T\) already: no additional assignments are needed. - For subjects where \(A_i < T\): at least \(T - A_i\) additional assignments are needed to bring that subject to \(T\) points.

The total number of additional assignments needed to bring all subjects to the target score is the sum of the deficiencies for each subject. If this total does not exceed the maximum submittable number \(M\), the goal is achievable, and that total is the minimum number of assignments. Conversely, if the total exceeds \(M\), it is impossible to bring all subjects to \(T\) points or above regardless of how assignments are allocated, so we output -1.

Algorithm

The problem can be solved with the following steps:

1. Initialize a variable total_needed representing the total number of additional assignments needed to \(0\).
2. For each subject’s score \(A_i\) (\(i=1, \ldots, N\)), do the following in order:
   • If \(A_i < T\), add the deficiency \(T - A_i\) to total_needed.
   • If \(A_i \geq T\), do nothing (the value to add is \(0\)).
3. Compare the final total_needed with \(M\):
   • If total_needed <= M, output total_needed.
   • If total_needed > M, output -1.

Complexity

• Time complexity: \(O(N)\)
  • For \(N\) subjects, we check each subject’s score once, so the computation is proportional to \(N\). Since \(N \leq 10^5\), this runs sufficiently fast.
• Space complexity: \(O(N)\)
  • Memory is needed to store the \(N\) input scores in a list.

Implementation Notes

• Handling large values: \(M\) can be up to \(10^9\), and the total number of required assignments can be as large as \(N \times T = 10^5 \times 100 = 10^7\), but since Python’s integer type automatically handles arbitrary-precision integers, there is no concern about overflow.

• Reading input: Since \(N\) can be large, it is efficient to read all input at once using sys.stdin.read().split() or similar methods.

  Source Code

import sys

def solve():
    # 入力をすべて読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N, M, T を取得
    n = int(input_data[0])
    m = int(input_data[1])
    t = int(input_data[2])
    
    # 各科目の点数 A_i を取得
    a = list(map(int, input_data[3:]))
    
    # 全科目を目標点 T 以上にするために必要な追加課題の総数を計算
    total_needed = 0
    for score in a:
        if score < t:
            total_needed += (t - score)
            
    # 必要個数が M 以下であればその個数を出力、そうでなければ -1 を出力
    if total_needed <= m:
        print(total_needed)
    else:
        print("-1")

if __name__ == "__main__":
    solve()

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