Cho dãy số nguyên a gồm n số nguyên dương: a1, a2, . . . , an và một số nguyên dương M.
Yêu cầu: Đếm xem dãy a có bao nhiêu dãy con liên tiếp có tổng không quá M.
Dữ liệu vào
• Dòng đầu chứa: n, M
• Dòng tiếp theo chứa dãy a.
Kết quả
Một số nguyên duy nhất là kết quả bài toán
Input
6 11
3 10 1 4 2 9
Output
11
Giới hạn:
• n ≤ 106 ; 1 ≤ S, ai ≤ 109 ;
• Có 50% test với n ≤ 1000.
Nguồn: ĐPT '1819