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\). By applying dynamic programming (DP) and cleverly designing the state representation, we can solve this efficiently with a time complexity of \(O(N)\).

---

Analysis

1. Rephrasing the Nature of the Operation

At first glance, the operation of removing elements and “shifting left” seems complex. However, by focusing on the “removed portions” after repeated operations, an important property becomes apparent.

The number of elements removed is always \(K\) per operation. Therefore, the length of each final removed interval must be a multiple of \(K\). Conversely, any contiguous interval whose length is a multiple of \(K\) can be completely removed by deleting \(K\) elements at a time from one end, regardless of how it is arranged in the original sequence.

From this observation, the problem can be simply rephrased as follows:

“Select several non-overlapping intervals of length that is a multiple of \(K\) from the sequence, remove all of them, and find the maximum sum of the remaining elements.”

2. Straightforward Dynamic Programming (DP)

Based on this rephrasing, we define the following DP: - \(dp[i]\): The maximum sum of remaining elements when the first \(i\) elements (\(A_1, A_2, \ldots, A_i\)) of the sequence have been processed.

The value of \(dp[i]\) is the larger of the following two choices:

1. Keep the \(i\)-th element Since we keep the \(i\)-th element \(A_i\), we add \(A_i\) to the maximum value up to the previous position. $\(dp[i] = dp[i-1] + A_i\)$

2. Make the \(i\)-th element the right end of a removed interval There exists some \(j < i\) such that we remove the interval \([j+1, i]\) (of length \(i-j\)). The length \(i-j\) must be a multiple of \(K\). $\(dp[i] = \max_{\substack{0 \le j < i \\ (i-j) \equiv 0 \pmod K}} dp[j]\)\( The condition \)(i-j) \equiv 0 \pmod K\( can be rephrased as **\)j \equiv i \pmod K$**.

3. Optimization

If we implement the above transitions directly, for each \(i\) there are \(O(N/K)\) candidates for \(j\), resulting in an overall complexity of \(O(N^2 / K)\), which will exceed the time limit (TLE) in the worst case (e.g., \(K=1\)).

Here, we focus on the condition \(j \equiv i \pmod K\). Let \(r\) be the remainder when \(i\) is divided by \(K\). Then all candidate \(dp[j]\) values for the transition are limited to “those whose index has remainder \(r\) when divided by \(K\)”.

Therefore, we prepare an array max_dp[r] for each remainder \(r\) (\(0 \le r < K\)) that records the maximum \(dp[j]\) encountered so far. $\(max\_dp[r] = \max_{\substack{j < i \\ j \equiv r \pmod K}} dp[j]\)$

Using this, the transition for choice 2 can be computed in \(O(1)\): $\(dp[i] = max\_dp[i \bmod K]\)$

---

Algorithm

1. Array Initialization:

   • Create a \(dp\) array of size \(N+1\) with initial values of \(-\infty\) (a very small value). However, set \(dp[0] = 0\).
   • Create a max_dp array of size \(K\) with initial values of \(-\infty\). However, set max_dp[0] = 0 (since the index \(0\) of \(dp[0]\) satisfies \(0 \bmod K = 0\)).

2. DP Transitions: For \(i = 1\) to \(N\), perform the following:

   • Transition for keeping the element: \(val = dp[i-1] + A_i\)
   • Transition for removing the element: Let \(r = i \bmod K\), then \(val = \max(val, max\_dp[r])\)
   • Set \(dp[i] = val\).
   • Update max_dp[r] using \(dp[i]\): \(max\_dp[r] = \max(max\_dp[r], dp[i])\)

3. Output the Answer:

   • The final answer is \(dp[N]\).

---

Complexity

• Time Complexity: \(O(N)\) We loop \(i\) from \(1\) to \(N\), and each transition takes \(O(1)\), so the overall complexity is \(O(N)\), which is very fast.
• Space Complexity: \(O(N)\) The DP table dp has size \(N+1\) and max_dp has size \(K\), so the space complexity is \(O(N + K) = O(N)\).

---

Implementation Notes

• Initial value of \(-\infty\): To represent unreachable states, use a sufficiently small value (such as 1e18) as \(-\infty\). To prevent overflow during transitions, use the long long data type.

• Correspondence between 1-indexed and 0-indexed: In the code, the elements \(A\) are managed with 0-indexed from 0 to N-1, but the DP transition index \(i\) corresponds to 1-indexed from 1 to N. Therefore, note that when referencing element \(A_i\), it becomes A[i-1] in the code.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

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);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // dp[i] は A の最初の i 個の要素を処理したときの最大値
    vector<long long> dp(N + 1, -INF);
    // max_dp[r] は、インデックス j % K == r である dp[j] の最大値
    vector<long long> max_dp(K, -INF);

    dp[0] = 0;
    max_dp[0] = 0;

    for (int i = 1; i <= N; ++i) {
        long long val = -INF;
        // i 番目の要素を残す場合
        if (dp[i - 1] != -INF) {
            val = dp[i - 1] + A[i - 1];
        }
        // i 番目の要素を消去する区間の右端とする場合
        int r = i % K;
        if (max_dp[r] != -INF) {
            val = max(val, max_dp[r]);
        }
        dp[i] = val;
        if (dp[i] != -INF) {
            max_dp[r] = max(max_dp[r], dp[i]);
        }
    }

    cout << dp[N] << "\n";

    return 0;
}

---

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