← 返回题目列表

AtCoder · abc130_d

D. 足够的阵列

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

分数: 400 点

问题陈述

给定一个长度为正整数的序列 N, A=a_1,a_2,…,a_{N},和一个整数 K。 有多少个连续的子序列 A 满足以下条件?

  • (条件)连续子序列中的元素之和至少为 K.

如果两个连续的子序列源自不同的位置,我们认为它们是不同的 A,即使它们的内容相同。

请注意,答案可能不适合 32- 位整数类型。

约束

  • 1 \leq a_i \leq 10^5
  • 1 \leq N \leq 10^5
  • 1 \leq K \leq 10^{10}

输入

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

N K
a_1 a_2 ... a_N

输出

打印连续子序列的数量 A 满足条件。


示例输入 1

4 10
6 1 2 7

示例输出 1

2

以下两个连续的子序列满足条件:

  • A[1..4]=a_1,a_2,a_3,a_4,总和 16
  • A[2..4]=a_2,a_3,a_4,总和 10

示例输入 2

3 5
3 3 3

示例输出 2

3

再次注意,如果两个连续的子序列源自不同的位置,即使它们的内容相同,我们也认为它们是不同的。


示例输入 3

10 53462
103 35322 232 342 21099 90000 18843 9010 35221 19352

示例输出 3

36