AtCoder AGC 011 B - Colorful Creatures

$A_i$ を降順にソートしても一般性を失わない。

大きいものの方が吸収しづらいから、1番最後に $1$ , その前に $2, \ldots,$ を吸収したとして良い。 $A_1, \ldots, A_i$ を吸収するのに必要な最小のとなる生き物の大きさの整数値を $B_i$ とする。

$B_1 = \lceil A_1 / 2\rceil$ である。 $A_i$ が吸収でき、さらにその後 $i-1, \ldots, 1$ が吸収できる条件を考えると、 $B_i = \max(\lceil A_i / 2 \rceil, B_{i-1}-A_i)$ である。

各 $i$ に対し、 $i$ は $i+1$ 以降を吸収できるから、 $\sum_{k=i}^n A_k \ge B_{i-1}$ を満たすかどうか判定すれば良い。