241979 - 最短子段

题目描述

给定一个由 n 个正整数组成的序列 a_1, a_2, ..., a_n,以及一个目标值 S。

序列的连续子段指连续的一段 a_l, a_{l+1}, ..., a_r,其中 1 ≤ l ≤ r ≤ n。这段子段的长度是 r - l + 1,它的和是这一段里所有数之和。注意 l 与 r 可以相等,此时子段只含一个数。

请找出和大于等于 S 的最短连续子段,输出它的长度;如果整个序列所有数之和都小于 S,说明不存在这样的子段,输出 -1。

输入

第一行,两个整数 n、S,分别表示序列长度和目标值。

第二行,n 个整数 a_1, a_2, ..., a_n,表示这个正整数序列。

输出

输出一个整数,表示和大于等于 S 的最短连续子段的长度;若不存在这样的子段,则输出 -1。

样例

输入

6 10
2 3 1 2 4 3

输出

4
说明

对于所有测试数据,都保证:

  • 1 ≤ n ≤ 10^5

  • 1 ≤ a_i ≤ 10^9

  • 1 ≤ S ≤ 10^14

对于部分测试点具体数据描述如下:

  • 测试点 1~3(30 分):n ≤ 200。

  • 测试点 4~7(40 分):n ≤ 5000。

  • 测试点 8~10(30 分):n ≤ 10^5。

标签
题目参数
时间限制 1 秒
内存限制 256 MB
提交次数 8
通过人数 3
金币数量 4 枚
难度 基础


上一题 下一题