Overview

This problem asks us to maximize the difference in total scores (Takahashi − Aoki) when Takahashi can retake exactly one subject and freely change his score on it.

Analysis

First, the difference in total scores without any retake can be calculated as follows:

\[\text{total\_diff} = \sum_{i=1}^{N} A_i - \sum_{i=1}^{N} B_i\]

Next, consider the case where Takahashi retakes subject \(i\). If his score on subject \(i\) is changed from \(A_i\) to a new score \(X\) (\(0 \leq X \leq P_i\)), the difference in total scores becomes:

\[\text{total\_diff} - A_i + X\]

To maximize this, we should make \(X\) as large as possible, so setting \(X = P_i\) (full marks) is optimal.

In this case, the “increase in the difference (gain)” from retaking subject \(i\) is:

\[\text{gain}_i = P_i - A_i\]

This represents “how much more can be gained on subject \(i\)”, i.e., the room for improvement.

Concrete example: When \(N = 2\), \(P = [100, 50]\), \(A = [80, 10]\), \(B = [70, 60]\):

• Difference without retake: \((80 + 10) - (70 + 60) = -40\)
• Retaking subject 1: gain \(= 100 - 80 = 20\), difference \(= -40 + 20 = -20\)
• Retaking subject 2: gain \(= 50 - 10 = 40\), difference \(= -40 + 40 = 0\)

Since subject 2 has more room for improvement, retaking subject 2 is optimal.

Key insight: We only need to select one subject with the maximum \(P_i - A_i\) among all subjects, so a brute-force search is sufficiently efficient.

Algorithm

1. Read the input.
2. Calculate the current difference in total scores: \(\text{total\_diff} = \sum A_i - \sum B_i\).
3. For each subject \(i\), calculate the gain \(P_i - A_i\) (room for improvement) and find the maximum value \(\text{best\_gain}\).
4. The answer is \(\text{total\_diff} + \text{best\_gain}\).

Complexity

• Time complexity: \(O(N)\) — Computing the totals and finding the maximum are each \(O(N)\)
• Space complexity: \(O(N)\) — Storing arrays \(P, A, B\)

Implementation Notes

• Takahashi can also lower his score, but since we want to maximize the difference, it is always optimal to score full marks. Therefore, cases where the score decreases need not be considered.

• Since \(P_i\) and score values can be up to \(10^9\) and the number of subjects can be up to \(2 \times 10^5\), the total can be as large as approximately \(2 \times 10^{14}\). In Python there is no need to worry about integer overflow, but in C++ and similar languages, long long must be used.

• The problem states that “the result of retaking may be the same score as the original”, but this corresponds to the case where \(P_i - A_i = 0\), which simply results in a gain of 0 and is handled naturally.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    P = [int(input_data[idx + i]) for i in range(N)]; idx += N
    A = [int(input_data[idx + i]) for i in range(N)]; idx += N
    B = [int(input_data[idx + i]) for i in range(N)]; idx += N
    
    total_diff = sum(A) - sum(B)
    
    # For each subject i, if Takahashi retakes it, he can change A[i] to any value in [0, P[i]].
    # The new difference = total_diff - A[i] + new_score
    # To maximize, set new_score = P[i], so gain = P[i] - A[i]
    # We want to maximize (P[i] - A[i]) over all i.
    
    best_gain = max(P[i] - A[i] for i in range(N))
    
    print(total_diff + best_gain)

main()

This editorial was generated by claude4.6opus-thinking.