SAC '21 P2 - Littering

View as PDF

Submit solution

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

Authors:
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.

Constraints

For all subtasks:

1 \leq K \leq N \leq 100\,000

1 \leq F_{i} \leq 1\,000\,000\,000

Subtask 1 [50%]

1 \leq N, F_{i} \leq 1\,000

Subtask 2 [50%]

No additional constraints.

Sample Input

5 2
3 4 2 1 5

Sample Output

9

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.


Comments

There are no comments at the moment.