Overview

A problem where you collect gems by moving left and right from a starting point on a straight shopping street. Maximize the total gems in a contiguous interval that can be visited in exactly \(K\) moves.

Analysis

Key Insight 1: The shops visited form a contiguous interval

Since you move along a straight path, the shops you visit always form a contiguous interval \([S-L, S+R]\) that includes the starting point \(S\) (\(L\): maximum distance traveled left, \(R\): maximum distance traveled right).

Key Insight 2: Calculating the minimum number of moves

The minimum number of moves required to visit the entire interval \([S-L, S+R]\) is determined by the order of traversal:

• Go left first, return, then go right: \(2L + R\) moves (walk \(L\) steps left → walk \(L\) steps back right → walk \(R\) steps right)
• Go right first, return, then go left: \(L + 2R\) moves (walk \(R\) steps right → walk \(R\) steps back left → walk \(L\) steps left)

Since we can choose whichever is better, the minimum cost is \(L + R + \min(L, R)\).

Key Insight 3: Leftover moves can be wasted

Since \(N \geq 2\), we can always consume leftover moves by going back and forth between two adjacent shops. Therefore, the condition “minimum number of moves \(\leq K\)” is sufficient.

Problem with the naive approach

Trying all combinations of \((L, R)\) takes \(O(N^2)\), but by splitting into the two cases above and fixing one variable, we can solve it in \(O(N)\).

Algorithm

1. Precompute a prefix sum so that the total gems in any interval can be obtained in \(O(1)\).
2. Case 1 (Left → Right): Iterate \(L\) from \(0\) to \(\min(S-1, \lfloor K/2 \rfloor)\). Since the cost is \(2L + R\), compute the maximum distance we can go right with the remaining \(K - 2L\) steps: \(R = \min(N-1-S,\ K-2L)\).
3. Case 2 (Right → Left): Iterate \(R\) from \(0\) to \(\min(N-1-S, \lfloor K/2 \rfloor)\). Since the cost is \(L + 2R\), compute the maximum distance we can go left with the remaining \(K - 2R\) steps: \(L = \min(S,\ K-2R)\).
4. For each case, compute the total gems in the interval \([S-L, S+R]\) and output the maximum value as the answer.

Concrete Example

For \(N=5, S=3, K=4, A=[1, 5, 3, 7, 2]\) (with \(S=2\) in 0-indexed): - Case 1: When \(L=1\), \(R = \min(2, 4-2) = 2\). Sum of interval \([1,4]\) = \(5+3+7+2 = 17\). - Case 2: When \(R=1\), \(L = \min(2, 4-2) = 2\). Sum of interval \([0,3]\) = \(1+5+3+7 = 16\).

Complexity

• Time complexity: \(O(N)\) (the loop for Case 1 runs at most \(S\) times, the loop for Case 2 runs at most \(N-1-S\) times, totaling \(O(N)\))
• Space complexity: \(O(N)\) (prefix sum array)

Implementation Notes

• Even when \(K\) is very large, the actual range visited is at most \(N\) shops, so \(L\) and \(R\) are clipped to at most \(N\). This ensures the number of loop iterations remains \(O(N)\) even when \(K \leq 10^9\).

• Converting to 0-indexed makes array access easier.

• To account for the case \(L=0, R=0\) (collecting no gems by moving and wasting all moves), set the initial value to \(A[S]\).

  Source Code

import sys
from itertools import accumulate

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    S = int(input_data[1]) - 1  # 0-indexed
    K = int(input_data[2])
    A = [int(input_data[3 + i]) for i in range(N)]
    
    # Prefix sum for A
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    def range_sum(l, r):
        # sum of A[l..r] inclusive, 0-indexed
        if l > r:
            return 0
        return prefix[r + 1] - prefix[l]
    
    # Starting at position S (0-indexed).
    # We can go left by some amount L and right by some amount R.
    # The shops visited are all shops in [S-L, S+R].
    # The minimum number of steps to visit all of [S-L, S+R] is:
    #   L + R + min(L, R)
    # because we go one direction first, come back, then go the other direction.
    # We need L + R + min(L, R) <= K.
    # Also, we can waste extra steps by going back and forth (as long as we don't go out of bounds).
    # We need to be able to waste the extra steps. We can always waste steps as long as N >= 2
    # (go back and forth between two adjacent shops). Since N >= 2, any extra steps can be wasted.
    # But wait - we need to check that we CAN waste steps. If we're stuck at a corner with only
    # one neighbor... actually no, even at a corner we can go back and forth with the one neighbor.
    # So the condition is simply: L + R + min(L, R) <= K.
    # Also L <= S, R <= N-1-S.
    
    # We want to maximize range_sum(S-L, S+R) subject to:
    #   0 <= L <= S
    #   0 <= R <= N-1-S
    #   L + R + min(L, R) <= K
    
    # But we also need K steps total and N >= 2, so we can always waste extra steps
    # by oscillating. The only edge case: can we actually make K moves without going out of bounds?
    # Since N >= 2, we always have at least one neighbor to oscillate with.
    
    ans = A[S]  # At minimum, we get A[S] (L=0, R=0, waste K steps oscillating)
    
    # Case 1: Go left first, then right. Cost = 2*L + R, need 2*L + R <= K.
    # For each L, maximize R = min(N-1-S, K - 2*L). L can be 0..min(S, K//2).
    # Case 2: Go right first, then left. Cost = L + 2*R, need L + 2*R <= K.
    # For each R, maximize L = min(S, K - 2*R). R can be 0..min(N-1-S, K//2).
    
    # Case 1: go left L, come back, go right R
    max_L = min(S, K // 2)
    for L in range(0, max_L + 1):
        remaining = K - 2 * L
        R = min(N - 1 - S, remaining)
        if R < 0:
            continue
        val = range_sum(S - L, S + R)
        if val > ans:
            ans = val
    
    # Case 2: go right R, come back, go left L
    max_R = min(N - 1 - S, K // 2)
    for R in range(0, max_R + 1):
        remaining = K - 2 * R
        L = min(S, remaining)
        if L < 0:
            continue
        val = range_sum(S - L, S + R)
        if val > ans:
            ans = val
    
    print(ans)

solve()

---

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