高橋君が訪れるお店の番号の最小値を \(m\) 、最大値を \(M\) とします。 高橋君は隣接するお店を訪れるので、番号が \(m\) 以上 \(M\) 以下のお店すべてから宝石を獲得しているとして構いません。 よって、このとき高橋君が手に入れる宝石の個数は \(A _ m+A _ {m+1}+\cdots+A _ M\) です。

移動回数が余った場合、これまでに訪れた店を適切に訪れることで移動回数を消費できるので、訪れるお店の番号の最小値と最大値の組 \((m,M)\) が達成できることは、\(K\) 回以内の移動でお店 \(m\) とお店 \(M\) の両方を訪れることができることと同値です。

\(m=S-a,M=S+b\ (0\le a,0\le b)\) と書いたとき、お店 \(m\) とお店 \(M\) の両方を訪れるために必要な移動回数は \(2\min\lbrace a,b\rbrace+\max\lbrace a,b\rbrace\) です。

\(a\) を固定したとき、\(b\) は可能な限り大きくしたほうが手に入れられる宝石の個数が大きくなります。 よって、\(a\) の範囲 \(0\le a\lt S\) を全探索して

• 移動できる \(b\) の最大値を求め
• 累積和を利用して \(A _ m+A _ {m+1}+\cdots+A _ M\) の値を求める

ことなどでこの問題を解くことができます。

\(a, b\) の大小関係で場合分けをし、小さいほうについて全探索を行うことでもこの問題を解くことができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, S, K;
    cin >> N >> S >> K;
    --S;

    vector<long> A(N);
    for (long& a : A) {
        cin >> a;
    }

    // 累積和を求める
    for (int i = 1; i < N; ++i) {
        A[i] += A[i - 1];
    }
    A.emplace(begin(A));

    long ans = 0;
    // a を全探索
    for (int a = 0; a <= S && a <= K; ++a) {
        int b = min(N - S - 1, max(K - 2 * a, (K - a) / 2));
        ans = max(ans, A[S + b + 1] - A[S - a]);
    }

    cout << ans << endl;
    return 0;
}

N, S, K = map(int, input().split())
S -= 1

A = [0] + list(map(int, input().split()))

# 累積和を求める
for i in range(N):
    A[i + 1] += A[i]

ans = 0
# a を全探索
for a in range(min(S, K)):
    b = min(N - S - 1, max(K - 2 * a, (K - a) // 2))
    ans = max(ans, A[S + b + 1] - A[S - a])

print(ans)