Mã bài:
ts10th_23_3
Điểm:
1,5 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
512M
Dữ liệu vào:
CAU3.INP
Dữ liệu ra:
CAU3.OUT
Tác giả:
Dạng bài
Hè này, Lam xây dựng cho mình kế hoạch luyện tập chủ động trên một hệ thống lập trình trực tuyến. Hệ thống cung cấp ~n~ bài toán, hai bài toán có nội dung liên quan được sắp xếp liền kề nhau. Các bài toán có độ khó lần lượt là ~a_1, a_2, ..., a_n~ . Lam đặt ra mục tiêu là kết thúc đợt nghỉ hè phải ôn luyện được một số nội dung nên phải làm được các bài toán liên quan và có tổng độ khó lớn hơn hoặc bằng ~S~ .
Do trong hè còn có nhiều hoạt động khác, Lam cũng muốn mình phải làm ít nhất các bài toán mà vẫn đạt mục tiêu đặt ra
Yêu cầu: Hãy giúp Lam tính ra số lượng bài toán ít nhất liên tiếp nhau cần phải làm để đạt tổng độ khó tối thiểu là ~S~.
Dữ liệu
Nhập từ tệp CAU3.INP
:
- Dòng ~1~ chứa ~2~ số nguyên dương ~n~ và ~S~ ~(1 \le n \le 10^7, 1 \le S \le 10^{16})~.
- Dòng ~2~ chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.
Kết quả
Xuất ra tệp CAU3.OUT
:
- Một số nguyên là số lượng bài toán Lam cần làm. Trường hợp không có phương án thỏa mãn, ghi ra số ~-1~.
Ràng buộc
- Subtask ~1~ ~(25\%)~: ~n \le 100, S \le 10^6, a_i \le 10^4~.
- Subtask ~2~ ~(25\%)~: ~n \le 5000, S \le 5 \times 10^9, a_i \le 10^6~.
- Subtask ~3~ ~(25\%)~: ~n \le 10^5, S \le 10^{14}, a_i \le 10^9~.
- Subtask ~4~ ~(25\%)~: không ràng buộc gì thêm.
Ví dụ ~1~
Dữ liệu
10 18
5 1 3 9 10 7 4 9 2 8
Kết quả
2
Ví dụ ~2~
Dữ liệu
5 27
2 3 5 1 9
Kết quả
-1
Bình luận