No.704 Trash Pickup Medium
タグ : / 解いたユーザー数 57
作問者 :
はむこ
/ テスター :
夕叢霧香(ゆうむらきりか)
Problem Statement
There are $n$ pieces of trash in a park.A group of $n$ neighborhood volunteers is going to collect them.
Person $i (0 \le i < n)$ is initially at $(a_i, 0)$. Trash $j (0 \le j < n)$ is initially at $(x_j, y_j)$.
Initially, person $i$ and trash $j$ are sorted along the x-axis direction ($a_0 \le a_1 \le \cdots \le a_{n-1}$, $x_0 \le x_1 \le \cdots \le x_{n-1}$).
The effort for person $i$ to collect all of trash $j$, trash $j+1$, ... trash $i (0 \le j \le i)$ is the Manhattan distance between trash $j$ and person $i$.
Person $i$ cannot collect trash $j > i$. If person $i$ collects no trash, that person's effort is $0$.
Minimize the sum of efforts required to collect all the trash.
Input
n
a_0 a_1 ... a_{n-1}
x_0 x_1 ... x_{n-1}
y_0 y_1 ... y_{n-1}
$1 \le n \le 3\times 10^5$
$0 \le a_i, x_i, y_i \le 10^5 (0 \le i < n)$
$a_0 \le a_1 \le \cdots \le a_{n-1}$
$x_0 \le x_1 \le \cdots \le x_{n-1}$
Output
Print a newline at the end.
Sample
Sample 1
Input
4 0 1 2 3 0 1 2 3 1 1 1 1
Output
4
It is optimal for person $i$ to collect trash $i$.
The Manhattan distance for each piece of trash is $1$, so the answer is the total, $4$.
Sample 2
Input
4 0 1 2 3 0 1 2 3 10 10 10 10
Output
13
It is optimal for person $3$ to collect all the trash. Persons $0, 1, 2$ are idle.
Collecting trash $[0, 3]$ costs the Manhattan distance between trash $0$ and person $3$, so the answer is the Manhattan distance between $(3, 0)$ and $(0, 10)$, $13=|3-0|+|0-10|$.
Sample 3
Input
4 0 1 2 3 0 1 2 3 2 2 2 2
Output
5
It is optimal for person $3$ to collect all the trash. Persons $0, 1, 2$ are idle.
Since person $3$ takes trash $[0, 3]$, the effort is the Manhattan distance between person $3$ and trash $0$. Person 3 is at $(3, 0)$ and trash $0$ is at $(0, 2)$, so the effort is $5=|3-0|+|0-2|$.
Sample 3
Input
10 3251 5690 6665 16359 20099 34165 44782 58006 70432 72049 2772 9289 40088 44279 57294 57580 57685 61437 68039 73446 64849 45751 58453 17408 55499 38832 58870 71951 66081 4577
Output
113920
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。