[四川青少年 C++ 算法设计大赛 2024] 4-5 年级组第 5 题

小 X 制定了一个为期 $n$ 天的训练计划。通过合理的规划，预定对于第 $i$ 天，他可以通过训练获得 $a_i$ 的学习值。 但是计划往往赶不上变化，小 X 发现他每天所获得的学习值与他该天的学习状态产生着关联，我们用一个专注度 $S$ 和认真阈值 $m$ 来描述小 X 的学习状态： - $S$ 的初值为 $0$； - 对于任意一天，如果 $S$ 的值大于等于认真阈值 $m$，那么小 X 将会在该天获得双倍的学习值（即 $a_i\times 2$），并使得专注度 $S$ 减半（向下取整）； - 对于任意一天，如果 $S$ 的值小于认真阈值 $m$，那么小 X 只能在该天获得一半的学习值（向下取整，即 $\lfloor \frac{a_i}{2} \rfloor$），并增加相当于 $a_i$ 的专注度。 小 X 想知道 $n$ 天后，他一共可以获得多少学习值。 ## Input 第一行两个整数 $n,m$ 分别表示训练为期的天数和认真阈值。 第二行 $n$ 个空格隔开的数 $a_i$，第 $i$ 个数表示预期的第 $i$ 天的学习值。 ## Output 一行一个整数，表示 $n$ 天后小 X 一共可以获得多少学习值。 [samples] ## Background 第二届四川省青少年 C++ 算法设计大赛小学 4-5 年级组全省总决赛试题。数据为洛谷自造。 ## Note ### 样例解释 - 第一天，$S=0<m$，所以获得 $35$ 学习值，专注度增加 $70$，变为 $70$。 - 第二天，$S=70>m$，所以获得 $60$ 学习值，专注度减少一半，变为 $35$。 - 第三天，$S=35<m$，所以获得 $30$ 学习值，专注度增加 $60$，变为 $95$。 - 第四天，$S=95>m$，所以获得 $80$ 学习值，专注度减少一半，变为 $47$。 - 第五天，$S=47<m$，所以获得 $25$ 学习值，专注度增加 $50$，变为 $97$。 所以，一共获得 $35+60+30+80+25=230$ 学习值。 ### 数据范围及约定 对于 $100\%$ 的数据，$1\leq n\leq 1000$，$1\leq m,a_i\leq 10^6$。