1690. 子序列

单点时限: 2.0 sec

内存限制: 256 MB

在一个正整数序列中,找到一个子序列,使它的和超过 $S$,所有这样的子序列中,长度最短的是多少。子序列是相邻的。

输入格式

第一行两个整数 $n$ $(1 \leq n \leq 10^5)$,$S$ $(0 \leq S < \sum a_i)$,分别是序列的个数和上述的 $S$。

第二行有 $n$ 个正整数 $a_1,a_2,\ldots,a_n$ $(0 < a_i < 10^8)$。

输出格式

一个整数 $L$,子序列最短的长度。

样例

Input
3 2
1 2 1
Output
2

23 人解决,77 人已尝试。

36 份提交通过,共有 387 份提交。

6.9 EMB 奖励。

创建: 13 年,1 月前.

修改: 3 年前.

最后提交: 3 周,1 天前.

来源: LSP

题目标签