Overview

This is a problem where you select some items from \(N\) products to sell and maximize the profit (total selling price − total preparation cost). It is a fundamental greedy algorithm problem where you can independently decide “to sell or not to sell” for each product.

Analysis

Key Insight: Each product can be judged independently

Let’s look at the profit formula.

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

As shown, the profit can be decomposed into the sum of the difference \(A_i - B_i\) for each individual product.

In other words, whether or not to sell a product \(i\) has absolutely no effect on the choice of other products. Each product can be judged independently.

Decision criteria for each product

For product \(i\): - If \(A_i - B_i > 0\) (selling price > preparation cost), selling it adds positive profit → should sell - If \(A_i - B_i \leq 0\) (selling price ≤ preparation cost), selling it adds zero or negative profit → should not sell

Concrete Example

For example, suppose \(N = 3\) with the following products:

Product	\(A_i\) (selling price)	\(B_i\) (preparation cost)	\(A_i - B_i\)	Decision
1	100	30	+70	Sell ✅
2	50	80	−30	Don’t sell ❌
3	200	150	+50	Sell ✅

Selling products 1 and 3, the profit is \(70 + 50 = 120\) yen.

Comparison with the Naive Approach

A method that tries all combinations of products requires examining \(2^N\) cases, which is far too slow for \(N = 2 \times 10^5\). However, from the analysis above, since each product can be judged independently, the problem can be solved with a single loop of \(N\) iterations.

Algorithm

1. Initialize the total profit ans to \(0\).
2. For each product \(i\), if \(A_i > B_i\), add \(A_i - B_i\) to ans.
3. Output the final value of ans.

(If no product satisfies \(A_i > B_i\), ans remains \(0\), which is consistent with the condition that “the profit when selecting no products is \(0\) yen”.)

Complexity

• Time complexity: \(O(N)\) — each product is examined exactly once
• Space complexity: \(O(1)\) — only a variable to hold the running total is needed (no need to store the input)

Implementation Notes

• Since \(A_i, B_i\) can each be up to \(10^9\), the total can be as large as \(N \times 10^9 = 2 \times 10^{14}\). In C++ and similar languages, you need to use long long, but in Python there is no need to worry about integer overflow.

• There is no need to store the product information in an array; it is sufficient to read the input and perform the check and addition on the fly.

  Source Code

N = int(input())
ans = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a > b:
        ans += a - b
print(ans)

---

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