Overview

Given Takahashi’s score \(X\) and the scores \(A_i\) of \(N\) students, the problem asks us to compute the difference \(A_i - X\) only for students where \(A_i > X\), and find the total sum (the total frustration).

Analysis

The “frustration” required by this problem is defined for each student \(i\) as follows: - When \(A_i > X\): \(A_i - X\) - When \(A_i \leq X\): \(0\)

Mathematically, this can also be written as \(\max(0, A_i - X)\).

Key Points

• Each student can be processed independently: Whether a student’s score is higher than Takahashi’s score does not depend on other students’ scores. Therefore, we can simply check students from \(1\) to \(N\) in order.
• Constraint check: The number of students \(N\) is at most \(5 \times 10^5\). An \(O(N)\) algorithm that processes one student at a time is well within the time limit.

Concrete Example

For example, consider the case where Takahashi scored \(50\) points (\(X=50\)) and the other students scored \([40, 60, 50, 80]\). 1. Student with \(40\) points: \(40 \leq 50\), so frustration is \(0\) 2. Student with \(60\) points: \(60 > 50\), so frustration is \(60 - 50 = 10\) 3. Student with \(50\) points: \(50 \leq 50\), so frustration is \(0\) 4. Student with \(80\) points: \(80 > 50\), so frustration is \(80 - 50 = 30\) The total is \(0 + 10 + 0 + 30 = 40\).

Algorithm

1. Initialize a variable total_regret to \(0\) to hold the total frustration.
2. Loop through the scores of the \(N\) students one by one.
3. For each score score, if score > X, add score - X to total_regret.
4. After the loop ends, output total_regret.

Complexity

• Time complexity: \(O(N)\)
  • Since we scan through \(N\) elements once, the computation finishes in time proportional to \(N\).
• Space complexity: \(O(N)\)
  • If we store the \(N\) input scores in a list, we use memory proportional to \(N\).

Implementation Notes

• Fast input: Since \(N\) can be as large as \(5 \times 10^5\), in Python we use sys.stdin.read().split() to read all input at once, reducing execution time.

• Conditional branching: By using the condition if score > x:, we can straightforwardly implement the rule from the problem statement that “computation is performed only when \(A_i > X\)”.

  Source Code

import sys

def solve():
    # 入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    x = int(input_data[1])
    a = map(int, input_data[2:])
    
    total_regret = 0
    for score in a:
        if score > x:
            total_regret += score - x
            
    print(total_regret)

if __name__ == "__main__":
    solve()

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