/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の正整数列 A=a_1,a_2,…,a_{N} と整数 K が与えられます。A の連続する部分列であって、以下の条件を満たすようなものは何個あるでしょうか。
- (条件) 連続部分列に含まれる全ての要素の値の和は、K 以上である。
ただし、ある二つの連続部分列が列として同じでも、取り出された位置が異なるならそれらは別々に数えるものとします。
出力が 32bit 整数型に収まらない場合があることに注意してください。
制約
- 1 \leqq a_i \leqq 10^5
- 1 \leqq N \leqq 10^5
- 1 \leqq K \leqq 10^{10}
入力
入力は以下の形式で標準入力から与えられます。
N K a_1 a_2 ... a_N
出力
条件を満たすような連続部分列の個数を出力してください。
入力例 1
4 10 6 1 2 7
出力例 1
2
- A[1..4]=a_1,a_2,a_3,a_4 (要素の値の和は 16)
- A[2..4]=a_2,a_3,a_4 (要素の値の和は 10)
の二通りです。
入力例 2
3 5 3 3 3
出力例 2
3
ある二つの連続部分列が列として同じでも、取り出された位置が異なるならそれらは別々に数えることに注意してください。
入力例 3
10 53462 103 35322 232 342 21099 90000 18843 9010 35221 19352
出力例 3
36
Score : 400 points
Problem Statement
You are given a sequence of positive integers of length N, A=a_1,a_2,…,a_{N}, and an integer K. How many contiguous subsequences of A satisfy the following condition?
- (Condition) The sum of the elements in the contiguous subsequence is at least K.
We consider two contiguous subsequences different if they derive from different positions in A, even if they are the same in content.
Note that the answer may not fit into a 32-bit integer type.
Constraints
- 1 \leq a_i \leq 10^5
- 1 \leq N \leq 10^5
- 1 \leq K \leq 10^{10}
Input
Input is given from Standard Input in the following format:
N K a_1 a_2 ... a_N
Output
Print the number of contiguous subsequences of A that satisfy the condition.
Sample Input 1
4 10 6 1 2 7
Sample Output 1
2
The following two contiguous subsequences satisfy the condition:
- A[1..4]=a_1,a_2,a_3,a_4, with the sum of 16
- A[2..4]=a_2,a_3,a_4, with the sum of 10
Sample Input 2
3 5 3 3 3
Sample Output 2
3
Note again that we consider two contiguous subsequences different if they derive from different positions, even if they are the same in content.
Sample Input 3
10 53462 103 35322 232 342 21099 90000 18843 9010 35221 19352
Sample Output 3
36