Editor

Prize Pool for the Top Scores

#635 · Heaps · Advanced · Fast enough · 130 XP · about 25 min

An online game pays a prize pool equal to the total of the k highest scores posted so far, or of all the scores while there are fewer than k. Scores are posted one at a time, and after each one the game shows the new size of the pool.

Write prize_pools(scores, k) that returns a list with the size of the pool after each score in scores is posted.

Examples

prize_pools([5, 1, 8, 3, 9], 2)  # returns [5, 6, 13, 13, 17]
prize_pools([4, 4, 4], 5)        # returns [4, 8, 12]
prize_pools([2, 7], 1)           # returns [2, 7]

In the first example the two best scores after the third game are 8 and 5, so the pool is 13. The 3 does not change it, and the 9 takes the place of the 5: 9 + 8 = 17.

Constraints

  • 0 <= len(scores) <= 200,000
  • 1 <= k <= 200,000
  • Scores are whole numbers from 0 to 1,000,000.

Time limit

Each test must finish within 10 seconds, and the hidden tests post 200,000 scores with k in the thousands.

Fastest solvers

Leaderboard

First solves only, ranked by stars and then time.