/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君はスーパーマーケットで買い物をしています。
店内には一列に並んだ N 個の棚があり、入口に近い方から順に 1 番目、2 番目、…、N 番目と番号が付けられています。i 番目の棚には A_i 個の商品が陳列されています。
高橋君は入口側の 1 番目の棚から順番に棚を見ていき、各棚で買いたい商品の個数を確認していきます。k 番目の棚まで確認し終えた時点で、1 番目から k 番目までの棚の商品数の合計 A_1 + A_2 + \cdots + A_k が初めて X 以上になったとき、手で持ちきれなくなるので買い物かごを取りに入口まで戻ることにします。
高橋君が買い物かごを取りに戻るのは何番目の棚まで確認し終えたときか求めてください。ただし、N 番目の棚まで確認しても合計が X 以上にならない場合は -1 を出力してください。
制約
- 1 \leq N \leq 5 \times 10^5
- 1 \leq X \leq 10^{15}
- 1 \leq A_i \leq 10^9
- 入力はすべて整数である
入力
N X A_1 A_2 \cdots A_N
1 行目には、棚の数 N と商品数の閾値 X がスペース区切りで与えられる。
2 行目には、各棚の商品数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
出力
高橋君が初めて買い物かごを取りに戻る棚の番号を 1 行で出力せよ。そのような棚が存在しない場合は -1 を出力せよ。
入力例 1
5 7 1 2 3 4 5
出力例 1
4
入力例 2
4 20 3 4 5 6
出力例 2
-1
入力例 3
10 35 2 8 1 7 3 6 9 4 5 10
出力例 3
7
入力例 4
20 5000000000 120000000 350000000 410000000 275000000 330000000 290000000 480000000 150000000 510000000 220000000 305000000 415000000 390000000 260000000 500000000 340000000 280000000 470000000 360000000 190000000
出力例 4
15
入力例 5
1 1000000000 1000000000
出力例 5
1
Score : 300 pts
Problem Statement
Takahashi is shopping at a supermarket.
There are N shelves lined up in a row inside the store, numbered 1, 2, \ldots, N in order from the entrance. The i-th shelf has A_i products displayed on it.
Takahashi looks at the shelves one by one starting from shelf 1 nearest to the entrance, checking the number of products he wants to buy at each shelf. When he finishes checking up to the k-th shelf, if the total number of products from shelves 1 through k, that is A_1 + A_2 + \cdots + A_k, reaches X or more for the first time, he decides to go back to the entrance to get a shopping basket because he can no longer carry everything by hand.
Determine at which shelf number Takahashi finishes checking when he decides to go back to get a shopping basket. If the total does not reach X or more even after checking all shelves up to the N-th shelf, output -1.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 1 \leq X \leq 10^{15}
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
N X A_1 A_2 \cdots A_N
The first line contains the number of shelves N and the threshold X, separated by a space.
The second line contains the number of products on each shelf A_1, A_2, \ldots, A_N, separated by spaces.
Output
Print in one line the shelf number at which Takahashi first decides to go back to get a shopping basket. If no such shelf exists, print -1.
Sample Input 1
5 7 1 2 3 4 5
Sample Output 1
4
Sample Input 2
4 20 3 4 5 6
Sample Output 2
-1
Sample Input 3
10 35 2 8 1 7 3 6 9 4 5 10
Sample Output 3
7
Sample Input 4
20 5000000000 120000000 350000000 410000000 275000000 330000000 290000000 480000000 150000000 510000000 220000000 305000000 415000000 390000000 260000000 500000000 340000000 280000000 470000000 360000000 190000000
Sample Output 4
15
Sample Input 5
1 1000000000 1000000000
Sample Output 5
1