#P5626. 「一本通 5.5 练习 2」绿色通道

    ID: 4627 传统题 1000ms 256MiB 尝试: 61 已通过: 24 难度: 5 上传者: 标签>难度分类普及+/提高-排序与序列处理二分答案动态规划线性 DP单调队列优化 DPCF1800单调队列/单调栈优化

「一本通 5.5 练习 2」绿色通道

「一本通 5.5 练习 2」绿色通道

题目描述

小 Y 最多用 tt 分钟完成练习册上的部分题目。题目按 11 到 nn 编号,完成第 ii 题需要 aia_i 分钟。每道题要么做完,要么留空。

下标连续且全部留空的若干题组成一个空题段,长度是其中的题数。选择若干题完成,使最长空题段的长度最小。若全部完成,最长空题段的长度为 00。若一题都没有完成,长度为 nn。

输入格式

第一行两个整数 n,tn,t。第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

输出一行一个整数,表示最长空题段能够达到的最小长度。

样例 1

17 11
6 4 5 2 5 3 4 5 2 3 4 5 2 3 6 3 5
3

样例可选第 4,6,10,144,6,10,14 题,总耗时为 1111 分钟。最长空题段有 33 题。

数据范围

对于 60%60\% 的数据,n≤2000n\le2000。

对于全部数据,1≤n≤5×1041\le n\le5\times10^4,1≤ai≤30001\le a_i\le3000,1≤t≤1081\le t\le10^8。