Trường em có màn hình LED lớn ở sân trường để chiếu các video tuyên truyền, quảng bá hình ảnh, vinh danh học sinh vào những lúc giải lao hay sinh hoạt ngoại khóa. Thư viện video của trường có \(N\) video clip (đoạn phim ngắn), mỗi video clip có thời lượng chiếu là \(a_i\) giây. Để tự động hóa khâu chiếu video, nhà trường cần chọn một số video clip liên tiếp có tổng thời lượng tối thiểu là \(S\) giây, nhằm đảm bảo chiếu đủ thời gian đã lên lịch. Ngoài ra, việc xử lí vieo khá phức tạp nên để tối ưu cho việc xử lí sau này thì số lượng video clip được chọn phải là ít nhất.
Yêu cầu
Là thành viên trong câu lạc bộ truyền thông, em hãy viết chương trình giúp nhà trường tìm ra số lượng video clip liên tiếp ít nhất sao cho tổng thời lượng các video clip được chọn lớn hơn hoặc bằng \(S\). Thư viện video luôn đảm bảo tìm được kết quả.
Dữ liệu vào
Cho trong file văn bản VIDEO.INP, có cấu trúc như sau:
- Dòng \(1\): Gồm hai số nguyên dương \(N\),\(S\) cách nhau một dấu cách(\(N \leq 10^6, S \leq 2.10^9)\)
- Dòng \(2\): Gồm \(N\) số nguyên dương \(a_1,a_2,...,a_n\) thể hiện thời lượng của mỗi video clip. Mỗi số cách nhau một dấu cách(\(1 \leq a_i \leq 10^9)\)
Kết quả
Ghi ra file văn bản VIDEO.OUT, có cấu trúc như sau:
Một dòng duy nhất ghi một số nguyên là kết quả bài toán.
Sample
Input
10 10
1 5 3 2 3 1 4 4 1 2
Output
3
Ràng buộc
- Có \(40\%\) số test tương ứng với \(40\%\) số điểm với \(N \leq 100\)
- Có \(30\%\) số test tương ứng với \(30\%\) số điểm với \(100 < N \leq 1000\)
- Có \(30\%\) số test tương ứng với \(30\%\) số điểm với \(1000 < N \leq 10^6\)
Bình luận