Description

Xiao A wants to post $n$ posts on Codeforces! For example:

"My rating is 1064."

"I am PolarSea."

"Do you know phi? Do you know where your phi position is? Do you know its price? 1e9 + 7."

"Every problem is very easy, no need to worry about getting destroyed in the contest. Arrive and check in for T1, casually solve T2, submit T3 once and it passes, think a bit and T4 can also be accepted. DP transitions are easy, all math results are well known. Graph construction is obvious, data structures are quite ordinary. No memory tricks, no constant-factor tricks, the code is not long and your hands will not get sore. No nasty huge simulation, only lots of very easy problems. In a moment, four problems are submitted, everyone gets AK and smiles."

"..."

To do this, Xiao A registered $k$ new accounts. He decides to post each post in order, and use all $k$ accounts. However, posting too much may attract Mike's attention and get him banned, and Xiao A certainly does not want that. After some evaluation, he obtained a safety index $a_i$ for each post, meaning the probability that he will not be banned after posting the $i$-th post.

Since first impressions are very important, Xiao A defines the safety index of an account as the safety index of the first post made by that account. In addition, if two consecutive posts are made using the same account, the safety index of that account will decrease by the smaller safety index of these two posts.

Xiao A wants to find a posting plan that maximizes the sum of the safety indices of all accounts. You only need to output the maximum possible sum.

---

"Simplified Statement"

Partition $1 \sim n$ into exactly $k$ non-empty sets $S_1, S_2, \cdots, S_k$ with no overlap and no omission, and $|S_i|>0$. Let $i$ be assigned to the $d_i$-th set, and maximize

$$\left(\sum_{i=1}^k a[{\min_{j\in S_i}j}]\right)-\left(\sum_{i=1}^{n-1}\min(a_i,a_{i+1})[d_i=d_{i+1}]\right)$$

where on the left, $[x]$ means the element with index $x$, and on the right, $[x]$ equals $1$ if $x$ is true and $0$ otherwise.

Input Format

This problem contains multiple test cases.

The first line contains an integer $t$, indicating the test point id.
The second line contains an integer $T$, indicating the number of test cases.

For each test case:

The first line contains two integers $n, k$.
The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, representing the safety index of each post.

Output Format

For each test case, output one integer per line, representing the answer.

0
3
4 2
1 1 3 2
8 3
1 3 2 8 6 4 7 5
40 10
9843011 22841896 42690334 3412396 8420789 100693326 23390709 11537210 145661796 21418321 16914724 146120903 14287416 9157773 259599687 16469809 13371424 221660485 23554750 3004543 19382066 514113557 959488450 162305801 377127750 240963428 597774302 18789772 647693870 517468301 547221960 162988230 309004668 267293109 867629494 476230153 70400563 100943563 140708197 999999999

3
13
5882440256

Hint

"Explanation for Sample 1"

Xiao A can use account $1$ to post posts $1, 2$ and $4$, and use account $2$ to post post $3$. The total safety is $(a_{\min(1,2,4)}-\min(a_1,a_2))+a_3=1-1+3=3$.

"Constraints and Notes"

This problem has 6 test points.

• Testcase #0 (1 point): sample.
• Testcase #1 (20 points): $k=2$.
• Testcase #2 (20 points): $n\leq 10$, $k\leq 4$.
• Testcase #3 (15 points): $k=3$.
• Testcase #4 (20 points): $n\leq 10^3$.
• Testcase #5 (24 points): no special constraints.

For $100\%$ of the data, $2 \leq k \leq n \leq 10^5$, $0 \leq a_i \leq 10^9$, $T=10$ (except Testcase #0).
For all test points, the time limit is 1s and the memory limit is 128MB.

"Source"

Sweet Round 07 B2.
idea & solution: tzc_wk & Alex_Wei (enhanced); data: Alex_Wei; validation: chenxia25.

My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. My rating is 1064. ......

Upvote -77 Downvote                  PolarSea

Translated by ChatGPT 5