The 2nd Universal Cup. Stage 19: Estonia J

首先二分答案 \(0/1\) 分数规划是直接的，之后这题有一个非常反直觉的结论是直接忽略掉关于血量时刻 \(\geqslant 0\) 的限制，仅仅要求最终血量 \(\geqslant 0\)，改造问题与原问题等价。感性理解一下就是中间过程有 \(<0\) 但最终 \(\geqslant 0\) 的卡特兰式增长速率其实是小于仅要求最终 \(\geqslant 0\) 的指数的增长速率的，所以求完极限之后前面的 \(\text{case}\) 可以忽略不计(但感觉实在很玄学)。

令二分的答案为 \(mid\)，现在令 \(b\) 为可删向量数，令 \(c\) 为选择增加血量，\(s\) 为忽略的减小血量，\(f_{i,j}\) 为 \(i\) 组的 \(j\) 号任务的权重，\(t_{i,j}\) 为 \(i\) 组 \(j\) 号任务的时间，\(e_{i,j}\) 为 \(i\) 组 \(j\) 号元素的速率，则相当于 \(i\) 组 \(j\) 号任务可以化为两种向量 \(f_{i,j}(c,t_{i,j}e_{i,j}-t_{i,j}x)\)(选择) 与 \(f_{i,j}(-s,0)\)(忽略)(注意由于可以执行无限轮，每一个向量可以乘上任意倍率，所以 \(f_{i,j}\) 的按比例分配可以忽略)，在每一组删除不超过 \(b\) 个向量，令删完后第 \(i\) 组向量和为 \(v_{i}\)，使得每一组非负整数组 \(c\) 满足 \(\sum_{i=1}^{n}c_{i}v_{i}\) 落在第一象限。

后面落在第一象限的条件有一个很好的刻画方式，其等价于存在一条穿过二四象限的直线使得所有的向量都在这条直线下面，于是我们相当于要找存在一条跨过二四象限的直线 \(l\) 存在一点其到 \(l\) 的有向截距 \(>0\)，令直线的斜率为 \(-\frac{1}{k}\)，则 \((x,y)\) 的截距的某倍数可看作 \(x+ky\)。于是每一个向量的权值可以看成是 \(f_{i,j}\max(c+kt_{i,j}e_{i,j}-t_{i,j}x,-s)\)，令 \(sz_{i}\) 为第 \(i\) 组的向量总数，取前 \(max(1,sz_{i}-b)\) 大即可，这个可以用 \(\text{nth_element}\) 解决。

现在令所有均 \(\leqslant 0\) 为合法的，的但现在合法的 \(k\) 是一段区间，我们要找到这样一段区间才可以，注意到如果我们二分的如果不合法，那么必然有一个向量在 \(l\) 上方，此时如果其在第一象限那必然所有的都不合法，如果在二，则应将 \(k\) 调小才可能合法，如果在四，则将 \(k\) 调大才可能合法，那么这样如果存在合法的，那么我们一定会逼近它。

综上可以做到 \(O(n\log^2 V)\)，\(V\) 为值域。