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

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

题目背景

第二届四川省青少年 C++ 算法设计大赛小学 4-5 年级组全省总决赛试题。数据为洛谷自造。

题目描述

小 X 制定了一个为期 nn 天的训练计划。通过合理的规划,预定对于第 ii 天,他可以通过训练获得 aia_i 的学习值。

但是计划往往赶不上变化,小 X 发现他每天所获得的学习值与他该天的学习状态产生着关联,我们用一个专注度 SS 和认真阈值 mm 来描述小 X 的学习状态:

  • SS 的初值为 00
  • 对于任意一天,如果 SS 的值大于等于认真阈值 mm,那么小 X 将会在该天获得双倍的学习值(即 ai×2a_i\times 2),并使得专注度 SS 减半(向下取整);
  • 对于任意一天,如果 SS 的值小于认真阈值 mm,那么小 X 只能在该天获得一半的学习值(向下取整,即 ai2\lfloor \frac{a_i}{2} \rfloor),并增加相当于 aia_i 的专注度。

小 X 想知道 nn 天后,他一共可以获得多少学习值。

输入格式

第一行两个整数 n,mn,m 分别表示训练为期的天数和认真阈值。

第二行 nn 个空格隔开的数 aia_i,第 ii 个数表示预期的第 ii 天的学习值。

输出格式

一行一个整数,表示 nn 天后小 X 一共可以获得多少学习值。

5 50
70 30 60 40 50
230

提示

样例解释

  • 第一天,S=0<mS=0<m,所以获得 3535 学习值,专注度增加 7070,变为 7070
  • 第二天,S=70>mS=70>m,所以获得 6060 学习值,专注度减少一半,变为 3535
  • 第三天,S=35<mS=35<m,所以获得 3030 学习值,专注度增加 6060,变为 9595
  • 第四天,S=95>mS=95>m,所以获得 8080 学习值,专注度减少一半,变为 4747
  • 第五天,S=47<mS=47<m,所以获得 2525 学习值,专注度增加 5050,变为 9797

所以,一共获得 35+60+30+80+25=23035+60+30+80+25=230 学习值。

数据范围及约定

对于 100%100\% 的数据,1n10001\leq n\leq 10001m,ai1061\leq m,a_i\leq 10^6