P10093 [ROIR 2022] Gifts (Day 2)

Translated from [ROIR 2022 D2T4](https://neerc.ifmo.ru/school/archive/2021-2022/ru-olymp-regional-2022-day2.pdf)。 Santa Claus asks Vova to choose a gift. In front of Vova, there are $n$ gifts in a line. The happiness value each gift brings to Vova is given by an integer, and the value of the $i$-th gift is $a_i$. The happiness value can be positive, negative, or zero. Santa Claus asks Vova to choose two integers $l$ and $r$ such that $1 \le l \le r \le n$. Vova needs to take all gifts from $l$ to $r$. However, among the chosen gifts, Vova must give the $k$ gifts with the top $k$ largest happiness values to his sister Masha。

Help Vova choose $l$ and $r$ so that $1 \le l \le r \le n, r - l + 1 \ge k$, and the total happiness value of the gifts he gets (excluding the gifts given to his sister) is maximized。

The first line contains two integers $n$ and $k$, representing the number of gifts in front of Vova and the number of gifts that must be given to Masha。 The second line contains $n$ integers separated by spaces. The $i$-th integer $a_i$ is the happiness value brought by the $i$-th gift。

Output one integer, the total happiness value of the gifts Vova chooses, excluding the gifts given to Masha。

In sample $1$, Vova does not need to give any gifts to Masha, so he will choose $l = 3, r = 5$, and the total happiness value of the chosen gifts is $5 + (−1) + 7 = 11$。 In sample $2$, Vova needs to give the gift with the maximum happiness value to Masha. Then he will still choose $l = 3, r = 5$, but the total happiness value is $5 + (−1) = 4$。 In sample $3$, Vova needs to give the two gifts with the top two largest happiness values to Masha. In this case, it is not hard to see that Vova’s best choice is actually to select only two gifts and then give them both to his sister Masha. One optimal choice is $l = 1, r = 2$. Then the total happiness value is $0$。 This problem uses bundled testdata。 | Subtask | Score | Special property | | :----------: | :----------: | :----------: | | $1$ | $7$ | $n\le200$ | | $2$ | $8$ | $n\le1000$ | | $3$ | $10$ | $n\le6000$ | | $4$ | $8$ | $k=0$ | | $5$ | $14$ | $k=1$ | | $6$ | $39$ | $n\le80000$ | | $7$ | $14$ | None | Constraints: For $100\%$ of the data, $1 \le n \le 200000, 0 \le k \le \min(100, n),−10^9 \le a_i \le 10^9$。 Translated by ChatGPT 5