/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は陸上部のマネージャーとして、部員たちの練習記録を管理しています。
陸上部では N 日間の練習期間があり、各日には 1 から N までの番号が付けられています。日 i (1 \leq i \leq N) には、その日の「練習強度」を表す正の整数 A_i が記録されています。
部のルールでは、日 l から日 r までの連続する r - l + 1 日間からなる期間であって、その長さが K 日以上かつ期間内の練習強度の合計が目標値 M 以上であるものを「達成期間」と呼び、特別に表彰することになっています。
高橋君は、表彰対象となる達成期間がいくつあるかを調べたいと考えています。
具体的には、以下の条件をすべて満たす整数の組 (l, r) の個数を求めてください：
- 1 \leq l \leq r \leq N
- r - l + 1 \geq K （期間の長さが K 日以上）
- A_l + A_{l+1} + \cdots + A_r \geq M （期間内の練習強度の合計が M 以上）
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 1 \leq M \leq 10^{14}
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数
入力
N K M A_1 A_2 \cdots A_N
- 1 行目には、練習期間の日数を表す整数 N、期間の長さの最小値を表す整数 K、練習強度の合計の目標値を表す整数 M が、空白区切りで与えられる。
- 2 行目には、各日の練習強度を表す N 個の整数 A_1, A_2, \ldots, A_N が、空白区切りで与えられる。
出力
条件を満たす整数の組 (l, r) の個数を 1 行で出力してください。
入力例 1
5 2 10 3 5 4 2 6
出力例 1
6
入力例 2
8 3 15 2 4 6 3 5 7 1 8
出力例 2
17
入力例 3
10 4 1000000000000 500000000 600000000 400000000 300000000 700000000 200000000 800000000 100000000 900000000 550000000
出力例 3
0
Score : 400 pts
Problem Statement
Takahashi is the manager of the track and field club, and he manages the practice records of the club members.
The track and field club has a practice period of N days, and each day is numbered from 1 to N. On day i (1 \leq i \leq N), a positive integer A_i representing the "practice intensity" for that day is recorded.
According to the club's rules, a period consisting of r - l + 1 consecutive days from day l to day r is called an "achievement period" and is specially recognized if its length is at least K days and the total practice intensity within the period is at least the target value M.
Takahashi wants to find out how many achievement periods qualify for recognition.
Specifically, find the number of integer pairs (l, r) that satisfy all of the following conditions:
- 1 \leq l \leq r \leq N
- r - l + 1 \geq K (the length of the period is at least K days)
- A_l + A_{l+1} + \cdots + A_r \geq M (the total practice intensity within the period is at least M)
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 1 \leq M \leq 10^{14}
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All input values are integers
Input
N K M A_1 A_2 \cdots A_N
- The first line contains an integer N representing the number of days in the practice period, an integer K representing the minimum length of a period, and an integer M representing the target value for the total practice intensity, separated by spaces.
- The second line contains N integers A_1, A_2, \ldots, A_N representing the practice intensity for each day, separated by spaces.
Output
Print the number of integer pairs (l, r) that satisfy the conditions, on a single line.
Sample Input 1
5 2 10 3 5 4 2 6
Sample Output 1
6
Sample Input 2
8 3 15 2 4 6 3 5 7 1 8
Sample Output 2
17
Sample Input 3
10 4 1000000000000 500000000 600000000 400000000 300000000 700000000 200000000 800000000 100000000 900000000 550000000
Sample Output 3
0