logo AlgoBeat OnlineJudge
登录 注册

#215123. 摧毁时间线

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

你是一个在三维空间中的生命。

你的任务是摧毁一维世界的整条时间线。

时间线由 个时刻构成,按顺序编号为 。 为了摧毁时间线,你早已安插了一枚 E.Space 和三个控制器。三个控制器分别叫做 Past,Present 和 Future。

你并没有足够强大的力量,你只能通过随机逐个地移除时刻的方式来完成任务。每个时刻和相邻的时刻都有一定的连结,而改变这样的联系就需要花费与之相关的能量。你需要花费的能量为要移除的时刻和相邻两个时刻中 E.Space 的位置到下一个时刻中对应控制器的位置的平方和。

形式化地,设 E.Space 在第 个时刻的位置为 ,Past 控制器在第 个时刻的位置为 ,Present 控制器在第 个时刻的位置为 ,Future 控制器在第 个时刻的位置为 ,那么移除目前从前往后第 个时刻消耗的能量为 ,其中 表示目前从前往后第 个时刻的编号。特殊地,下标在 之外的所有值视为

在移除一个时刻后,由于强烈的引力,和时刻 相邻的两个时刻会重新靠在一起。

你想知道在运气最不好的情况下,移除整条时间线最多需要多少能量。

输入格式

第一行一个正整数

第二行 个整数,第 个表示

第三行 个整数,第 个表示

第四行 个整数,第 个表示

第五行 个整数,第 个表示

输出格式

一行一个整数,表示答案。

样例

样例输入 1

4
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1

样例输出 1

5

样例输入 2

9
-254 -877 272 404 786 -744 -284 -868 629
10 -396 -329 265 299 377 -607 575 798
-738 -94 -550 -440 -80 -363 -85 -287 377
-99 -401 -304 -344 -995 845 -191 -302 -533

样例输出 2

21474759

样例输入 3

60
429 -821 -652 24 263 -192 918 61 282 -629 -834 495 565 975 863 -207 -825 -783 -352 88 186 332 -750 -243 -697 871 946 658 853 -708 -452 566 171 364 379 630 -545 110 250 861 -838 490 -14 463 479 343 240 940 -935 325 818 -833 611 -419 -4 972 189 120 -592 -241
372 794 673 524 656 -386 -851 -728 -515 -439 -424 -300 -777 117 -731 26 727 -431 -482 -428 970 559 -343 48 -843 -379 -4 -272 767 -742 -280 0 -230 -808 608 23 208 -596 811 -428 -905 -467 208 -929 -374 -110 949 27 201 -823 -552 -105 -47 250 -435 841 879 -128 -245 -100
655 984 -425 -502 -344 415 70 -146 -780 611 272 607 723 -249 -869 -651 598 278 997 223 -336 -633 461 -115 591 892 950 -964 533 401 -986 -641 689 214 539 432 773 -498 -684 -946 -812 -370 -286 -382 46 184 950 151 245 -696 789 -883 493 -321 505 806 624 -551 914 -827
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

样例输出 3

193466852

数据范围与提示

保证

保证所有输入的数的绝对值不超过

子任务 1(7 pts):

子任务 2(11 pts):

子任务 3(13 pts):

子任务 4(22 pts):

子任务 5(22 pts):

子任务 6(25 pts): 无特殊限制。