Overview

This problem asks us to maximize the sum of remaining elements when repeatedly performing the operation “remove \(K\) consecutive elements” from a sequence of length \(N\).

At first glance, the number of combinations for removal positions seems enormous, but by noting that there is a powerful constraint on the original positions (indices) of elements that can remain, we can efficiently solve this using dynamic programming (DP) with time complexity \(O(N)\) and space complexity \(O(K)\).

Analysis

1. Key Observation: Conditions on Remaining Elements

When repeatedly performing the operation “remove a block of \(K\) consecutive elements,” let the original indices (1-based) of the finally remaining elements, listed from left to right, be \(i_1, i_2, \ldots, i_m\).

The removed portions can be classified into the following three patterns: - Leading portion: \(i_1 - 1\) elements before \(i_1\) - Gaps between elements: \(i_{j+1} - i_j - 1\) elements between \(i_j\) and \(i_{j+1}\) - Trailing portion: \(N - i_m\) elements after \(i_m\)

Since exactly \(K\) elements are removed in each operation, the number of elements in each removed interval must be a multiple of \(K\). Therefore, the following conditions hold:

1. Leading: \(i_1 - 1 \equiv 0 \pmod K \implies i_1 \equiv 1 \pmod K\)
2. Gaps: \(i_{j+1} - i_j - 1 \equiv 0 \pmod K \implies i_{j+1} \equiv i_j + 1 \pmod K\)
3. Trailing: \(N - i_m \equiv 0 \pmod K \implies i_m \equiv N \pmod K\)

Applying these relations sequentially, we obtain the following very elegant property about the original indices of remaining elements: - 1st remaining element: \(i_1 \equiv 1 \pmod K\) - 2nd remaining element: \(i_2 \equiv 2 \pmod K\) - \(j\)-th remaining element: \(i_j \equiv j \pmod K\) - Last remaining element (\(m\)-th): \(i_m \equiv m \equiv N \pmod K\)

In other words, “the original index \(i_j\) of the \(j\)-th remaining element must satisfy \(i_j \equiv j \pmod K\).”

Concrete Example (when \(K=3\))

The original indices of remaining elements are determined as follows: - The 1st remaining element is one of the \(1, 4, 7, \ldots\)-th elements - The 2nd remaining element is one of the \(2, 5, 8, \ldots\)-th elements - The 3rd remaining element is one of the \(3, 6, 9, \ldots\)-th elements

2. Reduction to Dynamic Programming (DP)

We scan the array from left to right and decide whether to “keep” or “remove” each element \(A[i]\). Let the current index be \(i\), and its remainder when divided by \(K\) be \(r = i \pmod K\).

When focusing on element \(A[i]\) at index \(i\), there are two choices:

1. Keep \(A[i]\) \(A[i]\) becomes the \(j\)-th remaining element where \(j \equiv r \pmod K\). The previously kept element (the \((j-1)\)-th one) must be at a position with remainder \(r-1\). Therefore, the value is obtained by adding \(A[i]\) to “the maximum value of the state where processing up to the previous element yields a remainder of \(r-1\) for the count of kept elements.”

2. Remove \(A[i]\) Removing \(A[i]\) means the last kept element is at some earlier index \(i'\) (where \(i' \equiv r \pmod K\)), and all elements from there to the current position (\(i - i'\) elements, which is a multiple of \(K\)) are removed. The maximum value in this case is simply the previously recorded “maximum value of the state with remainder \(r\).”

By adopting whichever of these two choices gives a larger value, we can update the optimal state.

Algorithm

DP Table Definition

• max_dp[r]: The maximum value among processed elements so far, in the state where the count of kept elements has remainder \(r\).
• dp_prev: The maximum value when processing up to the immediately preceding element.

Transition

For each element \(a = A[i]\) (\(r = i \pmod K\)), update as follows:

1. Take the maximum of keeping \(a\) and removing \(a\): $\(val = \max(\text{dp\_prev} + a, \text{max\_dp}[r])\)$
2. Update dp_prev to val for the next step.
3. Update max_dp[r] with val (overwrite only if larger).

Initial Values

• Initialize all elements of max_dp to \(-\infty\). However, set max_dp[0] = 0 as the initial value for the state where nothing is kept (count 0, remainder 0).
• dp_prev = 0

Complexity

• Time Complexity: \(O(N)\) We only scan the array \(A\) once, and each step’s processing is \(O(1)\). Even for \(N = 10^6\), it runs in under 0.1 seconds.
• Space Complexity: \(O(K)\) The DP table we maintain has size only \(K\), so memory consumption is minimal.

Implementation Notes

• Modular arithmetic optimization: Instead of computing i % K at every iteration in the loop, we increment a variable r and reset it to 0 when r == K, avoiding modular arithmetic to improve execution speed.

• Initialization with a sufficiently small value: Since array elements can include negative values, max_dp must be initialized with a sufficiently small value (\(-\infty\)) such as -10**18.

  Source Code

import sys


def solve():
    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:]]

    INF = 10**18
    max_dp = [-INF] * K
    max_dp[0] = 0

    dp_prev = 0
    r = 0
    for a in A:
        val = dp_prev + a
        r += 1
        if r == K:
            r = 0
        if max_dp[r] > val:
            val = max_dp[r]
        dp_prev = val
        if val > max_dp[r]:
            max_dp[r] = val

    print(dp_prev)


if __name__ == "__main__":
    solve()

---

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