Minimum Cost for Restaurant Orders
Time limit2sMemory limit256 MB
Given first-dish and later-dish prices for N dishes, compute for every k the minimum total cost of ordering exactly k dishes.
- Level
Medium5 of 10
- Topics
- Greedy, Sorting, Prefix sum
- Solved
- No attempts yet
Problem
A restaurant sells N different dishes. A customer may order any number of distinct dishes, but cannot order the same dish more than once.
The order matters only for the dish chosen first. For dish i, the price is A_i if it is ordered first and B_i otherwise.
For each k from 1 to N, compute the minimum total cost to order exactly k dishes.
Input
The first line contains N, the number of dishes. (2 <= N <= 500,000)
Each of the next N lines contains two integers A_i and B_i. (0 <= A_i, B_i <= 1,000,000,000)
Output
Print N lines. The k-th line must contain the minimum total cost to order exactly k dishes.