Overview

This is a problem where you can repeatedly remove consecutive \(K\) blocks and want to maximize the total sum of the blocks that ultimately remain.

The key insight is that when you think about “which blocks to keep,” the length of each consecutive segment of removed blocks must be a multiple of \(K\).

Analysis

Let’s fix which blocks ultimately remain.

For example, representing remaining blocks as 1 and removed blocks as 0, the final state looks like this:

11100011100000011

Now, focus on the consecutive segments of removed blocks 0.

Each operation removes exactly \(K\) consecutive blocks at once.
Also, you cannot simultaneously remove blocks on the left and right that span across a remaining block.

Therefore, the length of each consecutive segment of removed blocks must be a multiple of \(K\).

Conversely, if the length of each consecutive segment of removed blocks is a multiple of \(K\), we can achieve this by removing \(K\) blocks at a time from that segment, so it is realizable.

In other words, this problem can be rephrased as follows:

For each block, decide whether to “keep” or “remove” it.
However, the length of every consecutive segment of removed blocks must be a multiple of \(K\).
Maximize the total sum of kept blocks.

If we naively enumerate all orderings of operations or all segments to remove, there are far too many choices, and it is impossible to solve in time for \(N \leq 10^6\).

Therefore, we consider a dynamic programming approach that processes blocks from left to right.

Algorithm

Define \(dp[i]\) as follows:

The maximum total sum of kept blocks, satisfying the conditions, when considering the first \(i\) blocks from the left.

The initial value is:

\[ dp[0] = 0 \]

For the \(i\)-th block, there are broadly two choices:

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

In this case, we simply add \(A_i\) to the optimal solution up to the \((i-1)\)-th block.

\[ dp[i] = dp[i-1] + A_i \]

2. Remove the last \(K\) blocks

We consider removing the \(K\) blocks at positions \(i-K+1, i-K+2, \ldots, i\) together.

In this case, the remaining total equals the optimal value up to the \((i-K)\)-th block.

\[ dp[i] = dp[i-K] \]

Therefore, for \(i \geq K\):

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

On the other hand, for \(i < K\), we cannot yet remove \(K\) blocks together, so:

\[ dp[i] = dp[i-1] + A_i \]

For example, when \(K=2\), the length of consecutive removed segments must be \(2, 4, 6, \ldots\).
Even the case of removing a consecutive segment of length \(4\) can be represented by applying the “remove the last \(2\)” transition twice.

The final answer is:

\[ dp[N] \]

Complexity

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

Storing the full DP array directly requires \(O(N)\) memory, but the transition only needs \(dp[i-1]\) and \(dp[i-K]\).

Therefore, the code uses an array of length \(K\) to retrieve \(dp[i-K]\).

Implementation Details

prev holds the previous value \(dp[i-1]\).

The array dp is used as a circular array of length \(K\).

When processing the \(i\)-th element, \(i\) and \(i-K\) have the same remainder when divided by \(K\), so dp[i % K] contains \(dp[i-K]\).

In the code, r corresponds to the current \(i \bmod K\).

keep = prev + x
skip = dp[r]
cur = max(keep, skip)

• keep: the case where the current block is kept
• skip: the case where the last \(K\) blocks are removed

However, while \(i < K\), we cannot yet remove \(K\) blocks, so only keep is used.

Also, the absolute value of \(A_i\) is at most \(10^9\) and \(N\) is at most \(10^6\), so the total can be on the order of \(10^{15}\).
In Python, integers have arbitrary precision so there is no issue, but in C++ and similar languages, you need to use long long.

Source Code

import sys

def main():
    data = sys.stdin.buffer.read()
    ndata = len(data)
    idx = 0

    while data[idx] <= 32:
        idx += 1
    x = 0
    while data[idx] > 32:
        x = x * 10 + (data[idx] - 48)
        idx += 1
    N = x

    while data[idx] <= 32:
        idx += 1
    x = 0
    while data[idx] > 32:
        x = x * 10 + (data[idx] - 48)
        idx += 1
    K = x

    dp = [0] * K
    prev = 0
    r = 0

    for i in range(1, N + 1):
        while data[idx] <= 32:
            idx += 1

        neg = False
        if data[idx] == 45:
            neg = True
            idx += 1

        x = 0
        while idx < ndata and data[idx] > 32:
            x = x * 10 + (data[idx] - 48)
            idx += 1

        if neg:
            x = -x

        r += 1
        if r == K:
            r = 0

        keep = prev + x
        if i >= K:
            skip = dp[r]
            cur = skip if skip > keep else keep
        else:
            cur = keep

        dp[r] = cur
        prev = cur

    print(prev)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.