Solution

设 $f[i]$ 表示第 $i$ 辆汽车开始加工的时间，$t[i]$ 表示对每个工人完成工作时间做的前缀和，$g[i]$ 表示题目中的 $f[i]$。

题目中的：根据公司政策，一个工人完成他的工作后，他必须立即将工作交给下一个工人，不得拖延。表明每个工人 $j$ 开始加工第 $i$ 的时间一定大于等于他加工完第 $i$ 辆车的时间。就有：

$$f[i] + t[j-1] \times g[i] \ge f[i - 1] + t[j] \times g[i - 1]$$$$f[i] \ge f[i - 1] + t[j] \times g[i - 1] - t[j-1] \times g[i]$$$$f[i] = f[i - 1] + \max_{j=1}^{n} (t[j] \times g[i - 1] - t[j-1] \times g[i])$$

暴力枚举 $j$，可以获得 $40$ 分。

考虑斜率优化，式子右边提取出 $g[i-1]$ 或 $g[i]$，得到：

$$f[i] = f[i - 1] + g[i-1] \times \max_{j=1}^{n} (t[j] - t[j-1] \times \frac{g[i]}{g[i-1]})$$

$t[j]$ 相当于是 $y$，$t[j-1]$ 是 $x$，$\frac{g[i]}{g[i-1]}$ 是 $k$。接下来就是斜率优化的套路了。因为 $k$ 不具有单调性，所以需要二分，时间复杂度就是 $O(n \log n)$。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;
int f[N], t[N], g[N], n, m, q[N];
//f[i] 表示第 i 辆车的最早开始时间
inline int X(int i) {return t[i - 1];}
inline int Y(int i) {return t[i];}
signed main() {
	cin >> n >> m;
	int r = 0;
	for (int i = 1; i <= n; i ++) {
		cin >> t[i], t[i] += t[i - 1];
		//维护上凸壳(斜率递减)，x = t[i - 1],y = t[i]
		while (r > 1 && (Y(i) - Y(q[r])) * (X(q[r]) - X(q[r - 1])) > (Y(q[r]) - Y(q[r - 1])) * (X(i) - X(q[r])))r --;
		q[++ r] = i;
	}
	for (int i = 1; i <= m; i ++) cin >> g[i];
	f[1] = 0;
	for (int i = 2; i <= m; i ++) {
		//k = g[i] / g[i - 1]
		int ll = 1, rr = r, res;
		//二分找最值
		while (ll <= rr) {
			int mid = ll + rr >> 1;
			//斜率 <= k
			if ((Y(q[mid + 1]) - Y(q[mid])) * g[i - 1] <= (X(q[mid + 1]) - X(q[mid])) * g[i]) {
				res = mid;
				rr = mid - 1;
			} else ll = mid + 1;
		}
		f[i] = f[i - 1] + g[i - 1] * t[q[res]] - t[q[res] - 1] * g[i];
	}
	cout << f[m] + t[n] * g[m];
	return 0;
}