注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "stations.h"。

题目描述

题目译自 2019년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T4 「방송국」

有 $N$ 个广播站，分别是 $s_{1}, s_{2}, \ldots, s_{N}$，它们位于一条直线上。广播站 $s_{i}$ 的位置是正整数 $x_{i}$。你需要为每个广播站 $s_{i}$ 分配广播信号的范围 $r_{i}$。当广播站 $s_{i}$ 进行广播时，距离 $s_{i}$ 不超过 $r_{i}$ 的广播站可以接收到 $s_{i}$ 的广播信号。换句话说，如果广播站 $s_{j}$ 位于闭区间 $\left[ x_{i} - r_{i}, x_{i} + r_{i} \right ]$ 内，那么 $s_{j}$ 就能接收到 $s_{i}$ 的广播信号。

广播站 $s_{i}$ 的广播可以通过 $h - 1$ $(h > 1)$ 个其他广播站传递给广播站 $s_{j}$。也就是说，存在广播站 $s_{i_{1}}, s_{i_{2}}, \ldots, s_{i_{h-1}}$，使得 $s_{i}$ 的广播传递给 $s_{i_{1}}$，每个 $s_{i_{k}}$ 再传递给 $s_{i_{k+1}}$，最后 $s_{i_{h-1}}$ 传递给 $s_{j}$，这样 $s_{i}$ 的广播在 $h$ 次传递内就可以到达 $s_{j}$。当然，当 $h=1$ 时，表示 $s_{i}$ 的广播直接传递给 $s_{j}$。在这些情况下，我们称 $s_{i}$ 的广播在 $h$ 步内传递到了 $s_{j}$。

我们希望选择一个广播站作为 $h$-集中站。这个广播站不进行广播，但必须能够在最多 $h$ 步内接收到其他所有广播站的广播。我们可以将 $h$-集中站的广播信号范围设为 $0$。

当为每个广播站 $s_{i}$ 分配广播范围 $r_{i}$ 时，分配成本定义为广播范围的平方和。也就是说，成本为 $\sum_{i=1}^{N} r_{i}^{2}$。我们将以最小化这个成本来分配广播范围。如果广播站 $s$ 作为 $h$-集中站时的最小分配成本为 $C_{h}^{*}(s)$，那么问题的目标就是在所有可能的 $h$-集中站 $s$ 中，找到具有最小 $C_{h}^{*}(s)$ 的那个，以及给出导致该最小成本的广播范围分配。

给定 $N$ 个广播站的位置，对于每个 $h=1, 2, \ldots, N-1$，编写一个程序，输出所有可能的 $h$-集中站 $s$ 的最小分配成本 $C_{h}^{*}(s)$ 中的最小值。

例如，下面的图 1 和图 2 是 $5$ 个广播站 $s_{1}, \ldots, s_{5}$，它们分别位于坐标 $1, 3, 4, 6, 9$，当 $h=2$ 时的情况。

• 在图 1 中，当为 $s_{1}, s_{2}, s_{3}, s_{4}$ 分别分配广播范围 $3, 1, 5, 2$，且 $s_{5}$ 作为 $2$-集中站时，最小成本为 $39$。
• 在图 2 中，当为 $s_{1}, s_{2}, s_{4}, s_{5}$ 分别分配广播范围 $2, 1, 2, 3$，且 $s_{3}$ 作为 $2$-集中站时，最小成本为 $18$。

因此，$18$ 是所有可能的 $2$-集中站的最小成本中的最小值。

图 1

图 2

你需要为管理员实现以下一个函数：

• void stations(int N, int X[]);
  接受广播站的数量 N 和每个广播站的位置 X[0..N-1] 作为参数。其中，X[] 是大小为 N 的向量（vector），X[i] 的值互不相同，且按升序存储。

你需要在 stations() 函数中使用以下函数来提交答案：

• void answer(long long Y[]);
  这是一个提交大小为 N - 1 的向量 Y[] 的函数。对于 $i = 0, \ldots, N - 2$，Y[i] 的值是所有可能的 $(i + 1)$-集中站的最小成本的最小值。这个函数必须在 stations() 函数中且只能被调用一次。

实现细节

你需要提交一个名为 stations.cpp 的文件。该文件必须实现以下函数：

void stations(int N, int X[]);

该函数必须按照上述描述进行操作。当然，你可以创建和使用其他函数，但不得进行任何输入输出操作或访问其他文件。

示例评测程序

示例评测程序按照以下格式读取输入：

• 第 $1$ 行：$N$，其中 $N$ 表示广播站的数量
• 第 $2$ 行：$N$ 个整数 $x_{1}\,x_{2}\,\cdots\,x_{N}$ ，其中 $x_{i}$ 为广播站的位置

示例评测程序对于每个 $i = 1, \ldots, N - 1$，在第 $i$ 行输出所有可能的 $i$-集中站的最小成本的最小值。

3
1 3 8

29
29

5
1 3 4 6 9

39
18
18
18

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 120$
• $1 \leq x_{1} < x_{2} < \cdots < x_{N} \leq 10^{8}$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$11$	$N \leq 7$
$2$	$21$	$N \leq 30$
$3$	$17$	$N \leq 60$
$4$	$51$	无附加限制