DHDHH

Submit solution
Points: 32
Time limit: 1.0s
Memory limit: 512M
Problem type

Một dãy số gồm toàn các số nguyên không lớn hơn \(S\) có độ đẹp được định nghĩa là một số nguyên dương \(X\) nhỏ nhất, sao cho ta có thể chia dãy số ban đầu thành \(X\) đoạn con liên tiếp, mỗi số trong dãy thuộc một và chỉ một đoạn con và tổng của tất cả các số trong mỗi đoạn con đều không quá \(S\).

Cho dãy số nguyên dương \(a_1, a_2, …, a_N\). Ta gọi độ hoàn hảo của dãy số trên là tổng độ đẹp của mọi dãy con liên tiếp của nó.

Yêu cầu: Tính độ hoàn hảo của dãy số đã cho.

Dữ liệu:

  • Dòng đầu chứa hai số nguyên dương \(N và S (N ≤ 2 * 10^5, S ≤ 10^{15}\)).

  • Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, …, a_N (a_i ≤ min(10^9, S)\) với mọi i=1..N).

Kết quả:

  • Ghi một số nguyên duy nhất là kết quả của bài toán.

Sample Input

3 3
1 2 3

Sample Output

8

Giải thích

Dãy 1, 2, 3 có các dãy con liên tiếp là:

\(1\): độ đẹp là \(1\)

\(2\): độ đẹp là \(1\)

\(3\): độ đẹp là \(1\)

\(1, 2\): độ đẹp là \(1\)

\(2, 3\): độ đẹp là \(2\)

\(1, 2, 3\): độ đẹp là: \(2\)

Vậy độ hoàn hảo bằng: \(1+1+1+1+2+2 = 8\)

Ràng buộc

  • Subtask1: 30% số điểm có\( N ≤ 5000.\)

  • Subtask2: 70% số điểm còn lại không có ràng buộc gì thêm.

Comments