Overview

This problem requires adding the total travel time of each section to “the number of rest breaks.”
The number of rest breaks can be counted directly, and the answer is \( \sum A_i + \left\lfloor \dfrac{N-1}{K} \right\rfloor \).

Analysis

First, the total travel time is simply

\[ A_1 + A_2 + \cdots + A_N \]

Next, we need to find the total rest time.
Rest breaks occur:

• After section \(K\)
• After section \(2K\)
• After section \(3K\)
• …

However, there is no rest break after finishing the last section.
In other words, the number of rest breaks is “the count of multiples of \(K\) among the sections that are less than \(N\).”

How many rest breaks are there?

Rest breaks occur at

\[ K, 2K, 3K, \ldots \]

among those that are less than \(N\).
This is the same as “the number of multiples of \(K\) between \(1\) and \(N-1\) inclusive,” which is

\[ \left\lfloor \frac{N-1}{K} \right\rfloor \]

Concrete example

For example, if \(N=10,\ K=3\), rest breaks occur:

• After section 3
• After section 6
• After section 9

for a total of 3 times. Indeed,

\[ \left\lfloor \frac{10-1}{3} \right\rfloor = \left\lfloor \frac{9}{3} \right\rfloor = 3 \]

Common mistake

Using \(N // K\) can lead to incorrect results.
For example, when \(N=6,\ K=3\), there is a rest break after section 3, but after section 6, the journey is already over, so there is no rest break.

• Correct number of rest breaks: \(1\)
• \(N // K = 6 // 3 = 2\) is incorrect

Therefore, the key point is to use \((N-1)//K\).

Naive approach

You can also simulate by iterating through each section:

• Add the travel time
• If the section number is a multiple of \(K\) and it is not the last section, add \(1\)

This simulation runs in \(O(N)\), which is fast enough.
However, since the number of rest breaks can be directly computed with a formula in this problem, you can write it more simply.

Algorithm

1. Compute the total sum \(S = \sum A_i\) of array \(A\)
2. Compute the number of rest breaks \(R = (N-1)//K\)
3. Output \(S + R\)

Complexity

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

Implementation notes

• The number of rest breaks is \((N-1) // K\), not \(N // K\).

• When implementing in other languages, \(\sum A_i\) can become large, so use a 64-bit integer type (long long, etc.).

• In this code, since the entire input is stored as an array, the space complexity is \(O(N)\).

  Source Code

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
N, K = data[0], data[1]
A = data[2:]

total = sum(A) + (N - 1) // K
print(total)

---

This editorial was generated by gpt-5.4-high.