SAC '21 Code Challenge P2 - Littering

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Ever since 2017, there has been a noticeable increase in the amount of garbage strewn across SAC. The garbage is of concern to Mr. DeMello, who cannot bear the smell. There is also a rumour going around school saying that Mr. DeMello might cancel the final exam if he is happy enough. In order to make Mr. DeMello happy, you decide to clean up some of the garbage. However, Mr. DeMello has a Suck-Up™ Sensor, which will alert him that you are trying to suck up to him after you pick up more than K pieces of garbage out of the N littered across campus (and make him keep the final exam). Additionally, each piece of garbage has been judged by Mr. DeMello to have a filthiness value, F_i. Armed with this knowledge, you want to find the maximum amount of filthiness you can pick up to maximize your chances to please Mr. DeMello.

Input Specification

The first line will contain N and K, the number of pieces of garbage and the number of pieces of garbage you can pick up.

The second line will contain N space-separated integers, F_i, the filthiness of the i^\text{th} piece of garbage.

Output Specification

Output the maximum amount of filthiness you can remove from the campus.


For all subtasks:

1 \le K \le N \le 100\,000

1 \le F_i \le 1\,000\,000\,000

Subtask 1 [50%]

1 \le N, F_i \le 1\,000

Subtask 2 [50%]

No additional constraints.

Sample Input

5 2
3 4 2 1 5

Sample Output


Explanation for Sample Output

The best solution is to pick up the 2^\text{nd} and 5^\text{th} piece of garbage, yielding the sum of 9.


There are no comments at the moment.