C - Walk the Line Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 個の街が一直線上に並んでいます。街には 1, 2, \ldots, N の番号が付けられており、1 \leq i \leq N-1 を満たす各整数 i について、街 i と街 i + 1 は長さ A_i の道で結ばれています。

あなたははじめ、街 S にいます。あなたは、道で結ばれた 2 つの街の間を、その道を通って移動することを繰り返すことができます。

あなたの移動距離の合計が L 以下となるように移動するとき、一連の移動で訪れる街の数として考えられる最大値を求めてください。ただし、街 S も訪れた街に含め、複数回同じ街を訪れても 1 度しか数えないものとします。

制約

  • 2 \leq N \leq 8000
  • 1 \leq S \leq N
  • 0 \leq L \leq 10^{18}
  • 1 \leq A_i \leq 10^9
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N S L
A_1 A_2 \ldots A_{N - 1}

出力

答えを出力せよ。

入力例 1

6 3 10
5 2 4 1 6

出力例 1

4

あなたははじめ街 3 にいます。街 3 \to 2 \to 3 \to 4 \to 5 の順に移動をしたとき、移動距離の合計は 2 + 2 + 4 + 1 = 9 であり、訪れた街は 2, 3, 4, 5 の 4 つです。

移動距離の合計が 10 以下となるように 5 つ以上の街を訪れることはできないため、このケースに対する答えは 4 となります。

入力例 2

8 8 17
2 3 4 4 3 5 1

出力例 2

6

入力例 3

2 1 1000000000000000000
10000

出力例 3

2

入力例 4

9 6 28
5 4 9 2 3 6 1 4

出力例 4

6

Score : 300 points

Problem Statement

There are N towns arranged in a line. The towns are numbered 1, 2, \ldots, N, and for each integer i satisfying 1 \leq i \leq N-1, town i and town i + 1 are connected by a road of length A_i.

You are initially at town S. You can repeatedly move between two towns connected by a road using that road.

Find the maximum possible number of towns visited in a sequence of moves such that the total distance traveled is at most L. Here, town S is included among the towns visited, and a town visited multiple times is counted only once.

Constraints

  • 2 \leq N \leq 8000
  • 1 \leq S \leq N
  • 0 \leq L \leq 10^{18}
  • 1 \leq A_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N S L
A_1 A_2 \ldots A_{N - 1}

Output

Output the answer.

Sample Input 1

6 3 10
5 2 4 1 6

Sample Output 1

4

You are initially at town 3. If you move in the order town 3 \to 2 \to 3 \to 4 \to 5, the total distance traveled is 2 + 2 + 4 + 1 = 9, and the towns visited are 2, 3, 4, 5, that is, four towns.

It is impossible to visit five or more towns with a total travel distance of at most 10, so the answer for this case is 4.

Sample Input 2

8 8 17
2 3 4 4 3 5 1

Sample Output 2

6

Sample Input 3

2 1 1000000000000000000
10000

Sample Output 3

2

Sample Input 4

9 6 28
5 4 9 2 3 6 1 4

Sample Output 4

6