公式解説と同様に、答えを格納する配列\(\mathrm{ans}\)を持ちます。ただし、\(\mathrm{ans}[0]=0\)とします。

\(\mathrm{ans}[0],\mathrm{ans}[1],\ldots,\mathrm{ans}[i-1]\)が既にわかっているとき、\(\mathrm{ans}[i]\)を高速に求める方法について考えます。 \(\mathrm{ans}[i]\)は、\(\mathrm{ans}[0],\mathrm{ans}[1],\ldots,\mathrm{ans}[i-1]\)と\(A_1,A_2,\ldots,A_N\)からそれぞれ要素をひとつずつえらんで足したもののうち、\(\mathrm{ans}[i-1]\)より大きいものの中での最小の値です。

ここで、足す\(A_j\)を固定すると、\(\mathrm{ans}[0],\mathrm{ans}[1],\ldots,\mathrm{ans}[i-1]\)の中で\(A_j\)を足して\(\mathrm{ans}[i-1]\)より大きくなるような最小の値は、（\(\mathrm{ans}\)は昇順に並んでいるので）二分探索により求めることができます。

よって、各\(j\)について\(\mathrm{ans}[k]+A_j>\mathrm{ans}[i-1]\)を満たす最小の\(\mathrm{ans}[k]\)を求め、各\(\mathrm{ans}[k]+A_j\)のうちの最小値をとれば、\(\mathrm{ans}[i]\)を\(\Omicron(N\log K)\)で求めることができます。

したがって、\(i=1,2,\ldots,K\)について上記の操作により\(\mathrm{ans}[i]\)を順に求めれば、全体で\(\Omicron(NK\log K)\)でこの問題を解くことができます。