問題一覧 > 通常問題

No.704 Trash Pickup Medium

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 57
作問者 : はむこ / テスター : 夕叢霧香(ゆうむらきりか)
お気に入りにしたユーザー ProblemId : 1950 / 自分の提出
問題文最終更新日: 2026-06-25 01:33:23
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 193 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。