HCI '16 - Gifts - Olympiads Online Judge

HCI '16 - Gifts

View as PDF

Submit solution

All submissions

Best submissions

Points: 17 (partial)

Time limit: 1.4s

Memory limit: 256M

Authors:

zj97, damian, fanpu

Problem type

YuPenG the Penguin is back again! He has just returned from the long trip to Hong Kong to attend the IMO (In My Opinion) competition. However, being the math god and the savage that he is, he does not care about others' opinions nor does he feel that they matter. Because of this, he managed to get the gold medal for IMO (not related to the other IMO). To celebrate his achievement, when YuPenG returned to the South Pole, as the god and ruler of PengVille, he ordered all of his $N$ $N$ subjects to bring him a gift each. (What a corrupted penguin)

The subjects placed the gifts on a round table (YuPenG loves circles). Each of the gifts has a satisfaction value of $A_i$ $A_{i}$ which is how much YuPenG wants that gift. $A_i$ $A_{i}$ can also be negative as some subjects brought cheese and butter. (Eww!) However, there is a problem. YuPenG, as a penguin, does not have hands and have wings. Therefore, he can only grab up to $M$ $M$ contiguous gifts. YuPenG will also only go to the table and grab the gifts twice. (What a lazy Penguin). Being the greedy Penguin that he is, he would wish to have the maximum sum of all the gifts that he grabs. However, he feels that this simple mathematics is too trivial for him and has requested for you to write a program to find the maximum sum of the value of gifts that he can grab.

Input Specification

The first line of input will contain two integers, $N$ $N$ and $M$ $M$ . The next line will contain $N$ $N$ integers representing the array $A$ $A$ .

Output Specification

The output should contain a single line. The line should contain $1$ $1$ integer which represents the maximum amount of satisfaction that YuPenG can achieve.

Constraints

For all subtasks:

$|A_i| \le 10^9$ $| A_{i} | \leq 10^{9}$

Subtask 1 [10%]

$2M \le N \le 30\,000$ $2 M \leq N \leq 30 000$

Subtask 2 [20%]

$N \le 500\,000$ $N \leq 500 000$

$M = \frac N 2$ $M = \frac{N}{2}$

Subtask 3 [70%]

$2M \le N \le 500\,000$ $2 M \leq N \leq 500 000$

Sample Input

Copy

6 2
6 4 -10 5 -1 6

Sample Output

Copy

Explanation

YuPenG can grab the set of gifts of $\{6,6\}$ ${6, 6}$ and $\{5\}$ ${5}$ which both are within 2 gifts which is the maximum amount of gifts he can grab. He cannot grab the set of $\{6,6,4\}$ ${6, 6, 4}$ as it is more than 2 gifts.

Comments

0

maxcruickshanks commented on Dec. 5, 2024, 6:46 p.m. ← edited →

Since the original data were weak, an additional test case was added to the first and third subtasks, and all submissions were rejudged. Data were provided by dnialh_.