CF1703G Good Key, Bad Key

题目描述

你有 $n$ 个箱子。第 $i$ 个箱子中有 $a_i$ 个硬币。你需要按照从箱子 $1$ 号到箱子 $n$ 号的顺序打开所有 $n$ 个箱子。 你可以用以下两种钥匙之一打开一个箱子: - 好钥匙:使用一次消耗 $k$ 个硬币。 - 坏钥匙:使用时不消耗硬币,但会使所有未打开的箱子中的硬币数减半(包括正要打开的这个箱子)。硬币减半时向下取整。比如,用坏钥匙打开箱子 $i$ 号时,$a_i=a_i/2$,$a_{i+1}=a_{i+1}/2$,$......$,$a_n=a_n/2$。 所有钥匙用过一次就会断掉(别想着买一把好钥匙开完所有箱子了),好钥匙需要重复付费,坏钥匙效果会重复计算。 也就是说,你总共需要使用 $n$ 把钥匙,每个箱子用一把。开始时,你没有硬币和钥匙,如果想用好钥匙,你就得去买。值得注意的是,在这个过程中你可以赊账买钥匙;例如,如果你只有 $1$ 个硬币,你也可以购买价值 $k=3$ 个硬币的好钥匙,你的余额会变成 $-2$ 个硬币。 你需要求出开完所有箱子之后你能获得的最大硬币数量(显然大于等于 $0$ )。

输入格式

输出格式

说明/提示

In the first test case, one possible strategy is as follows: - Buy a good key for $ 5 $ coins, and open chest $ 1 $ , receiving $ 10 $ coins. Your current balance is $ 0 + 10 - 5 = 5 $ coins. - Buy a good key for $ 5 $ coins, and open chest $ 2 $ , receiving $ 10 $ coins. Your current balance is $ 5 + 10 - 5 = 10 $ coins. - Use a bad key and open chest $ 3 $ . As a result of using a bad key, the number of coins in chest $ 3 $ becomes $ \left\lfloor \frac{3}{2} \right\rfloor = 1 $ , and the number of coins in chest $ 4 $ becomes $ \left\lfloor \frac{1}{2} \right\rfloor = 0 $ . Your current balance is $ 10 + 1 = 11 $ . - Use a bad key and open chest $ 4 $ . As a result of using a bad key, the number of coins in chest $ 4 $ becomes $ \left\lfloor \frac{0}{2} \right\rfloor = 0 $ . Your current balance is $ 11 + 0 = 11 $ . At the end of the process, you have $ 11 $ coins, which can be proven to be maximal.