Overview

This problem can be solved simply by adding “how many rest breaks occur” to the total travel time across all sections. The number of breaks can be calculated directly from \(N\) and \(K\) without simulation.

Analysis

First, the total travel time is clearly \(\sum_{i=1}^{N} A_i\)

Next, let’s think about rest breaks. Breaks occur “immediately after finishing every \(K\)-th section,” but only when there are still sections remaining. In other words, breaks occur after section numbers:

• \(K, 2K, 3K, \dots\)
• However, \(N\) is excluded (there is no break after the \(N\)-th section since everything is finished)

This is the same as “the number of multiples of \(K\) between \(1\) and \(N-1\) inclusive,” so the number of breaks is \(\left\lfloor \dfrac{N-1}{K} \right\rfloor\)

---

Concrete Examples

For example, when \(N=10,\ K=3\), the break candidates are after sections \(3, 6, 9\), and since sections still remain after each, there are 3 breaks. Using the formula: \(\left\lfloor \dfrac{10-1}{3} \right\rfloor = \left\lfloor 3 \right\rfloor = 3\) which matches.

For example, when \(N=6,\ K=3\), there is a break after section \(3\), but after section \(6\) the journey ends so no break. Using the formula: \(\left\lfloor \dfrac{6-1}{3} \right\rfloor = 1\) which is correct.

---

A straightforward approach of “iterating through each section and adding a break if \(i \% K == 0\)” also works in \(O(N)\), which is more than fast enough. However, the key point of this problem is that it can be further simplified by computing the number of breaks in a single formula.

Algorithm

1. Read \(N, K\) and the array \(A\) from input.
2. Compute the total travel time with total = sum(A).
3. Compute the number of breaks with breaks = (N - 1) // K.
4. Add total += breaks and output the result.

This gives the total time (travel + breaks).

Complexity

• Time complexity: \(O(N)\) (only for sum(A))
• Space complexity: \(O(N)\) (to store the input array \(A\))

Implementation Notes

• The number of breaks is (N - 1) // K, not N // K. This is because there is no break after the last section.

• The total value can become large, but with Python’s int there is no worry about overflow.

• An implementation that reads all input at once using sys.stdin.buffer.read(), as shown in the provided code, is fast and well-suited for competitive programming.

  Source Code

import sys

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

    total = sum(A)
    total += (N - 1) // K  # 休憩回数

    print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.