No.1012 荷物収集
タグ : / 解いたユーザー数 160
作問者 :
otamay6
/ テスター :
sakaki_tohru
問題文
数直線上に$N$ 個の荷物が並んでいます、荷物 $i (1 \le i \le N)$ は位置 $x_i$ にあり、重さは $w_i$ です。
荷物を別の位置に運ぶためには、$\vert$ (移動後の位置) - (移動前の位置) $\vert$ $\times$ (荷物の重さ)と等しいコストが必要です。
$Q$ 個の値 $X_1,X_2,\dots,X_Q$ が与えられます。各 $i(1 \le i \le Q)$ に対して、すべての荷物を位置 $X_i $に運ぶための必要最低限の合計コストをそれぞれ求めて1行ごとに出力してください。
入力
$N\ Q$ $x_1\ w_1$ $x_2\ w_2$ $\vdots$ $x_N\ w_N$ $X_1\ X_2\ \dots\ X_Q$
入力は全て整数で与えられる
$1 \le N,Q \le 10^5$
$1 \le x_i \le 10^9$
$ x_i \neq x_{j}\ (i \neq j)$
$1 \le w_i \le 10^4$
$1 \le X_i \le 10^9$
$ X_i \neq X_{j}\ (i \neq j)$
出力
各 $i(1 \le i \le Q)$ に対して、必要最低限の合計コストをそれぞれ1行ごとに出力してください。
最後に改行してください。
サンプル
サンプル1
入力
2 1 1 10 10 4 5
出力
60
位置1にある荷物を位置5に運ぶのに必要なコストは $(5-1) \times 10 = 40$で、位置10にある荷物を位置5に運ぶのに必要なコストは $(10-5) \times 4 = 20$なので
合計でコストが 60 かかります。
サンプル2
入力
3 3 4 3 9 4 10 10 3 9 10
出力
97 25 22
$Q$ 個の答えはそれぞれ独立に求めてください。
サンプル3
入力
1 3 9 4 3 6 10
出力
24 12 4
サンプル4
入力
10 5 659 6670 2020 3864 2086 2170 2782 600 3304 1393 4274 2995 5534 9315 5845 4033 7859 2981 9532 9707 1993 2759 4455 4812 8723
出力
157522286 142876890 118104646 115125838 170268640
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。