ECOO '18 R2 P2 - Homework

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 30.0s
Memory limit: 256M

Problem type

George has procrastinated too much on his N homework assignments, and now he is running out of time to finish them all.

Each of George's N assignments has a weight that it contributes to his grade and a deadline in days from today. George will need one day to finish any of the assignments and he must complete an assignment before its deadline in order to submit it (he can't complete it the day an assignment is due).

Help George figure out the order in which he should complete his assignments such that the total weight of the assignments he completes is maximized.

Input Specifications

The standard input will contain 10 datasets. Each dataset begins with an integer N\,(1\leq N\leq10^6).

The next N lines contain an integer D and a decimal W\,(1\leq D\leq 10^6, 0<W\leq100), representing an assignment that has a deadline in D days from today and a weight of W.

For the first seven cases, N\leq1000.

Output Specifications

For each dataset, output the maximum total weight of the assignments that George can complete, rounded to 4 decimal places (George is very meticulous about his grades).

Sample Input (Two Datasets Shown)

3
1 1.0
2 1.0
3 1.0
5
1 2.0
1 1.0
3 3.0
7 10.0
3 2.0

Sample Output

3.0000
17.0000

Comments

There are no comments at the moment.