← 返回题目列表

AtCoder · awc0027_e

E. 连续间隔的选择

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

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