No.1012 Package Collection
タグ : / 解いたユーザー数 167
作問者 :
otamay6
/ テスター :
sakaki_tohru
Problem Statement
There are $N$ packages on a number line. Package $i (1 \le i \le N)$ is at position $x_i$ and has weight $w_i$.
Carrying a package to another position costs $\vert$ (position after moving) - (position before moving) $\vert$ $\times$ (weight of the package).
You are given $Q$ values $X_1,X_2,\dots,X_Q$. For each $i(1 \le i \le Q)$, find the minimum total cost required to carry all the packages to position $X_i $, and print each answer on its own line.
Input
$N\ Q$ $x_1\ w_1$ $x_2\ w_2$ $\vdots$ $x_N\ w_N$ $X_1\ X_2\ \dots\ X_Q$
All input values are integers.
$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)$
Output
For each $i(1 \le i \le Q)$, print the minimum total cost required, each on its own line.
Print a newline at the end.
Sample
Sample 1
Input
2 1 1 10 10 4 5
Output
60
The cost to carry the package at position 1 to position 5 is $(5-1) \times 10 = 40$, and the cost to carry the package at position 10 to position 5 is $(10-5) \times 4 = 20$, so
the total cost is 60.
Sample 2
Input
3 3 4 3 9 4 10 10 3 9 10
Output
97 25 22
Find each of the $Q$ answers independently.
Sample 3
Input
1 3 9 4 3 6 10
Output
24 12 4
Sample 4
Input
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
Output
157522286 142876890 118104646 115125838 170268640
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。