解説

$K$ を $1$ から順に検証する解法では、 $K$ の最大値が $2 \times 10^9$ であるため間に合いません。

そこで、 $1 \leqq K \leqq 2 \times 10^9$ として $K$ の最小値を二分探索で求める方法を考えます。

ある $K$ の値でドラゴンを討伐出来た時、それ以上の $K$ でもドラゴンを討伐出来る事が保証されているためこの解法で解くことが出来ます。

ただし、一つ注意するべき事として $K$ の値を仮定した際、 $A_i$ の値次第では、ドラゴンに与えるダメージの合計は、$64$ bit整数におさまらない場合があります。

そのため、$64$ bit整数として扱う場合、ドラゴンに与えるダメージがドラゴンの体力を越えた時点で計算を打ち切る等の工夫が必要です。

C++での実装例は以下の通りです。