No.2008 Super Worker
タグ : / 解いたユーザー数 151
作問者 :
Kiri8128
/ テスター :
Kazun
問題文
きりさんはアルバイトをしています。最初、きりさんのバイトレベルは $1$ です。 $N$ 件の仕事があり、これらを好きな順番ですべて引き受けることにしました。 バイトレベルが $x$ のときに $i\ (1 \le i \le N)$ 番目の仕事をすると、給料が $A_i \cdot x$ もらえて、その後バイトレベルが $B_i \cdot x$ になります。 得られる給料の合計の最大値はいくらでしょうか。答えを $10^9+7$ で割った余りを出力してください。
入力
$N$ $A_1\ A_2\ \cdots A_N$ $B_1\ B_2\ \cdots B_N$
$1 \le N \le 2 \times 10^5$
$1 \le A_i,\ B_i \le 10^6\ (1 \le i \le N)$
入力はすべて整数
出力
得られる給料の合計の最大値を $10^9+7$ で割った余りを出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2 30 20 2 3
出力
110
【$1$ 番目の仕事を先にする場合】
$1$ 番目の仕事で $30$ 、 $2$ 番目の仕事で $40$ 、合計 $70$ の給料を得ることができます。
【$2$ 番目の仕事を先にする場合】
$2$ 番目の仕事で $20$ 、 $1$ 番目の仕事で $90$ 、合計 $110$ の給料を得ることができます。
よって得られる金額の最大値は $110$ です。
サンプル2
入力
2 7000 1000000 1000000 1
出力
0
$10^9+7$ で割った余りを出力することに注意してください。
サンプル3
入力
8 3 14 15 92 65 35 89 79 2 7 1 8 2 8 1 8
出力
2048669
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。