Overview

This problem requires calculating the “difference between selling price and preparation cost” for each product, and finding the total when selecting only the products that yield a positive profit.

Analysis

The profit formula when selecting a set of products \(S\) can be transformed as follows:

\[\text{profit} = \sum_{i \in S} A_i - \sum_{i \in S} B_i = \sum_{i \in S} (A_i - B_i)\]

From this formula, we can see that selecting the \(i\)-th product adds \((A_i - B_i)\) yen to the overall profit. Takahashi can decide whether to select or not select each product completely independently. Therefore, to maximize the overall profit, he should select all products whose individual profit is positive (i.e., \(A_i - B_i > 0\)) and not select any product that would result in a negative contribution.

For example, suppose there are the following 3 products: - Product 1: \(A_1 = 100, B_1 = 30 \implies\) profit is \(100 - 30 = 70\) yen - Product 2: \(A_2 = 50, B_2 = 80 \implies\) profit is \(50 - 80 = -30\) yen - Product 3: \(A_3 = 200, B_3 = 150 \implies\) profit is \(200 - 150 = 50\) yen

In this case, selecting products 1 and 3 gives a profit of \(70 + 50 = 120\) yen, which is the maximum.

If we were to try a naive brute-force search over all possible selections (\(2^N\) possibilities), under the constraint \(N \le 2 \times 10^5\), the number of computations would become astronomically large, resulting in a Time Limit Exceeded (TLE). However, by evaluating each product independently as described above, only one computation per product is needed, allowing us to find the answer efficiently.

Algorithm

1. Initialize a variable to track the total profit to \(0\).
2. For each product \(i\) (\(1 \leq i \leq N\)), calculate the individual profit \(A_i - B_i\).
3. If that value is greater than \(0\), add it to the total profit. In mathematical terms, we add \(\max(0, A_i - B_i)\) for each product.
4. The total after checking all products is the maximum profit we seek.

Complexity

• Time complexity: \(O(N)\)
  • We only perform one subtraction and one comparison (\(\max\) computation) per product, so the processing finishes in time proportional to the number of products \(N\).
• Space complexity: \(O(N)\)
  • Memory is used to read the input data all at once and store it as an array (list).

Implementation Notes

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), in Python it is better to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly, which reduces execution time.

• Concise code: In Python, combining sum() with a generator expression allows the loop processing to be written concisely in a single line.

• Overflow considerations: The total profit can be at most \(N \times \max(A_i) \approx 2 \times 10^{14}\), which exceeds the 32-bit integer limit (approximately \(2 \times 10^9\)). Python automatically handles this as arbitrary-precision integers, so there is no issue. However, when implementing in other languages such as C++, you need to use a 64-bit integer type (such as long long) for the variable storing the answer.

  Source Code

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    ans = sum(max(0, int(data[i]) - int(data[i+1])) for i in range(1, 2 * N, 2))
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.