The towns to be visited form an interval containing \(S\). In other words, there exist integers \(l\) and \(r\) with \(l \leq S \leq r\), such that the set of the visited towns is precisely formed by the towns numbered between \(l\) and \(r\).

Consider the total traveling distance for a fixed pair \((l, r)\). It suffices to find the maximum \((r - l + 1)\) for a pair \((l, r)\) with the total distance not exceeding \(L\).

Let \(X\) and \(Y\) be the distances between town \(l\) and town \(S\), and between town \(S\) an town \(r\), respectively.

The minimum travel distance when visiting town \(l\) before visiting town \(r\) is \(2X + Y\), and that when visiting town \(r\) before visiting town \(l\) is \(X + 2Y\), so the minimum travel distance possible is \(\min(2X + Y, X + 2Y)\).

After precalculation, \(X\) and \(Y\) can be found in \(O(1)\) time, so that the problem can be solved in a total of \(O(N^2)\) time.

One can also use the property that, as \(l\) increases, the allowed range of \(r\) also grows (weakly) monotonically, one can use the sliding window trick to solve it in \(O(N)\) time.

Sample code

#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';
}