本题的超级弱化版：https://qoj.ac/problem/10452

由此可知当 $a<0$ 时，最优解一定在各个二次函数斜率相同的位置取到。

证明：反证法，若将某个函数的取值向左调整 $\varepsilon$，另一个函数的取值向右调整 $\varepsilon$，贡献一定会下降，所以该构造是最优的。

考虑将函数分成 $a<0,a=0,a>0$ 三类。

对于 $a\le 0$：

将斜率从大到小扫描，可以得到一个分 $O(n)$ 段二次函数的 $g(x)$ 表示总用时 $\le x$ 获得的最大收益。

注意 $a=0$ 时同一个斜率对应了多个横坐标，需要特判。

时间复杂度 $O(n\log n)$。

对于 $a>0$：

之前的反证法会失效，但是可以做向左向右的调整可以一直增大贡献，所以最终最多只有一个函数取值在中间，其他函数都取到最小值或最大值。

题目保证了最多只有 $t=18$ 个这样的函数，所以考虑比较暴力的做法。

我们先枚举哪个函数不选，然后枚举剩下的函数的选择情况。发现当不选的函数确定时，这些函数的二次项系数都为定值，两两间只有一个交点，考虑维护上凸壳。

由于需要知道凸壳每段的函数，所以分治构造凸壳，每次归并两侧凸壳，时间复杂度 $O(2^tt^2)$。

最后将凸壳与 $g$ 的分段进行归并，每一段都是二次函数，容易求出最大值，时间复杂度 $O(tn)$。

注意两者都一定要线性归并，否则时间复杂度退化为 $O(2^tt^3+t^2n)$。

总时间复杂度：$O(n\log n+2^tt^2+tn)$。

其他注意事项：

1. 需要使用 $\varepsilon$ 判断等号。

2. 注意到 long double 只有 $20$ 位有效数字，而 $M^2$ 高达 $10^{16}$，本题需要 $10^{-6}$ 的精度，所以可能需要 __float128。