TCO2013 Round1C Div1 500

問題

プログラミングコンテストをやっている。
部屋がn+1部屋あって、0〜n-1までの番号の部屋にはそれぞれ何人か人がいる。
自分はn番の部屋に1人でいて、ほかの部屋の人数は知ることはできない。
各部屋のスコアの合計点数の配列が与えられる。
今、自分より上位がk人以下になるようにしたい。

このとき、自分は最低何点スコアをとれば、満たせるか。

考え方

自分があるスコアの時、他の部屋で、自分より点数が高い人が何人いるかは、
その部屋の合計スコア/(自分のスコア+1)
で求められるので、すべての部屋で人数を計算できる。

スコアは結構大きい値をとるので、二分探索で調べる。

反省

すべての人が1点だった場合で、kがそれ以上の値だった場合、上げる必要がないので、0を返すようにしたが、1部屋当たり10^9で47部屋あるので、オーバーフローしてしまった。