Link

Sol

首先暴力最大流肯定很容易搞出来，跑 $10^4$ 级别应该差不多？

考虑模拟最大流，因为最大流可能很大，因此把最大流换成最小割，来考虑割会有什么样的效果。

第二列点就代表零食，第三列就是小朋友。

现在考虑割，割从源点出发到第二列点的边，对最小割是没有影响的。因为第二列到第三列仍然没有发生改变，贡献给答案的只有 $b_j, c_j$，$a_i$ 总共有多少流出去就行了。假如 $a_i$ 割了 $k$ 条边，那么每次取的就是 $\min {((n-k)b_j, c_j)}$ 。这样就存在一个分界点 $k$，前面的都是 $(n-k)b_j$，后面的全部都选 $c_j$。

具体怎么确定选啥，现在是要 $(n-k) b_j > c_j$，只要 $\frac{b_j}{c_j} > \frac{1}{n-k}$ 即 $\frac{c_j}{b_j} > n - k$，先默认 $k=0$。因为分界点每次我们都需要枚举，所以每次取 $\frac{b_j}{c_j} \leq k$ 的位置即可。

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SIZE = 2e5 + 5;

int n, m;
int b[SIZE]; LL s[SIZE], a[SIZE], c[SIZE];
vector < int > flow[SIZE];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    template < class T > 
    inline T read() {
        T a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
} using GTR::read;

int main() {
    n = read <int> (), m = read <int> (); LL sumb = 0;
    for (int i = 1; i <= n; ++ i) a[i] = read <LL> (), s[i] = s[i - 1] + a[i];
    for (int i = 1; i <= m; ++ i) b[i] = read <int> (), sumb += b[i];
    for (int i = 1; i <= m; ++ i) {
        c[i] = read <LL> ();
        LL pos = ceil((double) c[i] / (double) b[i]);
        if (pos <= n) flow[pos].emplace_back(i);
    }
    auto sum = [] (int l, int r) { return s[r] - s[l - 1]; };
    sort(a + 1, a + n + 1); LL ans = s[n], s2 = 0, s1 = s[n];
    for (int i = 1; i <= n; ++ i) {
        s1 -= a[n - i + 1];
        for (int j: flow[i]) s2 += c[j], sumb -= b[j];
        ans = min(ans, s1 + s2 + 1ll * sumb * i);
    }
    printf("%lld\n", ans);
    return 0;
}