Overview

Given the selling price and preparation cost of each product, this problem asks us to maximize profit by selecting only the products whose profit is positive.

Analysis

The profit of each product \(i\) can be calculated as \(A_i - B_i\). Products with positive profit increase the overall profit when sold, while selling products with negative profit would decrease the overall profit. Therefore, the optimal strategy is to select and sell only the products with positive profit.

A naive approach would be to try all combinations of products, but since \(N\) can be as large as \(2 \times 10^5\), trying all \(2^N\) combinations is not practical. However, the key insight is that the selection of each product is independent and the profit calculation is additive, which means we can evaluate each product individually.

Algorithm

1. For each product, calculate the profit as \(A_i - B_i\)
2. Select only the products with positive profit and compute the sum of their profits
3. Output the total profit

This algorithm uses a greedy approach where products with positive profit are always included and products with negative profit are always excluded. Since the selection of each product does not affect the others, this simple method yields the optimal solution.

Complexity

• Time complexity: \(O(N)\)
  • Because we perform constant-time computation for each of the \(N\) products
• Space complexity: \(O(N)\)
  • Because we need an array to store the product data

Implementation Notes

• Input reading is optimized by reading all input at once using sys.stdin.read

• The profit of each product is calculated sequentially within the loop, and only positive values are added to the total sum

• Since the profit is 0 yen when no products are selected, no special handling is needed

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    A = []
    B = []
    index = 1
    for i in range(n):
        a = int(data[index])
        b = int(data[index+1])
        index += 2
        A.append(a)
        B.append(b)
    
    total_profit = 0
    for i in range(n):
        profit = A[i] - B[i]
        if profit > 0:
            total_profit += profit
            
    print(total_profit)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.