P13692 [CEOI 2025] lawnmower

在经历了 Poenari 城堡的冒险之后，Vlad 回到家，作为一个真正的罗马尼亚人，他的第一想法就是应该先喂他的马。马对食物要求不高，所以 Vlad 直接把自家草坪当作主要饲料来源。 为此，Vlad 有一台容量为 $c$ 的割草机。他决定将草坪划分为 $n$ 条割草道，编号从 $0$ 到 $n - 1$，并且必须按顺序割完。第 $i$ 条割草道上有 $v[i]$ 数量的未割草，由于一些未知原因，Vlad 推割草机经过这一条需要 $a[i]$ 秒。 在经过几条割草道后，割草机的收集箱可能会达到满容量，此时它将停止割草，剩下的草会留在该条道上。每当出现这种情况时，必须在该条道的末端清空收集箱，这需要花费 $b$ 秒。清空只能在割草道的末端进行。如果在经过第 $i$ 条割草道时收集箱已满，Vlad 仍需要推到该条道的末端，再清空收集箱，然后重新经过该条道一次（或多次），直到割完剩余的草。 例如，如果某条第 $i$ 条割草道需要经过 $3$ 次才能割完全部草，则所需时间为： $$ a[i] + b + a[i] + b + a[i] $$ 在整个草坪割完后，割草机也必须清空一次。 经过一番思考并抱怨说割完需要花费太久，Vlad 得出结论：有时候提前清空收集箱（即便还没满）可能会更节省时间，但他不确定最佳策略。因此他请求你的帮助。 给定每条割草道上的草量、经过该条所需的时间、收集箱容量以及清空所需的时间，求 Vlad 在最短时间内完成割草的最佳策略所需的总时间。

### 实现细节 你需要实现以下过程： ```cpp long long mow(int n, int c, int b, std::vector &a, std::vector &v); ``` * $n$：草坪的割草道数量 * $c$：收集箱的总容量 * $b$：清空收集箱所需的秒数 * $a$：长度为 $n$ 的数组，表示经过每条割草道所需的时间 * $v$：长度为 $n$ 的数组，表示每条割草道上的草量 该过程应返回一个整数，表示完成割草的最短时间。 该过程在每个测试用例中恰好调用一次。

无

### 样例解释 1 考虑如下调用： ```cpp mow(3, 5, 2, {2, 10, 3}, {2, 4, 6}) ``` 在此样例中，有 $3$ 条割草道，收集箱容量为 $5$，清空需要 $2$ 秒。 第一条道，Vlad 割完需要 $2$ 秒，此时收集箱中有 $2$ 单位的草。他选择立即清空（花费 $2$ 秒）。第一条道总共用时 $4$ 秒。 第二条道，割 $4$ 单位草。他选择不清空，第二条道用时 $10$ 秒。 第三条道，开始割草后割到 $1$ 单位草时收集箱已满，因此他推到道末（用 $3$ 秒），清空收集箱（用 $2$ 秒），然后重新割第三条道（用 $3$ 秒）。整个草坪割完后还需要清空一次（用 $2$ 秒）。第三条道总用时 $3 + 2 + 3 + 2 = 10$ 秒。 总用时 $4 + 10 + 10 = 24$ 秒。可以证明这是 Vlad 割草的最优策略。 ### 数据范围 * $1 \leq n \leq 200000$ * 对于每个 $0 \leq i < n$，$1 \leq a[i] \leq 10^9$ * 对于每个 $0 \leq i < n$，$1 \leq v[i] \leq 10^9$ * $1 \leq b \leq 10^9$ * $1 \leq c \leq 10^9$ 保证正确答案不超过 $10^{18}$。 ### 子任务 1. （9 分）所有给定值（$n$、$b$、$c$、$a[i]$、$v[i]$）均不超过 $200$ 2. （16 分）$n, c \leq 5000$ 且对所有 $0 \leq i < n$，$v[i] \leq 5000$ 3. （36 分）$c \leq 200000$ 4. （17 分）$a[0] = a[1] = \ldots = a[n - 1]$ 5. （22 分）无额外限制 --- 翻译由 ChatGPT-5 完成