Overview

When you can remove consecutive \(K\) blocks any number of times, find the maximum total value of the blocks that ultimately remain.

The key insight is that when viewing the “remaining blocks” and “removed blocks” from left to right, the removed portions can be treated as chunks of length \(K\).

Analysis

Consider the positions of the blocks that ultimately remain.

Since remaining blocks are never removed, the deletion operations cannot connect blocks on the left and right sides across a remaining block.

Therefore, the removed block sequences between remaining blocks, as well as the removed block sequences to the left of the first remaining block or to the right of the last remaining block, must each be removed independently.

Since the only operation available is removing \(K\) consecutive blocks, the length of each removed interval must be a multiple of \(K\).

Conversely, if the length of a removed interval is a multiple of \(K\), it can be divided into chunks of length \(K\) and removed.

In other words, viewing the original sequence from left to right, we can think of this as a problem of decomposing it into either:

• Keep 1 block
• Remove \(K\) consecutive blocks

For example, when \(K=2\), an interval of length \(2\) can be removed, but two separated blocks cannot be directly removed together.

Therefore, simply “freely choosing which blocks to keep” is not correct.

Naively exhausting all possible operation sequences would result in far too many ways to choose removal intervals, making it completely infeasible for \(N \leq 10^6\).

Instead, we use DP processing from left to right.

Algorithm

Let \(dp[i]\) be “the maximum total when we have legally decided to keep or remove blocks from the 1st through the \(i\)-th block.”

When considering the \(i\)-th block, the last state is one of the following 2 cases:

1. Keep the \(i\)-th block

In this case, the first \(i-1\) blocks just need to have been legally processed already.

The score is:

\(dp[i-1] + A_i\)

2. Remove the last \(K\) blocks together

We remove the \(K\) blocks from the \((i-K+1)\)-th to the \(i\)-th.

In this case, the first \(i-K\) blocks just need to have been legally processed already.

The score is:

\(dp[i-K]\)

Therefore, the transition is as follows:

\(dp[i] = \max(dp[i-1] + A_i,\ dp[i-K])\)

However, when \(i<K\), \(dp[i-K]\) does not exist and cannot be used.

The initial value is:

\(dp[0] = 0\)

In implementation, since \(dp[i]\) only references \(dp[i-1]\) and \(dp[i-K]\), it is not necessary to maintain the entire array.

We can use a rolling DP that only keeps \(K\) elements.

In the code:

vector<long long> dp(K, NEG);
dp[0] = 0;

The indices are managed by the remainder when divided by \(K\).

During processing:

• dp[i % K] contains the pre-update \(dp[i-K]\)
• dp[(i-1) % K] contains \(dp[i-1]\)

Therefore, the update can be done as follows:

dp[to] = max(dp[to], dp[from] + a);

This corresponds to:

\(dp[i] = \max(dp[i-K], dp[i-1] + A_i)\)

The final answer is the value after processing all \(N\) blocks from the beginning, so it is:

dp[N % K]

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(K)\)

Implementation Notes

A sufficiently small value NEG is used to represent unreachable states.

Since \(A_i\) is at most \(10^9\) and \(N\) is at most \(10^6\), the total value can be approximately \(10^{15}\) at most.

Therefore, long long must be used instead of int.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    const long long NEG = -(1LL << 62);
    vector<long long> dp(K, NEG);
    dp[0] = 0;

    for (int i = 1; i <= N; i++) {
        long long a;
        cin >> a;

        int from = (i - 1) % K;
        int to = i % K;

        if (dp[from] != NEG) {
            dp[to] = max(dp[to], dp[from] + a);
        }
    }

    cout << dp[N % K] << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.