Overview

This problem asks us to find the maximum number of gems that can be collected when starting at position \(S\) and making exactly \(K\) moves along a row of shops. Since the range of shops visited by Takahashi always forms a contiguous interval containing \(S\), we can efficiently find the optimal solution by exhaustively searching over “visited intervals” using the properties of movement paths.

Analysis

1. The range of visited shops forms a “contiguous interval”

Since Takahashi can only move to adjacent shops, the set of shops he ultimately visits forms a contiguous interval \([S-x, S+y]\) (where \(x, y \ge 0\)) that includes the starting position \(S\). Since gems at the same shop can only be collected once (on the first visit), the goal is to cover as wide an interval \([S-x, S+y]\) as possible within the constraint of \(K\) moves.

2. Minimum number of moves to visit interval \([S-x, S+y]\)

Starting from \(S\), the shortest path to visit all shops in the interval \([S-x, S+y]\) (extending \(x\) shops to the left and \(y\) shops to the right) takes one of the following two forms:

• Pattern A (go left first, then turn back right) First move \(x\) steps left to reach \(S-x\), then turn back right to reach \(S+y\). The number of moves in this case is \(x + (x + y) = 2x + y\).

• Pattern B (go right first, then turn back left) First move \(y\) steps right to reach \(S+y\), then turn back left to reach \(S-x\). The number of moves in this case is \(y + (y + x) = 2y + x\).

Therefore, the minimum number of moves required to visit all of interval \([S-x, S+y]\) is \(\min(2x + y, 2y + x)\). If this is at most \(K\), then we can visit this interval in exactly \(K\) moves (any remaining moves can be consumed by going back and forth between adjacent shops).

*Note: Since the constraints guarantee \(K \ge 1\), Takahashi must move at least one step from the starting position. Therefore, \(x + y \ge 1\) must be satisfied.

3. Solution by exhaustive search

The number of shops \(N\) is at most \(2 \times 10^5\), so naively searching all intervals with a double loop would be \(O(N^2)\), which would exceed the time limit (TLE). However, if we fix one direction of movement (e.g., \(x\)), the other direction \(y\) is optimally determined greedily (as large as possible) to use up the \(K\) moves.

This allows us to reduce the search to \(O(N)\).

• Case 1: Searching Pattern A (\(2x + y \le K\)) Enumerate the leftward distance \(x\) from \(0\) to its maximum possible value (\(\min(S-1, \lfloor K/2 \rfloor)\)). For each \(x\), the rightward distance \(y\) can extend up to \(K - 2x\), so we set \(y = \min(N-S, K-2x)\).

• Case 2: Searching Pattern B (\(2y + x \le K\)) Enumerate the rightward distance \(y\) from \(0\) to its maximum possible value (\(\min(N-S, \lfloor K/2 \rfloor)\)). For each \(y\), the leftward distance \(x\) can extend up to \(K - 2y\), so we set \(x = \min(S-1, K-2y)\).

The total gems in interval \([S-x, S+y]\) can be computed in \(O(1)\) per query by precomputing a prefix sum array.

Algorithm

1. Build the prefix sum Create a prefix sum array \(P\) from array \(A\). This allows computing the total gems in interval \([L, R]\) as \(P[R] - P[L-1]\) in \(O(1)\).

2. Exhaustive search for Case 1 Loop \(x\) from \(0\) to \(\min(S-1, \lfloor K/2 \rfloor)\). For each \(x\), set \(y = \min(N-S, K-2x)\), and if \(x+y \ge 1\) is satisfied, compute the sum of interval \([S-x, S+y]\) and update the maximum.

3. Exhaustive search for Case 2 Loop \(y\) from \(0\) to \(\min(N-S, \lfloor K/2 \rfloor)\). For each \(y\), set \(x = \min(S-1, K-2y)\), and if \(x+y \ge 1\) is satisfied, compute the sum of interval \([S-x, S+y]\) and update the maximum.

4. Output the answer Output the updated maximum value.

Complexity

• Time complexity: \(O(N)\) Building the prefix sum takes \(O(N)\), and the loops for Case 1 and Case 2 each run at most \(N\) times, so the overall time complexity is \(O(N)\), which comfortably fits within the time limit.

• Space complexity: \(O(N)\) \(O(N)\) memory is used to store the input array \(A\) and the prefix sum array \(P\).

Implementation Notes

• Be careful with data types: The number of gems \(A_i\) can be up to \(10^9\), and their total sum can reach \(2 \times 10^{14}\), so variables storing prefix sums and the answer must use long long in C++. Also, since the number of moves \(K\) can be up to \(10^9\), it should similarly be handled as long long.

• Corner case: Since \(K \ge 1\), the option of not moving at all (\(x = y = 0\)) is not allowed. The condition if (x + y >= 1) in the code ensures that only cases where at least one step is taken are correctly considered.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, S;
    long long K;
    if (!(cin >> N >> S >> K)) return 0;

    vector<long long> A(N + 1);
    vector<long long> P(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        P[i] = P[i - 1] + A[i];
    }

    auto get_sum = [&](int L, int R) {
        if (L > R) return 0LL;
        return P[R] - P[L - 1];
    };

    long long ans = 0;

    // ケース 1: 2x + y <= K
    // 左に x 個、右に y 個進む（左に行ってから右に行く）
    long long limit_x = min((long long)S - 1, K / 2);
    for (long long x = 0; x <= limit_x; ++x) {
        long long y = min((long long)N - S, K - 2 * x);
        if (y < 0) continue;
        if (x + y >= 1) {
            ans = max(ans, get_sum(S - x, S + y));
        }
    }

    // ケース 2: 2y + x <= K
    // 右に y 個、左に x 個進む（右に行ってから左に行く）
    long long limit_y = min((long long)N - S, K / 2);
    for (long long y = 0; y <= limit_y; ++y) {
        long long x = min((long long)S - 1, K - 2 * y);
        if (x < 0) continue;
        if (x + y >= 1) {
            ans = max(ans, get_sum(S - x, S + y));
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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