97 . [Tutorial] 好吃的蛋糕

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
$\huge\text{owoovo is 8}$

User's AC Ratio

92.9% (13/14)

Submission's AC Ratio

70.4% (19/27)

Tags

tutorial

Description

有 $N$ 塊蛋糕，經過你審慎評估後，你了解到對於第 $i$ 塊蛋糕他的好吃度為 $y_i$。但無奈的是由於你食量有限，你只能吃下 $K$ 塊蛋糕。

試問在最佳策略下，若要最大化吃下的蛋糕好吃度總和，這個總和最大可以是多少？

Input Format

輸入首行有兩個正整數 $N, K$，代表蛋糕的個數以及你能吃下的蛋糕數量。

接下來一行 $N$ 個正整數 $y_1, y_2, \ldots, y_N$，其中 $y_i$ 代表第 $i$ 塊蛋糕的好吃度。

  • $1 \leq K \leq N \leq 2\times 10^ 5$
  • $1 \leq y_i \leq 10^ 9$

Output Format

輸出一行一個正整數，代表最大可能的蛋糕好吃度總和。

Sample Input 1

5 3
3 1 4 1 5

Sample Output 1

12

Sample Input 2

6 2
2 7 1 8 2 8

Sample Output 2

16

Hints

Problem Source

程式解題社教學題。

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資。 0
2 0~8 無特別限制。 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
Submit
Back to Top