来南京第二天就感冒了，然后嗓子疼，头疼炸了。哈哈。
等等是不是春季赛前我也这个状态来着。呃呃。好像确实一模一样。
这玩意跟 DP 有个鬼关系。
下面两个概率用 \(u_i, v_i\) 表示。
首先如果只选两者之一，贡献为 \(u_i / v_i\)，如果两者都选那么贡献为 \(u_i + v_i - u_iv_i\)。
我们要最大化和，这东西看起来就很费用流。先建个模先。
考虑二分图模型，源点向两个点连流量 \(a, b\)，费用 \(0\) 的边，分别表示选 \(u_i\) 和 \(v_i\)。然后这两个点向每个点 \(i\) 连费用 \(u_i / v_i\)，流量 \(1\) 的边。考虑 \(-u_i v_i\) 的贡献，我们可以先从 \(i\) 向汇点连 \(0\) 费用的边，然后再连一条 \(-u_i v_i\) 费用的边，这样正好满足贡献。
然后发现一边只有两个点，这东西太模拟费用流了，直接大力模拟。大致分 \(S \to a \to i \to T\)，\(S \to b \to i \to T\)，\(S \to a \to i \to b \to j \to T\)，\(S \to b \to i \to b \to j \to T\) 四种，具体懒得写了，太麻烦了。
反正最后复杂度是 \(O(n \log n)\) 的。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
priority_queue<pair<double, int>> q[6];
int n, a, b;
double u[MAXN], v[MAXN];
int type[MAXN];
void update() {
for (int i = 0; i < 6; i++) while (q[i].size()) {
if (type[q[i].top().second] != i % 3) {
q[i].pop();
} else break;
}
}
void insert(int x, int t) {
type[x] = t;
if (type[x] == 0) {
q[0].push({ u[x], x });
q[3].push({ v[x], x });
}
if (type[x] == 1) {
q[1].push({ v[x] - u[x] * v[x], x });
q[4].push({ v[x] - u[x], x });
}
if (type[x] == 2) {
q[2].push({ u[x] - u[x] * v[x], x });
q[5].push({ u[x] - v[x], x });
}
}
int main() {
scanf("%d%d%d", &n, &a, &b);
for (int i = 1; i <= n; i++) {
scanf("%lf", &u[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%lf", &v[i]);
}
for (int i = 1; i <= n; i++) {
insert(i, 0);
}
double ans = 0;
while (a || b) {
int op;
double val = -1e18;
if (a) {
// u[i]
if (q[0].size() && q[0].top().first > val)
val = q[0].top().first, op = 1;
// u[i] - v[i] + v[j]
if (q[3].size() && q[5].size() &&
q[3].top().first + q[5].top().first > val)
val = q[3].top().first + q[5].top().first, op = 2;
// u[i] - v[i] + v[j] - u[j]v[j]
if (q[1].size() && q[5].size() &&
q[1].top().first + q[5].top().first > val)
val = q[1].top().first + q[5].top().first, op = 3;
// u[i] - u[i]v[i]
if (q[2].size() && q[2].top().first > val)
val = q[2].top().first, op = 4;
}
if (b) {
// v[i]
if (q[3].size() && q[3].top().first > val)
val = q[3].top().first, op = 5;
// v[i] - u[i] + u[j]
if (q[0].size() && q[4].size() &&
q[0].top().first + q[4].top().first > val)
val = q[0].top().first + q[4].top().first, op = 6;
// v[i] - u[i] + u[j] - u[j]v[j]
if (q[2].size() && q[4].size() &&
q[2].top().first + q[4].top().first > val)
val = q[2].top().first + q[4].top().first, op = 7;
// v[i] - u[i]v[i]
if (q[1].size() && q[1].top().first > val)
val = q[1].top().first, op = 8;
}
if (op == 1) a--, insert(q[0].top().second, 1);
if (op == 2) a--, insert(q[5].top().second, 1), insert(q[3].top().second, 2);
if (op == 3) a--, insert(q[5].top().second, 1), insert(q[1].top().second, 3);
if (op == 4) a--, insert(q[2].top().second, 3);
if (op == 5) b--, insert(q[3].top().second, 2);
if (op == 6) b--, insert(q[4].top().second, 2), insert(q[0].top().second, 1);
if (op == 7) b--, insert(q[4].top().second, 2), insert(q[2].top().second, 3);
if (op == 8) b--, insert(q[1].top().second, 3);
update();
ans += val;
}
printf("%.12lf\n", ans);
return 0;
}