Overview

This problem asks us to find the maximum value of Takahashi’s total score minus Aoki’s total score, given that Takahashi can change his score in exactly one subject.

Analysis

First, the difference in total scores without any changes can be calculated as \(base = \sum_{i=1}^{N} A_i - \sum_{i=1}^{N} B_i\). Now, consider the case where only subject \(i\) is changed. When subject \(i\) is changed, the contribution \((A_i - B_i)\) is first removed from the original difference \(base\), and the new difference \((x - B_i)\) between the new score \(x\) and Aoki’s score \(B_i\) is added. In other words, the difference after the change becomes \(base - (A_i - B_i) + (x - B_i)\). Since \(x\) is an integer between \(0\) and \(P_i\) inclusive, the maximum is achieved when \(x = P_i\), giving \(base - (A_i - B_i) + (P_i - B_i)\). Therefore, we just need to compute this value for each subject and find the maximum.

Algorithm

1. Compute the difference in total scores without any changes, \(base\).
2. For each subject \(i\), compute the maximum difference after the change: \(base - (A_i - B_i) + (P_i - B_i)\).
3. Find the maximum value among all subjects.

Complexity

• Time complexity: \(O(N)\)
  • Computing the total takes \(O(N)\), and computing the value for each subject takes \(O(N)\), so the overall complexity is \(O(N)\).
• Space complexity: \(O(N)\)
  • This is for storing the input arrays.

Implementation Notes

• The initial value of \(max\_diff\) is set to a very small value (\(-10^{18}\)). This is because the computed results could be negative.

• Since we simply evaluate the formula for each subject, the implementation is straightforward.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    P = list(map(int, data[1:1+n]))
    A = list(map(int, data[1+n:1+2*n]))
    B = list(map(int, data[1+2*n:1+3*n]))
    
    base = sum(A) - sum(B)
    
    max_diff = -10**18
    for i in range(n):
        current_diff = base - (A[i] - B[i])
        max_possible = current_diff + P[i] - B[i]
        max_diff = max(max_diff, max_possible)
    
    print(max_diff)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.