P7878 "SWTR-7" My rating is 1064 (hard version)

#### This problem is the hard version of My rating is .... Note that the constraints are different from the [easy](https://www.luogu.com.cn/problem/P7874) version. #### A simplified statement is provided below the main description. [My rating is 1064.](https://codeforces.com/blog/entry/74503) (It was taken down by 2 - Tower, so it cannot be opened now.)

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.

**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.

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

**"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](https://www.luogu.com.cn/contest/) B2. idea & solution: [tzc_wk](https://www.luogu.com.cn/user/115194) & [Alex_Wei](https://www.luogu.com.cn/user/123294) (enhanced); data: [Alex_Wei](https://www.luogu.com.cn/user/123294); validation: [chenxia25](https://www.luogu.com.cn/user/138400). > **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