← 返回题目列表

AtCoder · arc169_b

B. 金额较小的子段

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

分数: 500 点

问题陈述

给你一个正整数 S。 对于正整数序列 x,我们定义 f(x) 如下:

  • 考虑分解 x 分成几个连续的子序列。对于每个连续子序列,其元素之和必须为 最多 S。 这种分解中连续子序列的最小数量是 f(x).

可以证明 的值 f 在此问题的约束下始终是可定义的。

给你一个正整数序列 A=(A_1,A_2,\cdots,A_N)。 求出 的值 \sum_{1 \leq l \leq r \leq N} f((A_l,A_{l+1},\cdots,A_r)).

约束

  • 1 \leq N \leq 250000
  • 1 \leq S \leq 10^{15}
  • 1 \leq A_i \leq \min(S,10^9)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N S
A_1 A_2 \cdots A_N

输出

打印答案。


示例输入 1

3 3
1 2 3

示例输出 1

8

例如,考虑 x=(1,2,3)。分解 (1,2),(3) 满足条件,并且分解为少于两个连续子序列满足条件,所以 f((1,2,3))=2.

下面显示的是可能的 l,r 以及相应的值 f:

  • (l,r)=(1,1): f((1))=1
  • (l,r)=(1,2): f((1,2))=1
  • (l,r)=(1,3): f((1,2,3))=2
  • (l,r)=(2,2): f((2))=1
  • (l,r)=(2,3): f((2,3))=2
  • (l,r)=(3,3): f((3))=1

因此,答案是 1+1+2+1+2+1=8.


示例输入 2

5 1
1 1 1 1 1

示例输出 2

35

示例输入 3

5 15
5 4 3 2 1

示例输出 3

15

示例输入 4

20 1625597454
786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130

示例输出 4

588