BT 13042018

Thu gom rác

OLP2016

Để cải thiện môi trường nhằm thu hút khách du lịch chính quyền của một thành phố du lịch nổi tiếng quyết định tiến hành thu gom và xử lý rác dọc bờ biển. Toàn bộ bờ biển thuộc khu du lịch được chia thành n đoạn đánh số từ 1 đến n. Khảo sát cho thấy ở đoạn thứ i có xi tấn rác, i = 1 ÷ n. Xe liên hợp kiểu mới thu gom, phân loại và chế biến rác được đưa ra vận hành thử nghiệm. Trong một khoảng thời gian hoạt động liên tục xe có thể thu gom và chế biến không quá t tấn rác. Vì là lần vận hành thử nghiệm nên các kỹ sư chế tạo rất thận trọng, muốn chọn một khúc bờ biển nào đó gồm một số đoạn liên tiếp để tiện theo dõi và đánh giá. Hãy xác định có bao nhiêu cách chọn khác nhau nếu chỉ dựa vào tiêu chí đảm bảo sao cho xe không phải xử lý quá t tấn rác. Mỗi đoạn trong khúc đã chọn phải được làm sạch, tức là thu gom hết rác trong đoạn đó. Hai khúc gọi là khác nhau nếu tồn tại một đoạn có ở trong khúc này và không có trong khúc kia.

Dữ liệu:
Vào từ file văn bản TRASH.INP: Dòng đầu tiên chứa 2 số nguyên n và t ( 1 ≤ n ≤ 1e6, 1 ≤ t ≤ 1e9), Dòng thứ 2 chứa n số nguyên x1, x2, . . ., xn (1 ≤ xi ≤ 1e6, i = 1 ÷ n). Tổng các xi không vượt quá 1e9.

Kết quả:
Đưa ra file văn bản TRASH.OUT một số nguyên – số cách lựa chọn khác nhau có thể thực hiện

VD:
Input:
9 10
11 1 2 1 1 5 10 2 3

Ouput:
19