CF1101F Trucks and Cities

有 $n$ 个城市沿着一条公路分布，可以看作在一条直线上。第 $i$ 个城市距离原点 $a_i$ 千米。所有城市都位于原点的同一侧。有 $m$ 辆卡车需要从一个城市开到另一个城市。 每辆卡车由 $4$ 个整数描述：起始城市 $s_i$，终点城市 $f_i$，每公里油耗 $c_i$，以及最多可加油次数 $r_i$。第 $i$ 辆卡车每行驶一公里将消耗 $c_i$ 升油。 当卡车到达某个城市时，可以进行加油（在城市之间的路途中无法加油）。第 $i$ 辆卡车最多可以加油 $r_i$ 次。每次加油都会将油箱加满。所有卡车出发时油箱都是满的。 所有卡车的油箱容量均为 $V$ 升。你需要求出最小的 $V$，使得所有卡车都能在不超过允许加油次数的情况下到达目的地。

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 400$，$1 \le m \le 250000$），分别表示城市数和卡车数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$，$a_i < a_{i+1}$），表示城市的位置，按升序排列。 接下来的 $m$ 行，每行包含 $4$ 个整数，分别为 $s_i$、$f_i$、$c_i$、$r_i$（$1 \le s_i < f_i \le n$，$1 \le c_i \le 10^9$，$0 \le r_i \le n$），描述第 $i$ 辆卡车的信息。

输出一个整数，表示所有卡车都能到达目的地所需的最小油箱容量 $V$。

我们详细分析一下各个询问： 1. 第 $1$ 辆卡车需要从 $2$ 号城市到 $7$ 号城市，中途不能加油，因此油箱容量至少需要 $50$。 2. 第 $2$ 辆卡车需要从 $2$ 号城市到 $17$ 号城市，可以在路径上的任意城市加油，因此油箱容量至少需要 $48$。 3. 第 $3$ 辆卡车需要从 $10$ 号城市到 $14$ 号城市，中间没有城市，因此油箱容量至少需要 $52$。 4. 第 $4$ 辆卡车需要从 $10$ 号城市到 $17$ 号城市，只能加油一次，最优方案是在 $14$ 号城市（第 $5$ 个城市）加油，因此油箱容量至少需要 $40$。 5. 第 $5$ 辆卡车与第 $4$ 辆描述相同，因此油箱容量也至少需要 $40$。 6. 第 $6$ 辆卡车需要从 $2$ 号城市到 $14$ 号城市，可以加油两次：第一次在 $2$ 号或 $3$ 号城市，第二次在 $4$ 号城市，因此油箱容量至少需要 $55$。 由 ChatGPT 4.1 翻译