Overview

\(N\) residents take turns watering plants in a fixed order over \(D\) days. Since \(D\) can be extremely large, rather than naively simulating one day at a time, this problem requires leveraging the periodicity (cycle) of the watering schedule to reduce computational complexity.

Analysis

1. Limitations of Naive Simulation

The simplest approach would be to determine who is on duty each day and accumulate the water amounts over \(D\) days. However, looking at the constraints, \(D \leq 10^{14}\), which is an extremely large value. Since we can generally perform around \(10^8\) operations per second, this approach would exceed the time limit (TLE).

2. Focusing on Periodicity

The residents’ duty roster cycles every \(N\) people, and the total amount of water used in one cycle (\(N\) days) is always constant. - Total water used in one cycle: \(S_{total} = A_1 + A_2 + \dots + A_N\)

By considering how many full cycles are repeated within \(D\) days, we can significantly reduce the computation. - Number of full cycles: \(full\_cycles = D \div N\) (quotient) - Remaining days that don’t fill a complete cycle: \(remainder\_days = D \bmod N\) (remainder)

With this, the total amount can be computed as (full_cycles × Stotal) + (water amount for the remaining days).

3. Computing the Remaining Days

For the remaining days (\(0 \leq remainder\_days < N\)), we simply calculate the sum for \(remainder\_days\) people starting from person \(S\) on duty on day 1. Since this part is at most \(N\) days, we can efficiently compute it using a prefix sum, handling the case where the index wraps around from \(N\) back to \(1\).

Algorithm

1. Prepare Prefix Sums: Create an array prefix_sum[i] representing the total water amount from resident \(1\) to \(i\). This allows computing the sum of any interval in \(O(1)\).
2. Cycle Calculation: Divide \(D\) by \(N\) to obtain the quotient (number of cycles) and remainder (leftover days).
3. Compute the Total:
   • Full cycles: quotient × prefix_sum[N]
   • Leftover: Add up the water amounts for the “remainder” days starting from resident \(S\).
     • If \(S + remainder\_days - 1 \leq N\): A simple interval sum.
     • If it exceeds \(N\): Split into two parts — “from \(S\) to \(N\)” and “from \(1\) for the remaining days” — and add them together.

Complexity

• Time Complexity: \(O(N)\)
  • Building the prefix sum takes \(O(N)\), but subsequent calculations are \(O(1)\). This does not depend on the size of \(D\) and comfortably fits within the time limit.
• Space Complexity: \(O(N)\)
  • Required to store the array of length \(N\) (residents’ water amounts and prefix sums).

Implementation Notes

• Converting to 0-indexed: In the program, treating resident numbers \(1 \dots N\) as \(0 \dots N-1\) makes array indexing and remainder calculations smoother.

• Handling Large Numbers: The total value can reach up to \(D \times \max(A_i) = 10^{14} \times 10^4 = 10^{18}\). In Python, this is automatically handled as arbitrary-precision integers, but in other languages (such as C++), you need to use 64-bit integer types (such as long long).

  Source Code

import sys

def solve():
    # 入力を取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    d = int(input_data[1])
    s = int(input_data[2])
    a = list(map(int, input_data[3:]))
    
    # 累積和を計算
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + a[i]
    
    total_a = prefix_sum[n]
    
    # 全体のサイクル数と余りの日数を計算
    full_cycles = d // n
    remainder_days = d % n
    
    # フルサイクルの合計
    ans = full_cycles * total_a
    
    # 余りの日の計算
    if remainder_days > 0:
        # 1日目の当番は住人 S (0-indexed で S-1)
        start_idx = s - 1
        # 連続する remainder_days 分の合計を求める
        # 範囲が配列の末尾を越えない場合
        if start_idx + remainder_days <= n:
            ans += prefix_sum[start_idx + remainder_days] - prefix_sum[start_idx]
        else:
            # 範囲が配列の末尾を越えて先頭に戻る場合
            # 末尾までの和
            ans += prefix_sum[n] - prefix_sum[start_idx]
            # 先頭からの残りの和
            remaining_after_wrap = remainder_days - (n - start_idx)
            ans += prefix_sum[remaining_after_wrap]
            
    print(ans)

if __name__ == "__main__":
    solve()

This editorial was generated by gemini-3-flash-thinking.