A Greedy Problem

View as PDF

Submit solution

All submissions

Best submissions

Points: 5 (partial)

Time limit: 1.0s

Memory limit: 64M

Problem type

You are given $N$ $N$ factories and $M$ $M$ total number of boxes which you must fulfill. Each factory has 2 values, $p_i$ $p_{i}$ and $a_i$ $a_{i}$ , denoting the price in cents that factory $i$ $i$ charges for one box, and the total number of boxes factory $i$ $i$ has respectively.

Please find the minimum price in cents in order to obtain at least $M$ $M$ boxes. It is guaranteed that at least $M$ $M$ boxes can be achieved.

Input Specification

First line contains 2 integers, $N$ $N$ and $M$ $M$ .

Next $N$ $N$ lines each contain 2 integers, $p_i$ $p_{i}$ and $a_i$ $a_{i}$ .

Output Specification

Output the minimum price in cents in order to obtain at least $M$ $M$ boxes.

Subtasks

For all subtasks:

$1 \le N \le 2 \times 10^5$ $1 \leq N \leq 2 \times 10^{5}$

$1 \le M \le 2 \times 10^9$ $1 \leq M \leq 2 \times 10^{9}$

$0 \le p_i \le 1\,000$ $0 \leq p_{i} \leq 1 000$

$0 \le a_i \le 2 \times 10^6$ $0 \leq a_{i} \leq 2 \times 10^{6}$

Subtask 1 [20%]

$1 \le N \le 100$ $1 \leq N \leq 100$

$1 \le M \le 5 \times 10^7$ $1 \leq M \leq 5 \times 10^{7}$

Subtask 2 [80%]

No additional constraints.

Sample Input

Copy

Sample Output

Copy

Sample Explanation

Price per Box	Units available	Units bought	Prices $\times$ $\times$ # of units	Total Cost	Notes
$5$ $5$	$20$ $20$	$20$ $20$	$5 \times 20$ $5 \times 20$	$100$ $100$
$9$ $9$	$40$ $40$	$0$ $0$			Bought no boxes from factory 2
$3$ $3$	$10$ $10$	$10$ $10$	$3 \times 10$ $3 \times 10$	$30$ $30$
$8$ $8$	$80$ $80$	$40$ $40$	$8 \times 40$ $8 \times 40$	$320$ $320$	Did not buy all 80 units
$6$ $6$	$30$ $30$	$30$ $30$	$6 \times 30$ $6 \times 30$	$180$ $180$
Total	$180$ $180$	$100$ $100$		$630$ $630$	Cheapest total cost

Comments

1

pto1026 commented on Nov. 12, 2021, 4:07 p.m.

Can anyone look at my code and tell me where I have gone wrong, or point out a test case that will highlight my missteps.

2

Nils_Emmenegger commented on Nov. 12, 2021, 4:20 p.m. ← edited →

Since $M$ $M$ can get pretty large (up to $2 \times 10^9$ $2 \times 10^{9}$ ), simulating the purchase of every box individually will be too slow.