Overview

This problem asks you to find the total time for an entire drive by adding the sum of travel times across \(N\) segments and the number of rest breaks taken every \(K\) segments.

Analysis

First, the total time can be decomposed into “sum of travel times” + “sum of rest times.”

The sum of travel times is simply \(A_1 + A_2 + \cdots + A_N\).

The key point is correctly counting the number of rest breaks. Let’s organize the conditions under which a break occurs:

• Immediately after finishing a segment whose number is a multiple of \(K\) (\(K, 2K, 3K, \ldots\))
• And there are still remaining segments to drive

In other words, no break is taken immediately after finishing segment \(N\) (the last segment).

Let’s verify with concrete examples:

• Example 1: When \(N = 5, K = 2\), the multiples of \(K\) are \(2, 4\). After segment 2, there are remaining segments, so a break is taken. After segment 4, there are remaining segments, so a break is taken. The number of breaks is 2.
• Example 2: When \(N = 4, K = 2\), the multiples of \(K\) are \(2, 4\). After segment 2, there are remaining segments, so a break is taken. Segment 4 is the last segment, so no break is taken. The number of breaks is 1.
• Example 3: When \(N = 3, K = 5\), there are no multiples of \(K\) that are \(N\) or less, so the number of breaks is 0.

In general, the number of breaks is the count of multiples of \(K\) that are at most \(N\), excluding \(N\) itself.

The number of multiples of \(K\) that are at most \(N\) is \(\lfloor N / K \rfloor\). From here, you might be tempted to case-split — subtracting 1 if \(N\) itself is a multiple of \(K\) since no break is taken at the last segment — but if you think of it as “the number of multiples of \(K\) that are less than \(N\),” it can be uniformly computed as \(\lfloor (N-1) / K \rfloor\). When \(K > N-1\) (i.e., no break occurs at all), the result is \(0\).

Algorithm

1. Compute the sum of travel times \(\text{total} = \sum_{i=1}^{N} A_i\).
2. Determine the number of breaks \(\text{breaks}\).
   • If \(K \leq N - 1\): \(\text{breaks} = \lfloor (N-1) / K \rfloor\)
   • Otherwise (\(K \geq N\)): \(\text{breaks} = 0\)
3. Output \(\text{total} + \text{breaks}\) as the answer.

Note: \(\lfloor (N-1) / K \rfloor\) represents “the number of multiples of \(K\) between \(1\) and \(N-1\) inclusive.” This corresponds to counting only the segments \(K, 2K, \ldots\) that come before the last segment \(N\).

Complexity

• Time complexity: \(O(N)\) (to compute the sum of the array)
• Space complexity: \(O(N)\) (to store the array \(A\))

Implementation Notes

• Since \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the sum can be approximately \(2 \times 10^{14}\). In C++ and similar languages, you need to use a 64-bit integer type (long long), but in Python there is no need to worry about integer overflow.

• When computing the number of breaks, note that if \(K \geq N\) (the drive ends before \(K\) segments are completed), the number of breaks is 0. In the code, this is handled by branching on the condition K <= N - 1, but in practice, the formula \(\lfloor (N-1) / K \rfloor\) alone automatically yields \(0\) when \(K \geq N\), so it works correctly even without the conditional branch.

  Source Code

N, K = map(int, input().split())
A = list(map(int, input().split()))
total = sum(A)
if K <= N - 1:
    breaks = (N - 1) // K
else:
    breaks = 0
print(total + breaks)

---

This editorial was generated by claude4.6opus-thinking.