訪れる街の集合は \(S\) を含む区間になります。すなわち、\(l \leq S \leq r\) を満たす整数 \(l, r\) が存在し、訪れる街の集合は番号が \(l\) 以上 \(r\) 以下の街の集合となります。

\(l, r\) を決め打ったときの移動距離として考えられる最小値を求めます。この最小値が \(L\) 以下となる \(l, r\) について、\(r - l + 1\) の最大値を求めればよいです。

街 \(l\) と街 \(S\) の距離を \(X\)、街 \(S\) と街 \(r\) の距離を \(Y\) とします。

街 \(l\) を訪れた後に街 \(r\) を訪れるとき移動距離の最小値は \(2X + Y\)、街 \(r\) を訪れた後に街 \(l\) を訪れるとき移動距離の最小値は \(X + 2Y\) となるため、移動距離として考えられる最小値は \(\min(2X + Y, X + 2Y)\) です。

累積和や前計算などで \(X, Y\) を \(O(1)\) 時間で求めれば全体で \(O(N^2)\) 時間となります。

また、\(l\) が増えると許容される \(r\) は広義単調増加するという単調性を利用すれば、尺取り法を用いて \(O(N)\) 時間で解くこともできます。

実装例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	ll n, s, L;
	cin >> n >> s >> L;
	s--;
	vector<ll> a(n - 1);
	for (auto& e : a) cin >> e;
	int ans = 1;
	vector<ll> p(n);
	for (int i = 0; i < n - 1; i++) p[i + 1] = p[i] + a[i];
	for (int l = 0; l <= s; l++) {
		for (int r = s; r < n; r++) {
			ll x = p[s] - p[l], y = p[r] - p[s];
			if (min(2 * x + y, x + 2 * y) <= L) ans = max(ans, r - l + 1);
		}
	}
	cout << ans << '\n';
}