Bài 4. Tổng tuyệt đối (3 điểm)

Cho dãy n số nguyên. Hãy tính số cách chọn ra các dãy con liên tiếp của dãy số ban đầu sao cho giá trị tuyệt đối của tổng mỗi dãy được chọn lớn hơn S.

Dữ liệu: vào từ file văn bản BAI4.inp có cấu trúc:

• Dòng 1 chứa 2 số nguyên N và S;
• Dòng 2 chứa N số nguyên a_i với i=1,2,…,N

Kết quả: đưa ra file văn bản BAI4.out một số duy nhất tìm được theo yêu cầu của bài toán.

Ví dụ:

Ràng buộc:

• Có 30% số test ứng với 30% số điểm của bài có n<=100, S<=1000
• Có 40% test khác ứng với 40% số điểm của bài có có n,S<=1E4
• Có 30% test khác ứng với 30% số điểm của bài có có n,S<=1E5