题解：P13345 [EGOI 2025] IMO

先求出最终的排名，那么挖掉一些位置之后每行的和有取值范围 $[l_i,r_i]$，其中 $r_i=l_i+c_ik$。令 $ord_i$ 表示第 $i$ 名的原始标号，那么要求 $r_{i+1}\leq l_i-[ord_i>ord_{i+1}]$。直接从上往下 dp，记录当前 $l_i$ 的删除个数最大值。对于行内需要处理和为 $x$ 选 $y$ 个数是否合法，压成一个二进制数可以处理转移。值域大小是 $mk$，这样做的复杂度是 $\mathcal O(nm^2k)$。

上述做法的状态以值域为基，其大小为 $mk$，很不好优化。令 $S_i$ 表示初始每个人总分数，可以看成数轴上初始有 $n$ 个初始为单点的黑色区间 $[S_i,S_i]$。每次删除一个点会导致 $[l_i,r_i]$ 长度 $+k$，而数轴的总长 $\leq mk$，因此答案 $\leq m$，尝试以此作为状态。那么最终 $[l_i,r_i]$ 是以 $S_i$ 开始拓展的线段，最多拓展到 $[S_{i-1},S_{i+1}]$。

处理 $f_i$ 表示使得前面删 $i$ 个点所需的最大 $l_i$。和为 $x$ 选 $y$ 个数是否合法中，$x$ 只关心到 $S_{i+1}-S_i$。从 $f\to f'$ 的转移考虑填表法，枚举 $f_p$ 的转移，当前删除了 $q$ 个，找到 $\leq f_p-qk-[ord_i>ord_{i+1}]$ 的最大点作为 $f_q$，要求 $\ge S_{i+1}$ 否则终止。对于每个 $p$ 双指针找到这个转移点即可。

时间复杂度 $\mathcal O(n\log n+nm+\frac{m^3k}{\omega})$，因为中间可以 bitset 优化一下背包，因为只关心 $01$。寻找后继也可以直接在这个 bitset 上做。