Popust
레이팅 미적용의견: 0
\(2^{nd}\) round, November \(10^{th}\), 2012
Mirko is hungry as a bear, scratch that, programmer and has stumbled upon a local restaurant. The
restaurant offers N meals and has an interesting pricing policy: each meal i has two assigned prices, A_{i}
and B_{i}. Mirko pays A only for the first ordered meal, while B prices apply for all other meals.
Mikro can't decide how many meals to order. In order to make his decision easier, he has asked you to
compute, for each k between 1 i N (inclusive), the minimum total price for k ordered meals. Mirko
doesn't care which particular meals he orders or in which order he orders them, however he won't
order the same meal twice. Order, order, order.
The first line of input contains the positive integer N (\(2 \le N \le 500\,000\)), the number of different
meals offered by the restaurant.
Each of the following N lines contains two positive integers, A_{i}and B_{i} (\(1 \le A_{i}\), \(B_{i} \le 1\,000\,000\,000\)), the
prices for meal i as described above.
Output must consist of N lines, where line k contains the minimum price for ordering exactly k
different meals.
3
10 5
9 3
10 59
13
182
100 1
1 1001
25
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 10000000001000000000
2000000000
3000000000
4000000000
5000000000Clarification of the first example:
k = 1: Mirko pays A2 = 9 for the starting meal 2.
k = 2: Mirko pays A1 = 10 for the starting meal 1, then B2 = 3 for meal 2.
k = 3: Mirko pays A1 = 10 for the starting meal 1, then B2 = 3 for meal 2, and finally B3 = 5 for meal 3.
평가 및 의견
Popust
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Popust