Calgary Collegiate Programming Competition 2020 — Open Division


2020-03-14 10:00 AKDT

Calgary Collegiate Programming Competition 2020 — Open Division


2020-03-14 14:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -219 days 6:41:55

Time elapsed


Time remaining


Problem H
Profitable Pizzas

A new app available in Calgary allows people to sign-up to deliver pizzas in exchange for money. Every first of the month, a new list of pizzas to deliver is available. Each entry on the list contains the number $p_ i$ of the pizza to be delivered, the amount $d_ i$ of dollars the delivery-person will earn to deliver the pizza, and the deadline $t_ i$ in seconds by which the pizza must be delivered. If the pizza is delivered after the deadline, the delivery-person does not receive any money. Each pizza takes one second to deliver and only one can be delivered per second. You are the first person to login to this new app every month and can select all the pizzas you want to deliver before everyone else. You’d like to maximize the amount of money you can make from a given delivery list.

Write the algorithm to find that maximum.


The first line contains a single integer $1 \leq N \leq 2\cdot 10^5$, the number of pizzas to be delivered.

It is followed by $N$ lines, each containing an integer $1 \leq t_ i \leq 2\cdot 10^6$ representing the deadline by which the pizza must be delivered, followed by a space, followed by an integer $1 \leq d_ i \leq 100$ representing the amount of money paid for delivering the pizza before the deadline.


For each query, output the maximum amount of money you can get for delivering the pizzas before the deadline.

Sample Input 1 Sample Output 1
1 1
2 2
3 3
4 4
5 5