一种不那么常见的斜率优化形式。
首先贪心部分就不多说了，慢慢证就好。
然后直接上 DP 式子：
设 (f_{i, j}) 表示目前使用了 (i) 次，考虑到了第 (j) 个水池，1 号池的最高水位。
[f_{i,j}= max(frac{f_{i-1,k}+sum(k+1...j)}{j-k+1})
]
然后运用高中数学知识，这个东西等价于点 ((j+1,S_j)) 和点 ((k, S_k - f_{i-1,k})) 形成的直线的斜率，我们的目的是，从一个点集中找出一个点，使得其与定点 ((j+1,s_j)) 斜率最大。这个点显然是点集的凸包上的点。并且对于这道题来说，插入的点横坐标单调递增，决策点也单调递增，因此用单调队列维护凸包即可。
复杂度 (O(n^2))，我也不知道为什么一堆 double 运算的斜率优化 (O(n^2)) 跑 (8000) 的数据能跑这么快。
借助附件给的高精度板子，我成功的打破了 substring 的 (15.15KB) 的代码长度。