Bài 3 đề thi thử HSG L9 Quỳnh Lưu: Đầu tư chứng khoán

Anh Bình là nhà đầu tư chứng khoán, ngày nào đầu tư anh cũng có lãi. Có ~n~ ngày đầu tư, ngày thứ ~i~ anh Bình thu được lãi suất với số tiền ~a[i]~ (~0< a_i ≤ 10^9~). Trong quá trình đầu tư chứng khoán, Anh luôn đặt ra các mức lãi suất để mình phấn đấu trong thời gian ngắn nhất. Để kiểm chứng kết quả, với mức lãi suất cho trước là ~s~ (~0< s ≤ 2*10^9~) anh muốn biết số ngày liên tiếp ngắn nhất để mình đạt được mức lãi suất trên?

Yêu cầu:

Hãy lập trình giúp anh Bình đếm số ngày liên tiếp ngắn nhất có tổng lãi suất thu được đạt mức ~s~.

Dữ liệu:

• Dòng thứ nhất chứa hai số nguyên dương ~n~ (~0< n ≤ 10^5~) và ~s~ (~0< s ≤ 2*10^9~).
• Dòng thứ 2 chứa ~n~ số nguyên dương ~a_1, a_2, …, a_n~ thể hiện lãi suất đạt được mỗi ngày (~0< ai ≤ 10^9~) các số trên một dòng cách nhau một dấu cách trống.

  Kết quả:

Số ngày ngắn nhất thoã mãn yêu cầu bài toán.

Ví dụ:

Input

10 17
5 1 3 5 10 7 4 9 2 8

Inpt

2

Giới hạn

• 60% số test tương ứng với ~0< n ≤ 10^3~ và ~0< a_i ≤ 10^9~
• 40% số test tương ứng với ~10^3 < n ≤ 10^5~ và ~0< a_i ≤ 10^9~