Problem 4135 --D旅途读书

4135: D旅途读书

$INF\%$ 下一题

Description

小麦有一个特殊习惯，会把买回但未阅读的图书按推荐程度从小到大、从左到右摆放，便于自己查找。

今年五一假期，他计划坐高铁出行，随身带了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

• 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

本题记录	用户（点击查看用户）	运行号（点击购买题解）	时间
算法最快[ $2$ ms]	fog_wu123	1194795	2025-05-11 19:56:50
内存最少[ $1192$ KB]	佘福林	1158831	2024-12-24 23:56:50
第一AC	gdfdd	1101856	2024-05-14 13:15:23
第一挑战	gdfdd	1101856	2024-05-14 13:15:23

竞赛编号	竞赛名称	竞赛时间	访问比赛