Overview

This problem asks us to maximize the total score of visited stones when moving from stone \(1\) to stone \(N\), with the ability to “skip over one stone (without stopping on it)” up to \(K\) times.

By focusing on the properties of “skipped stones” to reformulate the problem, and applying an advanced optimization technique called WQS Binary Search (Alien DP), we derive a fast solution that satisfies the constraints.

---

Analysis

1. Reformulating the Problem (Considering the Complement)

Takahashi can either “step forward by one” or “jump over one stone.” The action of “jumping over one stone” can be rephrased as “skipping exactly one stone (advancing without stopping on it).”

Let’s organize the conditions that skipped stones must satisfy: - Since stone \(1\) (start) and stone \(N\) (goal) must always be visited, only stones \(2, 3, \ldots, N-1\) can be skipped. - Since jumps of two or more stones are not allowed, two consecutive stones cannot be skipped simultaneously. In other words, skipped stones must not be adjacent to each other (they must be independent). - The number of skipped stones (= the number of “skip one” jumps) is at most \(K\).

Let \(S_{total}\) be the total sum of scores of all stones, and \(T\) be the sum of scores of skipped stones. Then the total score of stones Takahashi visits is \(S_{total} - T\). Since \(S_{total}\) is a constant, maximizing the total score of visited stones is equivalent to “minimizing the sum of scores of skipped stones \(T\).”

Therefore, the problem can be simply redefined as follows:

From the array \(B = [A_2, A_3, \ldots, A_{N-1}]\), select at most \(K\) elements that are not adjacent to each other, and minimize their sum.

2. Why a Straightforward DP (Dynamic Programming) Doesn’t Work in Time

This reformulated problem can be solved with the following DP: - \(dp[i][j][0]\): minimum sum when selecting \(j\) elements from the first \(i\) elements, without selecting the \(i\)-th element - \(dp[i][j][1]\): minimum sum when selecting \(j\) elements from the first \(i\) elements, with the \(i\)-th element selected

However, the number of states in this DP is \(O(N \times K)\). Given the constraints \(N, K \leq 2 \times 10^5\), the total computation is \(O(NK) \approx 4 \times 10^{10}\), which exceeds the time limit (TLE).

3. Introducing WQS Binary Search (Alien DP)

Let \(g(c)\) be the minimum sum when selecting exactly \(c\) elements. Since increasing the number of selectable elements can only decrease (or maintain) the sum, the function \(g(c)\) is a convex function (specifically, concave from above / convex from below) with respect to \(c\).

When such “convexity with respect to the selection count” exists, WQS Binary Search (Alien DP / Penalty Method) can be applied.

Intuitive Image: Controlling the Count Constraint via Penalties (Fines)

Instead of directly handling the strict constraint of “at most \(K\) elements,” we consider a new rule: “Every time you select one element (skip one stone), you pay a penalty (fine) \(C\).”

• If the fine \(C\) is very large, no one wants to skip stones, so the number selected becomes \(0\).
• If the fine \(C\) is very large in the negative direction (essentially receiving a bonus), you want to skip as many as possible, so you select the maximum number of stones within the non-adjacent constraint.

By appropriately adjusting this fine \(C\) through binary search, we can find “the exact fine amount \(C\) such that when optimizing without count restrictions under the penalty rule, the number of selected elements becomes exactly \(K\) (or close to it).”

Once the penalty \(C\) is fixed, the count restriction disappears, so the problem can be solved with a simple \(O(N)\) DP.

---

Algorithm

Step 1: Edge Case Handling

If \(K = 0\) or \(N \leq 2\), no stones can be skipped (or there is no need to skip), so the total sum of all stone scores \(S_{total}\) is directly the answer.

Step 2: \(O(N)\) DP with Fixed Penalty \(C\)

For array \(B\) (of length \(M = N-2\)), perform a minimization DP incorporating the penalty \(C\). When the same minimum cost can be achieved, tie-break by maximizing the number of selected elements.

• \(dp0\): (minimum cost, \(-\)number selected) when the current element is not selected
• \(dp1\): (minimum cost, \(-\)number selected) when the current element is selected (By using Python’s tuple comparison (cost, -cnt), we can simultaneously minimize cost and maximize count)

The transitions are as follows: - Not selecting the next element: adopt the better one (smaller cost; if tied, more elements selected) between \(dp0\) and \(dp1\) from the previous step. - Selecting the next element: can only transition from the state \(dp0\) (not selected in the previous step). Add the current element’s value \(b\) and the penalty \(C\) to the cost, and increment the count by \(1\).

Step 3: Binary Search for the Optimal \(C\)

Set the search range for penalty \(C\) to \([-2 \times 10^9, 2 \times 10^9]\) and perform binary search. - If the DP with penalty \(C\) yields a selected count of \(K\) or more, the penalty is insufficient (the fine should be heavier to reduce the count), so raise the “lower bound” of the search range. - If the selected count is less than \(K\), the fine is too heavy, so lower the “upper bound.”

Step 4: Recovering the Answer

Let the optimal penalty found by binary search be \(best\_C\). Let \(val\) be the minimum cost obtained by solving the DP with \(best\_C\). This value includes “penalty \(best\_C \times K\).” Therefore, the true minimum cost with the penalty subtracted is \(g(K) = val - best\_C \times K\).

The final answer is \(S_{total} - g(K)\).

---

Complexity

• Time Complexity: \(O(N \log (\max |A_i|))\) The number of binary search steps is approximately \(\log_2(4 \times 10^9) \approx 32\), derived from the search range width (about \(4 \times 10^9\)). Since each step calls an \(O(N)\) DP, the total computation is approximately \(32 \times N\), which comfortably fits within the time limit.
• Space Complexity: \(O(N)\) Only memory for storing the input arrays \(A\) and \(B\) is needed. Since the DP table only needs to maintain the previous state, the space complexity is \(O(N)\) (or \(O(1)\) for just the DP portion).

---

Implementation Notes

• Importance of Tie-breaking: In WQS Binary Search, the target count \(K\) may lie on a linear segment of the convex function (a region where the slope is constant and multiple counts can be optimal for the same penalty). Therefore, by implementing the DP to “choose the option with the maximum count” when costs are equal, and setting the binary search condition to cnt >= K, we can reliably recover the correct value at the boundary.

• Optimization for PyPy: In the presented code, to avoid creating new objects (such as tuples) in the inner DP loop, updates are performed using primitive variables like dp0_val, dp0_cnt. This dramatically improves execution speed in Python/PyPy.

  Source Code

import sys

def main():
    # Fast I/O
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    A = [int(x) for x in data[2:]]
    
    total_sum = sum(A)
    if K == 0 or N <= 2:
        print(total_sum)
        return
        
    B = A[1:N-1]
    M = len(B)
    
    # DP solver with penalty C
    # Optimized for PyPy by localizing variables and avoiding object creation
    def solve(C, B=B, M=M):
        dp0_val = 0
        dp0_cnt = 0
        dp1_val = B[0] + C
        dp1_cnt = -1
        
        for i in range(1, M):
            b = B[i]
            if dp0_val < dp1_val or (dp0_val == dp1_val and dp0_cnt < dp1_cnt):
                next_dp0_val = dp0_val
                next_dp0_cnt = dp0_cnt
            else:
                next_dp0_val = dp1_val
                next_dp0_cnt = dp1_cnt
            
            next_dp1_val = dp0_val + b + C
            next_dp1_cnt = dp0_cnt - 1
            
            dp0_val = next_dp0_val
            dp0_cnt = next_dp0_cnt
            dp1_val = next_dp1_val
            dp1_cnt = next_dp1_cnt
            
        if dp0_val < dp1_val or (dp0_val == dp1_val and dp0_cnt < dp1_cnt):
            return dp0_val, -dp0_cnt
        else:
            return dp1_val, -dp1_cnt

    # Check if the constraint K is active
    val, cnt = solve(0)
    if cnt <= K:
        print(total_sum - val)
        return
        
    # Binary search for the penalty C
    low = -2 * 10**9 - 100
    high = 2 * 10**9 + 100
    best_C = low
    
    while low <= high:
        mid = (low + high) // 2
        val, cnt = solve(mid)
        if cnt >= K:
            best_C = mid
            low = mid + 1
        else:
            high = mid - 1
            
    val, cnt = solve(best_C)
    g_K = val - best_C * K
    print(total_sum - g_K)

if __name__ == '__main__':
    main()

---

This editorial was generated by gemini-3.5-flash-thinking.