問題一覧 > 通常問題

No.704 ゴミ拾い Medium

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 49
作問者 : はむこ / テスター : 夕叢霧香(ゆうむらきりか)
3 ProblemId : 1950 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-06-15 22:44:49

問題文

公園にn個のゴミがあります。
これを、n人の町内ボランティアで回収しようとしています。

人i(0≤i<n)は、始め(ai,0)にいます。また、ゴミj(0≤j<n)は、始め(xj,yj)にあります。
始め、人iとゴミjは、x軸方向に整列されています（a0≤a1≤⋯≤an−1、x0≤x1≤⋯≤xn−1）

人iがゴミj, ゴミj+1, ... ゴミi(0≤j≤i)の全てを回収するための労力は、ゴミjと人iのマンハッタン距離です。
人iは、ゴミj>iを回収できません。人iがゴミを回収しない場合は、その人の労力は0です。

全てのゴミを回収するための、労力の和を最小化してください。

入力

n
a_0 a_1 ... a_{n-1}
x_0 x_1 ... x_{n-1}
y_0 y_1 ... y_{n-1}

1≤n≤3×105
0≤ai,xi,yi≤105(0≤i<n)
a0≤a1≤⋯≤an−1
x0≤x1≤⋯≤xn−1

出力

最後に改行してください。

サンプル

サンプル1
入力
4
0 1 2 3
0 1 2 3
1 1 1 1
出力
4

人iがゴミiを回収するのが最適です。
それぞれのゴミのマンハッタン距離が1なので、合計して4が答えです。

サンプル2
入力
4
0 1 2 3
0 1 2 3
10 10 10 10
出力
13

人3がゴミを全て回収するのが最適です。人0,1,2は暇です。
ゴミ[0,3]を回収には、ゴミ0と人3のマンハッタン距離のコストが必要なので、(3,0)と(0,10)のマンハッタン距離13=|3−0|+|0−10|が答えです。

サンプル3
入力
4
0 1 2 3
0 1 2 3
2 2 2 2
出力
5

人3がゴミを全て回収するのが最適です。人0,1,2は暇です。
人3がゴミ[0,3]を取るので、人3とゴミ0のマンハッタン距離の労力がかかります。人3が(3,0)、ゴミ0が(0,2)にあるので、労力は5=|3−0|+|0−2|です。

サンプル3
入力
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
出力
113920

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。