Problem D: D旅途读书

"
Time Limit $1$ 秒/Second(s) Memory Limit $128$ 兆字节/Megabyte(s)
提交总数 $0$ 正确数量 $7$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
小麦有一个特殊习惯,会把买回但未阅读的图书按推荐程度从小到大、从左到右摆放,便于自己查找。
今年五一假期,他计划坐高铁出行,随身带了n本图书放在小桌板上,他计划在高铁上花t分钟读书。对
于携带的每本图书,他可以完全读完(花费a分钟)或者仅读目录(花费b分钟)。他将从最左边的图书
读起,之后读相邻摆放的下一本书。阅读后,小麦的书卷气会增加,增加值等于他完整读过图书的推荐
度之和。
现请你帮小麦计算,在t分钟后,他能获得的书卷气最大值是多少?
输入的第1行包括4个整数n, t, a, b,依次表示图书的数量、阅读时间、读完整本书的时间和只读目录的时
间。
第2行包含n个整数,其中第i个整数ki表示从左到右第i本图书的推荐程度。
输出1行1个整数,表示t分钟后,小麦书卷气增加的最大值。
3 5 2 1
2 2 5
7
• 1 ≤ n ≤ 2 × 105
• 1 ≤ t ≤ 109
• 1 ≤ b ≤ a ≤ 109
• 1 ≤ ki ≤ 109
• ki ≤ ki+1, i = 1, 2, . . . , n − 1
• 有40%的数据,n, t ≤ 1000