https://atcoder.jp/contests/agc011/tasks/agc011_b
\(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} \) を満たすかどうか判定すれば良い。