Overview

Takahashi wants to maximize the difference between his total score and Aoki’s total score by changing the score of exactly one subject. Let’s find this maximum difference.

Analysis

In this problem, Takahashi can change his score for exactly one subject, while all other subjects’ scores remain fixed. Aoki’s scores are also all fixed. Therefore, Takahashi’s goal is to “change exactly one subject’s score to maximize the total score difference $\((\text{Takahashi's total}) - (\text{Aoki's total})\)$.”

Choices for Each Subject

For a given subject \(i\), the range in which Takahashi can change his score is from \(0\) to \(P_i\) points. That is, changing the score for that subject to: - The minimum value \(0\) - The maximum value \(P_i\)

One of these two choices is always the most effective. This is because choosing any intermediate value cannot make the difference any larger.

Naive Approach and Its Issues

A naive approach would be to try all scores from \(0\) to \(P_i\) for every subject, but this is computationally infeasible (especially when \(P_i\) is large). However, in practice, it is sufficient to consider only the two choices of “set to minimum” or “set to maximum” for each subject.

Focusing on the Change in Difference

Let Takahashi’s original total score be \(S_A = \sum_{i=1}^{N} A_i\) and Aoki’s total score be \(S_B = \sum_{i=1}^{N} B_i\). When changing the score for subject \(i\): - If the score is changed to \(0\), the new total becomes \(S_A - A_i\), and the difference is \((S_A - A_i) - S_B\) - If the score is changed to \(P_i\), the new total becomes \(S_A - A_i + P_i\), and the difference is \((S_A - A_i + P_i) - S_B\)

It is optimal to choose the larger of these two.

The initial difference \(S_A - S_B\) is also a candidate, so the final answer is the maximum value obtained by performing the above operation over all subjects.

Algorithm

1. Compute Takahashi’s and Aoki’s total scores \(S_A\), \(S_B\).
2. Keep the initial difference \(D = S_A - S_B\).
3. For each subject \(i\), do the following:
   • Difference when changing subject \(i\)’s score to \(0\): \(D - A_i\)
   • Difference when changing subject \(i\)’s score to \(P_i\): \(D - A_i + P_i\)
   • Take the larger of these two as a candidate and update the overall maximum.
4. After examining all subjects, output the obtained maximum value.

Complexity

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

※ Since each subject can be processed in constant time, the problem can be solved in linear time.

Implementation Notes

• sys.stdin.read is used for fast input reading (in the case of Python).

• For each subject, compare the differences when changing the score to 0 or to the maximum, and update the maximum value.

• Don’t forget to also consider the initial difference as the starting value.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    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_A = sum(A)
    # 青木君の合計点（固定）
    sum_B = sum(B)
    
    max_diff = sum_A - sum_B  # 最初の差
    
    for i in range(N):
        # 高橋君がi番目の科目を0点に変更した場合の差
        diff_if_zero = (sum_A - A[i]) - sum_B
        # 高橋君がi番目の科目をP[i]点に変更した場合の差
        diff_if_max = (sum_A - A[i] + P[i]) - sum_B
        # その科目を変更することで得られる最大の差
        new_diff = max(diff_if_zero, diff_if_max)
        if new_diff > max_diff:
            max_diff = new_diff
            
    print(max_diff)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.