上界卡不来，怎么这么菜？？？
下文的概率都是指的 \(\frac{p}{100}\)。
首先有一个想法就是直接背包，但是 \(\prod p\) 涉及不小的数的乘积并不好放入状态，所以考虑设 \(f_s\) 表示 \(\sum w = s\) 的最大概率，但这样只能做到 \(O(n^2V)\)。
分析背包为什么会这么烂：
- 物品数量为 \(n\)。
- 值域上界为 \(nV\)。
这题的题面看着就很精简，似乎无法有更好的解法了，于是尝试从这两个方向来优化。
考虑到这个左侧 \(\prod p\) 的形式，感受一下如果放了很多 \(p\) 很小的物品感觉就比较劣，于是可以尝试对每个 \(p\) 卡一个上界——即算出每个 \(p\) 至多放多少个。
错误的卡上界方式：
不妨认为 \(w = 1 / p\)，那么选 \(k\) 个的答案肯定需要比选 \(1\) 个大，就需要满足 \(p^k\times kw = kp^{k - 1} > 1\)。
正确的卡上界方式：
考虑类似背包一个一个放入，那么答案需要递增，否则如果答案不升，概率还更小了一定不优，于是可以得到不等式 \(kp^{k - 1} > (k - 1)p^{k - 2}\)，解得 \(k < \frac{1}{1 - p}\)。
当 \(p = 1\) 时这个式子会 \(/0\)，不过分析一下 \(p = 1\) 就等同于送自己的，一定会选上，那么可以直接忽略掉。
同时因为答案式子后面是 \(\sum w\)，在 \(p\) 相同的情况下，贪心的想法可以知道肯定会尽量选 \(w\) 大的，于是现在就已经可以知道每个 \(p\) 会选多少个并且怎么选了，总共可能选的元素个数为 \(\sum\limits_{i = 1}^{99} \lfloor\frac{100}{100 - i}\rfloor = 481\)。
不过此时如果直接背包也还是 \(\mathcal{O}(m^2V)\) 的，于是继续考虑去卡值域的上界。
错误的卡上界方式：
认为上界 \(= \sum\limits_{i = 1}^{99} \lfloor\frac{100}{100 - i}\rfloor\lfloor\frac{2\times 10^5}{i}\rfloor\)。
正确的卡上界方式：
上面的做法明显是投机取巧啊，除了我真的会有人这么干吗（。
考虑类似上文的方法，考虑令 \(s = \sum w, t = \prod p\)，如果删掉一个物品 \((p, w = 1 / p)\) 不劣，那肯定不行，那么有 \(st > (s - 1 / p)\frac{t}{p}\)，解得 \(s <\frac{1}{p(1 - p)}\)。
这个函数在 \(p = 0.01 / 0.99\) 时（因为有定义域限制）取到最值，并且注意把 \(1\) 替换成 \(2\times 10^5 / 100 = 2\times 10^3\)，得到 \(s\le 202020\)。
此时就可以跑背包了，记 \(m = 481, W = 202020\)，时间复杂度为 \(\mathcal{O}(n\log n + mW)\)。
#include <bits/stdc++.h>using f128 = long double;constexpr int V = 202020;f128 f[V + 1];
std::vector<int> w[100];int main() {int n, sum1 = 0;scanf("%d", &n);for (int i = 1; i <= n; i++) {int p, _w;scanf("%d%d", &p, &_w);if (p == 100) {sum1 += _w;} else {w[p].push_back(_w);}}f[0] = 1.0;for (int _p = 1; _p <= 99; _p++) {std::sort(w[_p].begin(), w[_p].end(), std::greater<>());f128 p = 1.0L * _p / 100;for (int i = 1; (1.0L - p) * i < 1.0L && i - 1 < w[_p].size(); i++) {for (int j = V; j >= w[_p][i - 1]; j--) {f[j] = std::max(f[j], f[j - w[_p][i - 1]] * p);}}}f128 ans = 0;for (int s = 0; s <= V; s++) {ans = std::max(ans, f[s] * (s + sum1));}printf("%.10Lf\n", ans);return 0;
}