Overview

This problem asks you to maximize the total score of visited stepping stones when traversing \(N\) stepping stones in a garden, allowing up to \(K\) “skip jumps” (jumping over one stone at a time).

Analysis

Rephrasing the Problem

Takahashi moves from stepping stone \(1\) to stepping stone \(N\). The action of “skipping one stone” corresponds to “not visiting and skipping over” a certain stone. Since the number of skip jumps is at most \(K\), this problem can be rephrased as “choose at most \(K\) stepping stones to not visit (skip)”.

However, the movement rules impose the following constraints: - The starting point (stone \(1\)) and the ending point (stone \(N\)) must always be visited. Therefore, only stones \(2\) through \(N-1\) can be skipped. - You cannot “skip two or more consecutive stones” (you can make another skip jump from the landing stone of a previous skip jump, but each skipped stone in between is independent). In other words, the skipped stones must not be adjacent to each other.

Therefore, the problem can be simply rephrased as follows:

From \(A_2, \ldots, A_{N-1}\), select at most \(K\) mutually non-adjacent elements and minimize their total score. The final answer is (sum of all stones’ scores) \(-\) (sum of selected stones’ scores).

Note that skipping stones with positive scores would decrease the total score, so it is sufficient to only consider stones with negative scores as candidates for skipping.

Naive Approach (Dynamic Programming)

Using dynamic programming (DP), we can solve this with \(dp[i][j] = \) (minimum cost when considering up to the \(i\)-th stone with \(j\) skips). However, this results in \(O(NK)\) states, which does not fit within the time limit under the constraints \(N \le 2 \times 10^5, K \le N\) (worst case \(O(N^2)\) complexity).

Greedy with Undo (Doubly Linked List + Priority Queue)

The problem of selecting \(K\) non-adjacent elements to minimize (or maximize) can be solved efficiently by “incorporating undo (regret) options into a greedy approach”.

Consider selecting the element \(i\) with the smallest score (largest absolute value among negatives). If element \(i\) is selected (skipped), its neighbors \(l\) and \(r\) can no longer be selected. However, selecting \(i\) is not always optimal. It may be better to “not select \(i\) and instead select both neighbors \(l\) and \(r\)”, as the total reduction could be larger (more beneficial).

To simulate this “regret”, we perform the following operations: 1. Select the element with the smallest value \(val[i]\) among currently selectable elements. 2. Delete its neighbors \(l, r\) (preventing them from being individually selected later). 3. Update the value of element \(i\) to \(val[l] + val[r] - val[i]\) and push it back into the priority queue. 4. Using a doubly linked list, reconnect element \(i\)’s neighbors to \(left[l]\) and \(right[r]\).

Selecting this updated value \(val[i] = val[l] + val[r] - val[i]\) later corresponds to “canceling the initially selected \(val[i]\) and instead selecting \(val[l]\) and \(val[r]\)”. This is because: $\(\text{(initial profit } val[i] \text{)} + \text{(new profit } val[l] + val[r] - val[i] \text{)} = val[l] + val[r]\)$ which correctly implements the undo of the selection.

Algorithm

1. Compute the total sum of all stones’ scores total_sum.
2. Prepare an array val holding each stone’s value, and a doubly linked list left, right representing adjacency relationships.
   • Since stones \(1\) and \(N\) cannot be skipped, set val[0] and val[N-1] to a sufficiently large value (INF).
3. Add all pairs (val[i], i) for stones \(2\) through \(N-1\) to a priority queue (min-heap).
4. Repeat the following operation up to \(K\) times:
   • Extract the element \(i\) with the minimum value from the queue. If the element has already been deleted, ignore it and extract the next one.
   • If \(val[i] \geq 0\), no further score reduction is possible (skipping provides no benefit), so terminate the loop.
   • Add \(val[i]\) to the cumulative minimum score sum S_min.
   • Mark both neighbors \(l = left[i], r = right[i]\) of \(i\) as deleted (deleted).
   • Update \(val[i]\) to \(val[l] + val[r] - val[i]\) and reinsert it into the queue.
   • Update the doubly linked list, connecting \(i\)’s left to \(left[l]\) and right to \(right[r]\).
5. The final answer is total_sum - S_min.

Complexity

• Time Complexity: \(O(N \log N)\) Insertions and deletions from the priority queue are performed at most \(O(N)\) times. Each operation takes \(O(\log N)\), so the overall time complexity is \(O(N \log N)\), which comfortably fits within the time limit.
• Space Complexity: \(O(N)\) The arrays for the doubly linked list and the number of elements stored in the priority queue are at most \(O(N)\).

Implementation Notes

• Sentinel values at both ends: Since stones \(1\) and \(N\) cannot be skipped, setting their initial values to INF ensures they are never selected during the greedy process.

• Deleted flag: A deleted array is used to indicate that an element has been effectively removed due to an “undo” operation. When an element extracted from the queue is already deleted, it is skipped and the next element is processed.

  Source Code

#include <iostream>
#include <vector>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;

const long long INF = 1e16;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> A(N);
    long long total_sum = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        total_sum += A[i];
    }

    if (N <= 2) {
        cout << total_sum << "\n";
        return 0;
    }

    vector<long long> val(N);
    vector<int> left(N), right(N);
    vector<bool> deleted(N, false);

    val[0] = INF;
    val[N - 1] = INF;
    for (int i = 1; i <= N - 2; ++i) {
        val[i] = A[i];
    }

    for (int i = 0; i < N; ++i) {
        left[i] = i - 1;
        right[i] = i + 1;
    }

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    for (int i = 1; i <= N - 2; ++i) {
        pq.push({val[i], i});
    }

    long long S_min = 0;
    for (int k = 0; k < K; ++k) {
        while (!pq.empty() && deleted[pq.top().second]) {
            pq.pop();
        }
        if (pq.empty()) break;
        auto [v, i] = pq.top();
        pq.pop();
        if (v >= 0) break;

        S_min += v;
        int l = left[i];
        int r = right[i];
        deleted[l] = true;
        deleted[r] = true;

        long long next_val = val[l] + val[r] - val[i];
        if (next_val > INF) next_val = INF;
        val[i] = next_val;

        left[i] = left[l];
        right[i] = right[r];
        if (left[i] >= 0) {
            right[left[i]] = i;
        }
        if (right[i] < N) {
            left[right[i]] = i;
        }
        pq.push({val[i], i});
    }

    cout << total_sum - S_min << "\n";

    return 0;
}

---

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