← 返回题目列表

AtCoder · awc0003_d

D. 连续练习日

中文机器翻译题面 查看原题

分数: 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