Overview

Since the duty roster repeats the same order every \(N\) days, this problem requires splitting \(D\) days into “complete cycles” and “remaining days” to compute the total.
Instead of simulating day by day, we use the periodicity to compute the answer efficiently.

Analysis

The key observation is that the duty order repeats with a period of length \(N\).
If we denote the water usage array per resident as \(A_1, A_2, \dots, A_N\), then the total water used in one cycle (\(N\) days) is

\( \text{total\_cycle} = \sum_{i=1}^{N} A_i \)

Why a naive approach is too slow

If we naively compute “today’s duty person” for each day from day \(1\) to day \(D\) and accumulate the sum, it takes \(O(D)\) time.
However, since the constraint is \(D \le 10^{14}\), this is far too slow.

How to solve it

We decompose \(D\) days into:

• Number of complete cycles: \(q = \lfloor D/N \rfloor\)
• Remaining days: \(r = D \bmod N\)

Then:

• The contribution from complete cycles is \(q \times \text{total\_cycle}\)
• For the remaining \(r\) days, we sum sequentially starting from position \(S\)

This allows us to handle large \(D\) efficiently.

For example, if \(N=5, S=4\), the order is
\(4,5,1,2,3,4,5,\dots\)
so the remaining \(r\) days may wrap around from the end of the array to the beginning.
We handle this case distinction in the implementation.

Algorithm

1. Read \(N, D, S\) and the array \(A\).
2. Compute \(\text{total\_cycle} = \sum A\).
3. Compute \((q, r) = \text{divmod}(D, N)\).
4. Initialize the answer as \(ans = q \times \text{total\_cycle}\).
5. Convert the starting position to 0-index: start = S - 1.
6. If \(r > 0\), add the contribution of the remaining \(r\) days:
   • If start + r <= N, add A[start:start+r] (no wraparound)
   • Otherwise, add A[start:] + A[:(start+r)%N] (wraps from the end to the beginning)
7. Output ans.

Complexity

• Time complexity: \(O(N)\)
  (Computing sum(A) and at most summing over the entire array)
• Space complexity: \(O(N)\)
  (Storing the input array \(A\))

Implementation Notes

• Resident numbers are 1-indexed, while Python arrays are 0-indexed, so convert with start = S - 1.

• It is important to correctly handle the wraparound case (end → beginning).

• The answer can become very large, but with Python’s int, there is no concern about overflow.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, D, S = map(int, input().split())
    A = list(map(int, input().split()))

    total_cycle = sum(A)
    q, r = divmod(D, N)

    ans = q * total_cycle

    start = S - 1  # 0-index
    if r > 0:
        if start + r <= N:
            ans += sum(A[start:start + r])
        else:
            ans += sum(A[start:]) + sum(A[:(start + r) % N])

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.3-codex.