Overview

In a test with \(N\) subjects, Takahashi rewrites his score for exactly 1 subject (to a value between \(0\) and the maximum possible score), and we want to maximize the difference in total scores between Takahashi and Aoki (Takahashi - Aoki).

Analysis

Let \(S_A\) be Takahashi’s current total score and \(S_B\) be Aoki’s current total score. The current score difference is \(S_A - S_B\).

Now, suppose Takahashi changes his score for subject \(i\) from \(A_i\) to \(x\) (\(0 \leq x \leq P_i\)). The new total score difference becomes: $\(\text{(new difference)} = (S_A - A_i + x) - S_B = (S_A - S_B) + (x - A_i)\)$

To maximize this value, the following two points are important:

1. What value should the score be changed to? In the expression \((S_A - S_B) + (x - A_i)\), the values we can change are \(x\) and \(i\). First, fixing \(i\), we can see that making \(x\) as large as possible maximizes this value. Since the maximum value of \(x\) is the perfect score \(P_i\) for that subject, setting \(x = P_i\) is optimal. In this case, the resulting difference is \((S_A - S_B) + (P_i - A_i)\).

2. Which subject should be chosen? For all subjects \(i\), compute \(P_i - A_i\) (the score increase when rewriting that subject to the perfect score), and choose the subject with the maximum value. This maximizes the overall difference.

Even if \(P_i - A_i\) is \(0\) for all subjects (i.e., all subjects already have perfect scores), the condition “the maximum possible value after the change” from the problem statement can still be satisfied.

Algorithm

1. Compute Takahashi’s current total score \(S_A = \sum A_i\) and Aoki’s total score \(S_B = \sum B_i\).
2. For each subject \(i = 1, \dots, N\), compute the potential gain \(G_i = P_i - A_i\).
3. Find the maximum value \(max\_gain\) among all \(G_i\).
4. Output \((S_A - S_B) + max\_gain\).

Complexity

• Time complexity: \(O(N)\)
  • Computing the total scores takes \(O(N)\), and finding the maximum takes \(O(N)\). Since \(N \leq 2 \times 10^5\), this runs sufficiently fast.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the scores for each subject.

Implementation Notes

• In Python, using sys.stdin.read().split() to read all input at once allows faster processing when the data volume is large.

• Using the built-in functions sum() for computing the total and max() for finding the maximum allows for a concise and efficient implementation.

• In this code, max_gain is updated inside a loop, but it is also possible to use a generator expression such as max(p[i] - a[i] for i in range(n)).

  Source Code

import sys

def solve():
    # 標準入力から全てのデータを読み込み、空白で分割してリストにする
    data = sys.stdin.read().split()
    if not data:
        return
    
    # 科目数 N を取得
    n = int(data[0])
    
    # 各科目の満点 P_i、高橋君の得点 A_i、青木君の得点 B_i をリストとして取得
    # スライスと map を用いて効率的に整数に変換する
    p = list(map(int, data[1 : n + 1]))
    a = list(map(int, data[n + 1 : 2 * n + 1]))
    b = list(map(int, data[2 * n + 1 : 3 * n + 1]))
    
    # 現時点での合計得点の差（高橋君の合計 - 青木君の合計）を計算
    # sum() 関数は Python において高速に動作する
    current_diff = sum(a) - sum(b)
    
    # 高橋君はちょうど 1 科目 i を選び、その得点 A_i を 0 以上 P_i 以下の整数 x に変更できる。
    # 合計得点の差を最大化するためには、選んだ科目 i の得点を満点 P_i に変更するのが最善。
    # このとき、合計得点の差は (元の差) + (P_i - A_i) となる。
    # したがって、P_i - A_i が最大となる科目を選べばよい。
    
    max_gain = 0
    for i in range(n):
        gain = p[i] - a[i]
        if gain > max_gain:
            max_gain = gain
            
    # 元の差に最大の増加量を加えたものが答え
    print(current_diff + max_gain)

if __name__ == '__main__':
    solve()

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