Overview

This problem asks you to find the total number of apples \(D_i\) on harvested trees when you look at the trees from left to right, repeating the pattern of “harvest \(K\) trees, then skip 1 tree.”

Analysis

The key insight is that which trees are harvested is entirely determined by their position (index).
Specifically, when viewing the trees in cycles of \(K+1\) trees each:

• The first \(K\) trees in each cycle are harvested
• The last 1 tree in each cycle is skipped (rest)

For example, if \(K=3\), the cycle length is \(4\):
“harvest, harvest, harvest, skip, harvest, harvest, harvest, skip, …”

Therefore, for each \(i\): - If \(i \bmod (K+1)\) is \(1, 2, \ldots, K\), add it to the sum - If \(i \bmod (K+1)\) is \(0\) (the last position in the cycle), do not add it

Even if you think about “constructing harvest intervals and computing their totals,” you still need to read all \(D_i\) values, and ultimately all you need to do is perform this check \(N\) times.
Since the constraint is \(N \le 10^6\), the optimal approach is to make a single \(O(N)\) pass. Also, since the input is large, you need to read standard input efficiently.

Algorithm

1. Set the cycle length as \(cycle = K+1\).
2. Track the position within the cycle pos starting from \(1\) (\(1\) through \(K\) means harvest, \(K+1\) means skip).
3. For \(i = 1\) through \(N\), read \(D_i\) in order:
   • If pos <= K, add it to the answer
   • Increment pos by 1, and if pos == cycle + 1, reset pos = 1 (repeating the cycle)
4. Output the total at the end.

This accurately simulates the rule of “harvest \(K\) trees → skip 1 tree” as described in the problem.
(Even if \(N\) ends in the middle of a cycle, the process naturally terminates partway through.)

Complexity

• Time complexity: \(O(N)\) (each tree is processed exactly once)
• Space complexity: \(O(1)\) (no input array is stored; values are added as they are read)

Implementation Notes

• Since \(N\) can be up to \(10^6\) and \(D_i\) can be up to \(10^9\), the total can reach approximately \(10^{15}\). Python’s int can handle this safely without overflow.

• Because the input is large, we read everything at once using sys.stdin.buffer.read() and parse the integers manually for speed (calling input() \(10^6\) times tends to be slow).

• The cycle check can also be done with i % (K+1), but in the code we increment pos and reset it cyclically to avoid modular arithmetic and keep things simple.

  Source Code

import sys

data = sys.stdin.buffer.read()
n_data = len(data)
p = 0

def read_int():
    global p
    while p < n_data and data[p] <= 32:
        p += 1
    x = 0
    while p < n_data and data[p] > 32:
        x = x * 10 + (data[p] - 48)
        p += 1
    return x

N = read_int()
K = read_int()

cycle = K + 1
pos = 1
ans = 0

for _ in range(N):
    d = read_int()
    if pos <= K:
        ans += d
    pos += 1
    if pos == cycle + 1:
        pos = 1

sys.stdout.write(str(ans))

This editorial was generated by gpt-5.2-high.