你被任命执行一项非常重要的任务:你负责平整一条特定的道路。
道路可以表示为一条从 $$$(0, 0)$$$ 开始,到 $$$(n - 1, 0)$$$ 结束并由 $$$n$$$ 个顶点(包括起点和终点)组成的折线。折线第 $$$i$$$ 顶点的坐标为 $$$(i, a_i)$$$。
“展平”道路相当于从 $$$(0, y_0)$$$ 到 $$$(n - 1, y_1)$$$ 选择一些线段,使得折线的所有点都位于所选线段下方(或处于相同高度)。值 $$$y_0$$$ 和 $$$y_1$$$ 可能是实数。
您可以想象这条路有一些斜坡和坑,然后您开始在上面浇筑人行道,直到道路平坦。点 $$$0$$$ 和 $$$n - 1$$$ 具有无限高的墙,因此路面不会掉出线段 $$$[0, n - 1]$$$。
平整道路的成本等于所选路段和折线之间的面积。你想要最小化成本,这就是为什么平坦的道路不一定是水平的。
但是有一个问题:你的数据可能太旧了,所以你派了一个人去测量新的高度。该人从 $$$0$$$ 到 $$$n - 1$$$ 并向您发送折线每个顶点 $$$i$$$ 的新高度 $$$b_i$$$。
由于测量新高度可能需要一段时间,并且您不知道何时会被问到,因此请在获得每个新高度 $$$b_i$$$ 后计算平整道路的最低成本(以及相应的 $$$y_0$$$ 和 $$$y_1$$$)。
输入
第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 折线的顶点数。
第二行包含 $$$n$$$ 整数 $$$a_0, a_1, \dots, a_{n - 1}$$$ ($$$0 \le a_i \le 10^9$$$; $$$a_0 = a_{n - 1} = 0$$$) — 相应顶点的高度。
第三行包含 $$$n$$$ 整数 $$$b_0, b_1, \dots, b_{n - 1}$$$ ($$$0 \le b_i \le 10^9$$$; $$$b_0 = b_{n - 1} = 0$$$) — 相应顶点的新高度。
输出
打印 $$$n$$$ 数字:如果您已经知道实际高度 $$$b_0, \dots, b_i$$$,则作为第 $$$i$$$ 个数字($$$0$$$ 索引)打印“最佳段”的 $$$y_0 + y_1$$$(即给出最小成本的段的坐标总和)。
如果有多个“最佳段”,则打印其中可能的最小 $$$y_0 + y_1$$$。
如果您的答案的绝对或相对误差不超过 $$$10^{-9}$$$,则视为正确。
正式来说,让您的答案为$$$x$$$,陪审团的答案为$$$y$$$。当且仅当 $$$\frac{|x - y|}{\max{(1, |y|)}} \le 10^{-9}$$$ 时,您的答案才会被接受。
示例
输入 #1
5 0 5 1 3 0 0 1 3 2 0
输出 #1
8.000000000000 4.000000000000 6.000000000000 6.000000000000 6.000000000000
输入 #2
6 0 4 1 3 3 0 0 1 4 0 1 0
输出 #2
7.000000000000 5.000000000000 7.500000000000 7.500000000000 6.666666666667 6.666666666667
注意
第一个例子中的第一个答案如上图所示。
您可以通过以下“最佳片段”获得第二个答案:
您可以使用以下“最佳片段”获得第三个答案:
您可以通过如下所示的“最佳片段”来获得第四个答案: