不难发现一个较简单的网络流模型：
- 源点向所有糖果 \(i\) 连 \(a_i\) 的容量；
- 所有糖果向所有人 \(i\) 连 \(b_i\) 的容量；
- 所有人 \(i\) 向汇点连 \(c_i\) 的容量。
但第二步中建出的边数达到了惊人的 \(O(nm)\)，显然过不去。
考虑优化。从最大流角度优化较困难，由于最大流等价于最小割，我们可以从最小割的角度进行优化。
考虑先枚举源点到每个糖果的边是否断掉，设保留了 \(l\) 个糖果。那么每个人都有两种决策：把到 \(l\) 个糖果的边全部断掉，或是断掉到汇点的边，代价是 \(\min(lb_i,c_i)\)。
发现这个决策与具体选了哪些糖果无关，故我们可以先把不保留代价大的糖果保留，即按 \(a_i\) 降序排序，依次选糖果。观察第 \(i\) 个人的代价 \(\min(lb_i,c_i)\)，由于 \(l\) 是递增的，所以必定存在某个时刻 \(k_i\)，使得 \(k_ib_i>c_i\) 且 \((k_i-1)b_i\le c_i\)，即在 \(k_i\) 之前第 \(i\) 个人的决策是 \(lb_i\)，但到 \(k_i\) 之后第 \(i\) 个人的决策就变成了 \(c_i\)。把人按 \(k_i\) 升序排序，于是所有人决策总变化量是 \(O(n)\) 的，双指针即可。
#include <numeric>
#include <iostream>
#include <algorithm>
using namespace std;
using LL = long long;
const int kN = 2e5 + 1;
int n, m, b[kN], d[kN];
LL a[kN], c[kN], k[kN], ans;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= m; ++i) {
cin >> b[i];
}
for (int i = 1; i <= m; ++i) {
cin >> c[i];
k[i] = c[i] / b[i] + 1;
d[i] = i;
}
sort(a + 1, a + n + 1, greater<LL>());
sort(d + 1, d + m + 1, [](int i, int j) { return k[i] < k[j]; });
LL s = accumulate(a + 1, a + n + 1, 0LL), vc = 0, bs = accumulate(b + 1, b + m + 1, 0LL);
ans = s;
for (int i = 1, j = 1; i <= n; ++i) {
s -= a[i], vc += bs;
for (; j <= m && k[d[j]] <= i; ++j) {
vc -= 1LL * i * b[d[j]] - c[d[j]], bs -= b[d[j]];
}
ans = min(ans, s + vc);
}
cout << ans;
return 0;
}