Overview

The duty roster repeats the same order every \(N\) days, so the problem comes down to splitting \(D\) days into “how many full cycles fit” and “how many days remain at the end.”
The total for one full cycle is easy to compute, and the remainder part can be efficiently calculated using prefix sums.

Analysis

The first key observation in this problem is that the duty order repeats with a period of length \(N\).

For example, if \(N=5,\ S=4\), the duty order is

\(4, 5, 1, 2, 3, 4, 5, 1, \dots\)

In other words, no matter where you start, after \(N\) days, every person has been on duty exactly once.

Key Insight 1: The amount of water per cycle is always the same

During one cycle of \(N\) days, residents \(1\) through \(N\) each appear exactly once, so the total for one cycle is

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

Therefore, if we split \(D\) days into

• \(q = \left\lfloor \dfrac{D}{N} \right\rfloor\) full cycles
• a remainder of \(r = D \bmod N\) days

then

• The total for \(q\) full cycles is \(q \times \sum A_i\)
• We only need to compute the remaining \(r\) days

---

Key Insight 2: The remaining \(r\) days form a “contiguous interval on a circular array”

The remaining \(r\) days correspond to the sum of the first \(r\) people in the sequence starting from resident \(S\).

However, starting from \(S\), the index may exceed \(N\) and wrap back to 1, which makes it a bit tricky to extract directly from the array.

To handle this, we create an array by concatenating \(A\) twice:

\(B = A + A\)

This way, any contiguous interval on the circular array can be represented as a normal contiguous interval on \(B\).
For example, if

\(A = [a_1, a_2, a_3, a_4, a_5]\)

then

\(B = [a_1, a_2, a_3, a_4, a_5, a_1, a_2, a_3, a_4, a_5]\)

If \(S=4\) and we need 3 days, we need

\(a_4 + a_5 + a_1\)

which is a contiguous interval on \(B\).

---

Why the Naive Approach Fails

Simulating day by day and summing up over \(D\) days has a time complexity of \(O(D)\).
However, the constraints allow \(D \le 10^{14}\), so this is far too slow.

Instead, by

• using periodicity to handle the bulk of the days at once
• computing only the remainder using prefix sums

we can solve the problem efficiently.

---

Concrete Example

Consider

• \(N=5\)
• \(D=8\)
• \(S=4\)
• \(A=[2,3,5,7,11]\)

The duty order is

\(4,5,1,2,3,4,5,1\)

so the water amounts are

\(7,11,2,3,5,7,11,2\)

Here,

• \(8 \div 5 = 1\) remainder \(3\)

so

• Total for 1 full cycle: \(2+3+5+7+11=28\)
• Remaining 3 days: \(7+11+2=20\)

Therefore the answer is

\(28+20=48\)

Algorithm

1. Compute the total sum total_cycle = sum(A).
   This is the total water amount for one cycle of \(N\) days.

2. Divide \(D\) by \(N\):
   \(q, r = \mathrm{divmod}(D, N)\)

   • \(q\): number of full cycles
   • \(r\): remaining days

3. Create the doubled array B = A + A.

4. Build the prefix sum array pref for B.
   This allows computing interval sums as

\(\text{pref}[R] - \text{pref}[L]\)

1. Convert the starting position to 0-indexed: start = S - 1.

2. The sum for the remaining \(r\) days is
   pref[start + r] - pref[start]

3. The final answer is

\(q \times \text{total\_cycle} + \text{partial}\)

Complexity

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

Implementation Notes

• Resident numbers are 1-indexed, but Python arrays are 0-indexed, so the starting position should be S - 1.

• The remaining days \(r\) always satisfy \(0 \le r < N\), so by creating A + A, the required interval is guaranteed to fit within it.

• When r=0,
  pref[start + r] - pref[start] = 0
  so no special handling is needed.

• When implementing in other languages, the answer can be very large, so it is safe to use a 64-bit integer type.

  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)
    
    B = A + A
    pref = [0] * (2 * N + 1)
    for i in range(2 * N):
        pref[i + 1] = pref[i] + B[i]
    
    start = S - 1
    partial = pref[start + r] - pref[start]
    
    print(q * total_cycle + partial)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.