Overview

This is a problem where you harvest apples from \(N\) trees following the pattern “harvest from \(K\) trees, then rest for \(1\) tree,” and you need to find the total number of harvested apples.

Analysis

Observing Takahashi’s behavior, he repeats the pattern “harvest from \(K\) trees, then rest for \(1\) tree.” In other words, the trees he does not harvest (rests on) are the \((K+1)\)-th, \(2(K+1)\)-th, \(3(K+1)\)-th, … trees counting from the beginning.

This can be solved with a straightforward loop that processes trees one by one from the start, determining whether to “harvest or not” and accumulating the sum. However, in some languages like Python, there is an even more concise and faster approach. That approach is to subtract “the total apples of unharvested trees” from “the total of all apples.”

Algorithm

We think in terms of array indices (\(0\)-indexed). Tree \(1\) is at index 0, and the first resting tree \(K+1\) is at index K. Therefore, the unharvested trees are at indices K, 2K+1, 3K+2, … — that is, starting from index K and increasing by K+1 each time.

Using Python’s slice feature [start:stop:step], the list of unharvested trees can be concisely obtained in one line as D[K::K+1]. Thus, we compute the answer with the following steps: 1. Compute the total sum of apples from all trees: sum(D). 2. Compute the total sum of apples from unharvested trees: sum(D[K::K+1]). 3. The answer is the value obtained by subtracting 2 from 1.

Complexity

• Time complexity: \(O(N)\) Computing the sum of array elements and slice operations are proportional to the length of the array, so they complete in \(O(N)\). This is sufficiently fast for the constraint \(N \le 10^6\).
• Space complexity: \(O(N)\) Since we store the input as an array, \(O(N)\) memory is used.

Implementation Notes

• Leveraging Python’s slicing: By writing D[K::K+1], the operation is executed with C-level internal optimization, making it much faster than explicitly writing a loop with a for statement.

• Overflow considerations: Since the maximum value of \(D_i\) is \(10^9\) and \(N\) is \(10^6\), the answer can be as large as \(10^{15}\). In languages like C++, this does not fit in a 32-bit integer (int), so a 64-bit integer (long long) must be used. In Python, however, integers are automatically handled as arbitrary-precision integers, so there is no concern about overflow.

  Source Code

import sys

def main():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    D = [int(x) for x in data[2:]]
    
    ans = sum(D) - sum(D[K::K+1])
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.