分数: 433 分
问题陈述
高桥有一系列 N 整数 A_1, A_2, \ldots, A_N.
Takahashi 想要从该序列中选择一个连续的区间。具体来说,他选择一对整数 (l, r) (1 \leq l \leq r \leq N)并从 l-第 r-th。 所选间隔的
的 分数 游戏的 定义如下:
f(l, r) = \sum_{i=l}^{r} A_i + (r - l + 1) \times M
即得分为区间内元素之和加上区间长度的乘积 (r - l + 1) 和一个正整数 M.
查找整数对的数量 (l, r) (1 \leq l \leq r \leq N) 使得分数最多为 K.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 10^9
- 1 \leq K \leq 10^{18}
- -10^9 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数。
输入
N M K A_1 A_2 \cdots A_N
- 第一行包含序列的长度 N,得分系数 M,以及分数上限 K,用空格分隔。
- 第二行包含序列的元素 A_1, A_2, \ldots, A_N,用空格分隔。
输出
在一行中打印整数对的数量 (l, r) (1 \leq l \leq r \leq N) 使得分数最多为 K.
示例输入 1
5 2 10 1 3 2 4 1
示例输出 1
9
示例输入 2
7 3 20 -2 5 -1 4 3 -3 2
示例输出 2
22
示例输入 3
10 1000000000 5000000000 100 -500 300 200 -100 400 -200 150 250 -50
示例输出 3
35