No.705 ゴミ拾い Hard

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 11
作問者 : はむこはむこ / テスター : 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
2 ProblemId : 2113 / 出題時の順位表

問題文

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

人$i (0 \le i < n)$は、始め$(a_i, 0)$にいます。また、ゴミ$j (0 \le j < n)$は、始め$(x_j, y_j)$にあります。
始め、人$i$とゴミ$j$は、x軸方向に整列されています($a_0 \le a_1 \le \cdots \le a_{n-1}$、$x_0 \le x_1 \le \cdots \le x_{n-1}$)

人$i$がゴミ$j$, ゴミ$j+1$, ... ゴミ$i (0 \le j \le i)$の全てを回収するための労力は、ゴミ$j$と人$i$の3-ノルムの3乗です。
点$(x_0, y_0)$と点$(x_1, y_1)$の3-ノルムの3乗とは、$|x_0-x_1|^3+|y_0-y_1|^3$のことです。
人$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 \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}$

出力

答えは32bit整数に収まらない可能性があります。
最後に改行してください。

サンプル

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

人$i$がゴミ$i$を回収するのが最適です。
それぞれのゴミの3-ノルムが$1$なので、合計して$4$が答えです。

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

人$3$がゴミを全て回収するのが最適です。人$0, 1, 2$は暇です。
ゴミ$[0, 3]$を回収には、ゴミ$0$と人$3$の3-ノルムのコストが必要なので、$(3, 0)$と$(0, 10)$の3-ノルム$1027=|3-0|^3+|0-10|^3$が答えです。

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

人$1$がゴミ$0, 1$を回収し、人$3$がゴミ$2, 3$を回収するのが最適です。人$0, 2$は暇です。

サンプル4
入力
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 
出力
296036534625701

答えは32bit整数に収まらない可能性があります。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。