Overview

This problem asks you to calculate the total shortfall from the target score across all subjects, and determine whether that total is within the available number of additional assignments \(M\).

Analysis

Key Insight

The key point of this problem is to think about the efficient use of additional assignments.

Each additional assignment can raise any one subject’s score by 1 point. To achieve the goal, we only need to raise subjects that haven’t reached the target score \(T\) up to \(T\) points.

Concrete Example

For example, consider the case where \(N = 3\), \(M = 10\), \(T = 70\), and the scores are \([65, 80, 60]\).

• Subject 1: \(65\) points → Need \(70 - 65 = 5\) points to reach \(70\) points
• Subject 2: \(80\) points → Already \(70\) points or above, so no additional points needed (\(0\) points)
• Subject 3: \(60\) points → Need \(70 - 60 = 10\) points to reach \(70\) points

The total number of additional assignments needed is \(5 + 0 + 10 = 15\).

Since \(M = 10\), we have \(15 > 10\), so achieving the goal is impossible. The answer is -1.

Why a Simple Approach Works

This problem doesn’t require complex algorithms. The reasons are as follows:

1. The additional points needed for each subject can be calculated independently
2. There’s no need to consider priority in distributing additional assignments (since all shortfalls must be filled)
3. Simply summing up the shortfalls gives us the minimum number needed

Algorithm

1. For each subject \(i\), calculate the difference from the target score \(T\)
   • If \(A_i < T\): shortfall is \(T - A_i\) points
   • If \(A_i \geq T\): no shortfall (\(0\) points)
2. Sum up the shortfalls across all subjects (call this total_needed)
3. Make the determination:
   • If total_needed \(\leq M\), output total_needed (the minimum number needed)
   • If total_needed \(> M\), output -1 (impossible to achieve)

Complexity

• Time complexity: \(O(N)\)
  • We look at each subject once to calculate the shortfall
• Space complexity: \(O(N)\)
  • Size of the array storing scores
  • (Can be reduced to \(O(1)\) if processing without storing the array)

Implementation Notes

1. Be careful with shortfall calculation: When \(A_i \geq T\), \(T - A_i\) becomes negative, but in that case it should be treated as \(0\). In the code, this is handled by the if a < T conditional branch.

2. Be careful about overflow: With \(N\) up to \(10^5\) and maximum shortfall of \(100\) points, the total is at most around \(10^7\). In Python, there’s no concern about integer overflow, but in other languages, int type is sufficient.

3. Finding the minimum number: This problem asks not just “whether it’s possible” but “the minimum number needed”. However, since using exactly as many additional assignments as the shortfall is optimal, the sum directly becomes the answer.

Source Code

def solve():
    N, M, T = map(int, input().split())
    A = list(map(int, input().split()))
    
    # Calculate the additional points needed for each subject to reach target T
    total_needed = 0
    for a in A:
        if a < T:
            total_needed += T - a
    
    # Determine if M additional assignments are sufficient
    if total_needed <= M:
        print(total_needed)
    else:
        print(-1)

solve()

---

This editorial was generated by claude4.5opus.