分数: 400 分
问题陈述
高桥是田径俱乐部的经理,他管理俱乐部成员的练习记录。
田径俱乐部练习期为 N 天,每天的编号从 1 to N。当天 i (1 \leq i \leq N),一个正整数 记录代表当天“练习强度”的 A_i 。
根据俱乐部规则,一段时间包括 r - l + 1 从当天起连续几天 l 到今天 r 被称为“成就期”,如果其长度至少为 K 天且期间内总练习强度至少为目标值 M.
Takahashi 希望了解有多少个成就时期有资格获得认可。
具体来说,找到整数对的数量 (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
- 第一行包含一个整数 N 代表练习周期的天数,整数 K 表示周期的最小长度,整数 M 代表总练习强度的目标值,以空格分隔。
- 第二行包含 N 整数 A_1, A_2, \ldots, A_N 代表每天的练习强度,以空格分隔。
输出
打印整数对的数量 (l, r) 满足条件,在一行上。
示例输入 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