Overview

This problem asks us to find the maximum total number of gems in shops visited when Takahashi starts at shop \(S\) and makes exactly \(K\) moves. Since the set of visited shops always forms a contiguous interval \([L, R]\) containing \(S\), we can solve this in \(O(N)\) using prefix sums and formula-based narrowing of the range.

Analysis

1. Properties of Visited Shops

Since Takahashi cannot warp, the set of shops visited in exactly \(K\) moves forms a contiguous interval \([L, R]\) (\(L \le S \le R\)) containing the initial position \(S\). Moreover, since the number of gems \(A_i\) is always non-negative (\(\ge 0\)), for the same number of moves, the wider the visited interval \([L, R]\) is (the smaller \(L\) and the larger \(R\)), the more total gems can be collected.

2. Rephrasing the “Exactly \(K\) Moves” Constraint

At first glance, the parity constraint of “exactly \(K\) moves” seems difficult. However, since the number of shops \(N \ge 2\) and \(K \ge 1\), the length of the visited interval is always at least 2 (\(L < R\)). In this case, if we let \(D(L, R)\) be the minimum number of moves to visit all shops in interval \([L, R]\), then if \(D(L, R) \le K\), we can make the visited interval exactly \([L, R]\) with exactly \(K\) moves.

This is because: - If \(K - D(L, R)\) is even: We can consume moves 2 at a time by going back and forth between an endpoint (e.g., \(R\)) and its neighbor (\(R-1\)), without expanding the visited interval. - If \(K - D(L, R)\) is odd: We can consume 1 extra move by taking a step back just before reaching an endpoint, or stepping back after reaching it, without expanding the visited interval. The remaining even number of moves can be consumed by going back and forth (since the interval has length at least 2, there is always space to step back inside).

Therefore, the problem simplifies to “find the maximum sum of gems in an interval \([L, R]\) satisfying \(D(L, R) \le K\).”

3. Computing the Minimum Number of Moves \(D(L, R)\)

The shortest route to visit all of \([L, R]\) starting from \(S\) is one of the following two patterns: - Pattern 1 (go to left endpoint \(L\) first, then turn around to right endpoint \(R\)) Number of moves: \((S - L) + (R - L) = 2(S - L) + (R - S)\) - Pattern 2 (go to right endpoint \(R\) first, then turn around to left endpoint \(L\)) Number of moves: \((R - S) + (R - L) = (S - L) + 2(R - S)\)

Therefore, the minimum number of moves is \(D(L, R) = (R - L) + \min(S - L, R - S)\).

4. Optimization Idea (From Brute Force to \(O(N)\))

Brute-forcing all combinations of \([L, R]\) costs \(O(N^2)\), which exceeds the time limit for \(N \le 2 \times 10^5\) (TLE). Instead, we split into the two patterns above (depending on which gives the shortest route), and for each fixed endpoint, we directly compute how far the other endpoint can reach using formulas.

Algorithm

To efficiently compute the sum of gems in an interval, we prepare a prefix sum array \(P\) of \(A\) in advance (\(P[i] = A_1 + \dots + A_i\), so the sum of interval \([L, R]\) is \(P[R] - P[L-1]\), computed in \(O(1)\)).

Case 1: Going left first, then right is optimal (\(S - L \le R - S\))

In this case, the minimum number of moves is \(D(L, R) = 2(S - L) + (R - S) = S - 2L + R\). From the condition \(D(L, R) \le K\): $\(S - 2L + R \le K \iff 2L \ge S + R - K \iff L \ge \frac{S + R - K}{2}\)\( Since \)L\( is an integer, rounding up gives \)L \ge \lceil (S + R - K) / 2 \rceil = (S + R - K + 1) // 2$.

When the right endpoint \(R\) is fixed, the conditions that the left endpoint \(L\) must satisfy are all of the following: 1. \(L \ge 1\) (within the range of shops) 2. \(L \ge 2S - R\) (from the Case 1 prerequisite \(S - L \le R - S\)) 3. \(L \ge (S + R - K + 1) // 2\) (from the move count constraint)

Since the number of gems is non-negative, the smaller \(L\) is (the more we extend to the left), the more gems we can obtain. Therefore, for each \(R\) (\(S + 1 \le R \le \min(N, S + K)\)), the minimum \(L\) satisfying the conditions is uniquely determined as: $\(L = \max(1, 2S - R, (S + R - K + 1) // 2)\)\( We compute the sum of gems in interval \)[L, R]$ and update the maximum.

Case 2: Going right first, then left is optimal (\(S - L > R - S\))

In this case, the minimum number of moves is \(D(L, R) = (S - L) + 2(R - S) = 2R - S - L\). From the condition \(D(L, R) \le K\): $\(2R - S - L \le K \iff 2R \le S + L + K \iff R \le \frac{S + L + K}{2}\)\( Rounding down gives \)R \le (S + L + K) // 2$.

When the left endpoint \(L\) is fixed, the conditions that the right endpoint \(R\) must satisfy are all of the following: 1. \(R \le N\) (within the range of shops) 2. \(R \le 2S - L - 1\) (from the Case 2 prerequisite \(S - L > R - S\)) 3. \(R \le (S + L + K) // 2\) (from the move count constraint)

The larger \(R\) is (the more we extend to the right), the more gems we can obtain. Therefore, for each \(L\) (\(\max(1, S - K) \le L \le S - 1\)), the maximum \(R\) satisfying the conditions is uniquely determined as: $\(R = \min(N, 2S - L - 1, (S + L + K) // 2)\)\( We compute the sum of gems in interval \)[L, R]$ and update the maximum.

Finally, we output the maximum value obtained from Case 1 and Case 2.

Complexity

• Time Complexity: \(O(N)\) Building the prefix sum takes \(O(N)\), the Case 1 loop (iterating over \(R\)) takes at most \(O(N)\), and the Case 2 loop (iterating over \(L\)) takes at most \(O(N)\). All operations inside the loops are \(O(1)\), so the overall complexity is \(O(N)\), which comfortably fits within the time limit.
• Space Complexity: \(O(N)\) We use \(O(N)\) memory to store the prefix sum array \(P\) of size \(N+1\).

Implementation Notes

• Handling 1-based indexing: The problem statement uses 1-indexed notation (shops 1 through \(N\)). In the Python code, the prefix sum array P is allocated with size N + 1 so that calculations can be done directly in 1-indexed form, preventing bugs from index shifts.

• Ceiling integer division: The ceiling \(\lceil (S + R - K) / 2 \rceil\) in the computation of \(L\) in Case 1 is elegantly expressed using Python’s integer division as (S + R - K + 1) // 2.

  Source Code

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    S = int(data[1])
    K = int(data[2])
    A = [int(x) for x in data[3:]]

    P = [0] * (N + 1)
    for i in range(N):
        P[i + 1] = P[i] + A[i]

    ans = 0

    # ケース1: S - L <= R - S
    R_start = S + 1
    R_end = min(N, S + K)
    for R in range(R_start, R_end + 1):
        L = max(1, 2 * S - R, (R + S - K + 1) // 2)
        if L <= S:
            val = P[R] - P[L - 1]
            if val > ans:
                ans = val

    # ケース2: S - L > R - S
    L_start = max(1, S - K)
    L_end = S - 1
    for L in range(L_start, L_end + 1):
        R = min(N, 2 * S - L - 1, (L + S + K) // 2)
        if R >= S:
            val = P[R] - P[L - 1]
            if val > ans:
                ans = val

    print(ans)


if __name__ == "__main__":
    solve()

---

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