题解

思路

一个箱子中的硬币数只取决于此前用了多少次坏钥匙。若此前用了 $j$ 次坏钥匙，则当前能看到的硬币数为 $\left\lfloor a_i/2^j\right\rfloor$。因此可以把“已使用的坏钥匙次数”作为状态。

由于 $a_i\le 10^9$，坏钥匙使用约三十次后，任何箱子的贡献都已经变成零。此后继续区分更大的次数没有意义，可以把这些状态合并。

做法

设状态值表示处理完一个前缀、已经使用若干次坏钥匙时的最大余额。处理下一个箱子时有两种转移：使用好钥匙，获得当前折半后的硬币并支付 $k$；使用坏钥匙，折半次数加一，并获得再次折半后的当前硬币。

初始时只有“使用零次坏钥匙”的状态为零。依次处理全部箱子，最后取所有状态的最大值。为避免无意义的状态增长，把折半次数在 $31$ 处合并。

正确性来自逐箱决策的完备枚举：任意合法方案在每个箱子恰好选择一种钥匙，转移分别覆盖这两种选择；状态保留同一折半次数下的最大余额不会损失未来最优方案。超过合并阈值后所有后续硬币贡献均为零，合并也不改变答案。

复杂度

每个箱子只处理常数个折半状态。每个测试用例的时间复杂度为 $O(n\log A)$，空间复杂度为 $O(\log A)$，其中 $A=10^9$。