#P4868. 最短子序列

    ID: 4868 传统题 1000ms 128MiB 尝试: 9 已通过: 3 难度: 3 上传者: 标签>动态规划南海区赛训练算法尺取二分答案普及/提高−连续性问题分支结构

最短子序列

题目描述

给长度为 nn 的数组和一个整数 mm,求总和不小于 mm 的连续子序列的最小长度。

输入格式

第一行包含两个整数 nnmm
第二行包含 nn 个整数,表示数组中的元素。

输出格式

输出一个整数,表示满足条件的连续子序列的最小长度。如果不存在这样的子序列,则输出 00

样例

10 15
5 1 3 5 10 7 4 9 2 8
2

样例解释
选择第 44 个数字和第 55 个数字,5+10=15155+10=15 \ge 15,满足条件,并且是最短的满足条件的子序列。

数据范围

  • 10<n<10610 < n < 10^6
  • 0<m<1080 < m < 10^8
  • 数组中的每个数均在 111000010000 之间。