様々な解法があると思いますが、ここではその一つを紹介します。


小さいものから順に数を確定させていきます。

iiについて、現在t×Ait\times A_iがまだ確定していないような最小の正整数tttit_iとします。次に確定させる数の候補はti×Ai(1iN)t_i\times A_i(1\leq i\leq N)であるのでmini(ti×Ai)\min_i(t_i\times A_i)を確定させ、titi+1t_i\leftarrow t_i+1としながらKK個の数が確定するまで繰り返していけばよいです。

次に確定させる数の候補を優先度付きキュー(ヒープ)で管理しながら確定させていきます。 入力例1だと優先度付きキューの中身は以下のようになります。

{3,5,7}3確定{6,5,7}5確定{6,10,7}6確定{9,10,7}7確定{9,10,14}9確定{12,10,14}10確定{12,15,14}12確定{15,15,14}14確定{15,15,21}15確定{18,20,21}18確定{21,20,21}\{3,5,7\}\underset{3確定}{\longrightarrow}\{6,5,7\}\underset{5確定}{\longrightarrow}\{6,10,7\}\underset{6確定}{\longrightarrow}\{9,10,7\}\underset{7確定}{\longrightarrow}\\ \{9,10,14\}\underset{9確定}{\longrightarrow}\{12,10,14\}\underset{10確定}{\longrightarrow}\{12,15,14\}\underset{12確定}{\longrightarrow}\{15,15,14\}\underset{14確定}{\longrightarrow}\\ \{15,15,21\}\underset{15確定}{\longrightarrow}\{18,20,21\}\underset{18確定}{\longrightarrow}\{21,20,21\}