下面给出一种精确的连续动态规划做法。整条道路虽然是连续的，但由于雪厚只在给出的分段上发生变化，所有需要维护的函数都可以表示成分段二次函数。

先做一些记号。设 $P(x)$ 表示 $[0,x]$ 内雪的总体积，$Q(x)$ 表示 $[0,x]$ 内雪量按位置加权后的总和。二者都可以按分段递推计算。若 $x$ 落在第 $i$ 段，即 $r_{i-1}\le x\le r_i$，则 $P(x)=P(r_{i-1})+a_i(x-r_{i-1})$，$Q(x)=Q(r_{i-1})+\frac{a_i(x^2-r_{i-1}^2)}2$。

如果把区间 $[l,r]$ 的所有雪都推到 $r$，费用可以写成 $C(l,r)=r(P(r)-P(l))-(Q(r)-Q(l))$。这个式子的含义是：每一小段雪的移动距离都是“终点位置 $r$ 减去它原来的位置”，把所有雪的贡献加起来，就得到上式。

由于推雪车只从左向右运动，每个洞只会接收它左侧直到上一个洞之间的一整段雪。因此任意方案等价于把整条道路划分成若干连续段，每段的雪都推入该段右端点的洞中。多余的洞可以与已有洞重合，所以“恰好 $k$ 个洞”和“至多 $k$ 个有效洞”的最优值相同。

令 $dp_j(x)$ 表示用 $j$ 个洞清理 $[0,x]$，且第 $j$ 个洞放在 $x$ 的最小费用。考虑上一个洞的位置 $y$，就有 $dp_j(x)=\min_{0\le y\le x}{dp_{j-1}(y)+C(y,x)}$。

代入 $C(y,x)$ 后得到 $dp_j(x)=xP(x)-Q(x)+\min_{0\le y\le x}{dp_{j-1}(y)+Q(y)-xP(y)}$。直接在原坐标 $x$ 上处理比较麻烦，因为最优洞位可能落在某个原始分段内部。

接下来把坐标从“道路位置”换成“累计雪量”。因为所有 $a_i>0$，所以 $P(x)$ 严格递增。令 $X(u)$ 表示累计雪量达到 $u$ 时对应的道路位置，设 $M=P(r_n)$，并记 $J(u)=Q(X(u))$。在累计雪量坐标下，第 $i$ 段对应区间 $[S_{i-1},S_i]$，其中 $S_i=P(r_i)$。

在第 $i$ 段上，雪厚为常数，因此 $X(u)$ 是一次函数：$X(u)=\alpha_i u+\beta_i$，其中 $\alpha_i=\frac1{a_i}$，$\beta_i=r_{i-1}-\frac{S_{i-1}}{a_i}$。

令 $H_j(u)=dp_j(X(u))+J(u)$。把 $x=X(u),y=X(s)$ 代入上面的 DP，可以得到 $H_j(u)=uX(u)+\min_{0\le s\le u}{H_{j-1}(s)-X(u)s}$。初始时 $H_1(u)=uX(u)$。由于 $X(u)$ 分段一次，所以 $H_1(u)$ 是分段二次函数。

下面把转移中的前缀限制去掉。定义 $E_j(x)=\min_{0\le s\le M}{H_j(s)-xs}$。计算 $H_{j+1}(u)$ 时，原本的限制 $s\le u$ 不会影响最优值。

直观地说，若 $s>u$，那么 $s$ 对应的位置 $X(s)$ 不在 $X(u)$ 左侧，不可能作为清理到 $X(u)$ 时的上一个分界点。形式化地看，可以维护这样一个性质：对任意 $s\ge u$，都有 $H_j(s)-H_j(u)\ge X(u)(s-u)$。初始 $H_1(u)=uX(u)$ 时，这个性质由 $X(s)\ge X(u)$ 直接得到。每次转移后，新函数仍然由若干二次片段拼成，且各片段的斜率下界仍不小于对应的 $X(u)$，所以该性质可以逐层保持。于是当 $s\ge u$ 时，$H_j(s)-X(u)s\ge H_j(u)-X(u)u$，最小值不会出现在 $s>u$。

因此可以写成 $H_{j+1}(u)=uX(u)+E_j(X(u))$。这样每一层转移就变成了完整的函数变换。

下面考虑一个二次片段对 $E(x)$ 的贡献。假设上一层某个片段为 $q(u)=au^2+bu+c$，定义域为 $u\in[L,R]$。它对 $E(x)=\min_u(H(u)-xu)$ 的贡献为 $e(x)=\min_{u\in[L,R]}{q(u)-xu}$。

若 $a>0$，那么 $q(u)-xu$ 是一个开口向上的二次函数。它不考虑区间限制时的最低点在 $u_0=\frac{x-b}{2a}$，限制到 $[L,R]$ 后，$e(x)$ 是三段函数。记 $g_L=2aL+b$，$g_R=2aR+b$，则

$$e(x)= \begin{cases} q(L)-Lx,&x\le g_L,\ c-\dfrac{(x-b)^2}{4a},&g_L\le x\le g_R,\ q(R)-Rx,&x\ge g_R. \end{cases}$$

若 $a\le0$，最低值只会在端点取得，即 $e(x)=\min{q(L)-Lx,\ q(R)-Rx}$，也就是两条直线的下包络。我们把这样由一个二次片段产生的函数称为一个 bundle。

将 $H_j$ 的片段按 $u$ 从左到右排序。若两个片段对应区间分别为 $[L_1,R_1]$ 和 $[L_2,R_2]$，且 $R_1\le L_2$，那么第一个 bundle 由更小的 $u$ 区间产生，第二个 bundle 由更大的 $u$ 区间产生。随着 $x$ 增大，较大的 $u$ 会更占优势，因此两个 bundle 的优劣关系只会改变一次。

所以可以像维护单调凸包一样，用栈维护当前下包络。按顺序插入新的 bundle，与栈顶求第一次交点；如果交点不在栈顶的生效区间右侧，就弹出栈顶；否则新 bundle 从这个交点开始生效。每个 bundle 进栈、出栈至多一次，所以一层下包络可以线性构造。

两个 bundle 都可以拆成不超过三段“直线 / 二次 / 直线”。求交时只需合并这些内部断点，在常数个区间内解一次一次方程或二次方程，因此单次求交是 $O(1)$。

已知 $H_{j+1}(u)=uX(u)+E_j(X(u))$，而 $X(u)$ 分段一次。若 $X(u)=\alpha u+\beta$，且某段 $E_j$ 为 $E_j(x)=px^2+qx+r$，代入可得 $H_{j+1}(u)=u(\alpha u+\beta)+p(\alpha u+\beta)^2+q(\alpha u+\beta)+r$，仍然是关于 $u$ 的二次函数。

因此只需要把 $X$ 的分段边界和 $E_j$ 的分段边界用双指针归并，就可以得到下一层 $H$。

整个算法如下。先计算 $S_i=P(r_i)$，并构造 $X(u)$ 的所有分段；然后初始化 $H_1(u)=uX(u)$。对于 $j=1,2,\ldots,k-1$，先由 $H_j$ 的二次片段生成所有 bundle，再用单调栈求出 $E_j(x)=\min_u(H_j(u)-xu)$ 的精确下包络，最后将 $E_j(X(u))$ 与 $uX(u)$ 归并生成 $H_{j+1}$。最终由 $dp_k(r_n)=H_k(M)-Q(r_n)$ 得到答案。

正确性可以从下面几点理解。推雪车只从左向右移动，雪遇到右侧第一个洞后立即消失，不会越过该洞，所以每个洞接收一段连续区间内的雪，所有洞自然形成一组连续划分。考虑最后一个洞在 $x$，倒数第二个洞在 $y$，则 $[0,y]$ 的最优费用为 $dp_{j-1}(y)$，$[y,x]$ 的费用为 $C(y,x)$，枚举所有 $y$ 即得到 DP。

换到累计雪量坐标后，由 $x=X(u),y=X(s)$，以及 $P(X(u))=u$、$Q(X(u))=J(u)$，可以得到 $H_j(u)=uX(u)+\min_{0\le s\le u}{H_{j-1}(s)-X(u)s}$。又因为对 $s\ge u$ 有 $H_j(s)-H_j(u)\ge X(u)(s-u)$，所以约束 $s\le u$ 可以去掉。一个二次片段产生的 bundle 来自区间限制下的一元二次函数最小化；按 $u$ 顺序生成的 bundle 至多两两相交一次，因此单调栈求出的下包络是精确的。于是每一层函数转移都被精确构造，最终输出 $H_k(M)-Q(r_n)$，也就是最小清雪费用。

复杂度方面，设第 $j$ 层分段数为 $m_j$。由 $E_j$ 和 $X$ 归并生成 $H_{j+1}$ 时，分段数至多增加 $O(n)$，因此 $m_j=O(jn)$。每一层从 $H_j$ 构造 $E_j$，以及从 $E_j$ 构造 $H_{j+1}$，都是线性的，所以总时间复杂度为 $O(k^2n)$。空间复杂度为 $O(kn)$；即使只保存当前层，由于当前层本身可能有 $O(kn)$ 个分段，也仍为 $O(kn)$。在 $n\le30000,k\le50$ 下可以通过。

---

本题的部分分按照 $n,k$ 和雪厚结构分层。小数据可以枚举洞所在的分段，甚至对每一段内的位置做数值优化。$k$ 较小时，尤其是 $k=2$，可以单独推导分界点的最优位置并枚举分界。所有 $a_i$ 相等的特殊性质将问题退化为按长度均分的连续划分问题，更容易得到显式或较简单的动态规划。中等规模数据可以用普通 DP 加数值优化处理。满分数据则需要把道路位置换成累计雪量坐标，将转移表示为分段二次函数的下包络，并用类似凸包维护的方式在线性时间内完成每一层转移。