Overview

We want to maximize the difference between Takahashi’s total score and Aoki’s total score by changing Takahashi’s score in exactly one subject. The conclusion is that the answer is obtained by adding the “maximum increment achievable in one subject” to the “initial difference.”

Analysis

First, let the difference in total scores before any change be: \(D=\sum_i A_i-\sum_i B_i\)

If Takahashi retakes subject \(i\) and changes his score to \(A_i'\), the difference becomes: [ D’ = \left(\sum_{j\ne i} A_j + A_i’\right) - \sum_j B_j = D + (A_i’ - A_i) ] In other words, to maximize the difference, we just need to choose one subject that maximizes \((A_i' - A_i)\).

Since \(A_i'\) can be any integer from \(0\) to \(P_i\), to maximize \((A_i' - A_i)\) we should set that subject to full marks: [ \max (A_i’ - A_i) = P_i - A_i ]

Therefore, the overall answer is: - Compute the initial difference \(D\) - Find the maximum of the increments \(P_i - A_i\) across all subjects

and the answer is \(D + \max_i (P_i - A_i)\).

A naive approach of “selecting each subject and recomputing the total score from scratch each time” would take \(O(N)\) per computation, repeated \(N\) times for \(O(N^2)\) total, which is too slow for \(N\le 2\times 10^5\). By realizing through the above transformation that “we only need to look at the increment,” we can reduce this to \(O(N)\).

(Example) If \(P=[100,50], A=[60,40]\), then the increments are \([40,10]\), so the maximum increment is \(40\). The answer is the initial difference \(D\) plus \(40\).

Algorithm

1. Compute \(D=\sum_i A_i-\sum_i B_i\).
2. For each subject, compute the increment \(P_i-A_i\) and find the maximum \(best\_inc=\max_i(P_i-A_i)\).
3. Output \(D+best\_inc\).

Complexity

• Time complexity: \(O(N)\) (one pass each for the sum and the maximum)
• Space complexity: \(O(1)\) (constant aside from the input arrays; in a Python implementation, storing the arrays takes \(O(N)\))

Implementation Notes

• “Changing exactly one subject” also allows “no change,” but since \(P_i-A_i\ge 0\), the maximum increment is always non-negative, so the condition is naturally satisfied.

• The increment can be computed in a single pass, e.g., max(p - a for p, a in zip(P, A)).

• Since \(P_i\) can be large, sums and differences should be handled with int (in Python, arbitrary precision is automatic), which is safe.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    P = list(map(int, input().split()))
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    diff = sum(A) - sum(B)
    best_inc = max(p - a for p, a in zip(P, A))
    print(diff + best_inc)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.