生成序列中的预算选择¶
出题人解法： 先取所有非正数，再用随机枢轴划分正数，按较小部分的和缩小搜索区间。Codex（GPT-6）贡献： 实现完整规模的动态存储、三路划分和安全递推，补充排序方案及证明。
生成与非正数¶
使用 64 位计算递推。因余数绝对值小于 \(|D|\) ，有 \(|x_i|<2\times10^9\) ，生成项可存为 32 位整数。中间乘积绝对值小于 \(2\times10^{18}\) ，所有项之和绝对值小于 \(4\times10^{16}\) ，64 位均足够。
将所有非正数加入选择；这只会增加数量且不会增加费用。同时从剩余预算中减去它们的和。如果剩余预算仍为负，说明连所有非正数的和都高于原预算。这是所有子集能达到的最小和，因此无可行解，按约定输出零。
否则只需考虑正数。对任意固定数量，最便宜的选择都是该数量个最小值：若选中了较大值却没选较小值，交换后不会增加费用。因此答案一定能由排序后某个前缀实现。
随机三路划分¶
在未处理正数中选一个枢轴 \(v\) ，划分为小于、等于、大于 \(v\) 的三段，并统计较小段之和 \(s\) .
- 若 \(s>L\) ，所需前缀在较小段内部，丢弃其余两段并继续。
- 若 \(s\le L\) ，先全部选择较小段，扣掉费用。等于枢轴的 \(c\) 项中，可选择 \(\min(c,\lfloor L/v\rfloor)\) 项。
- 如果相等段没有全部选完，就已得到最大前缀。否则继续在较大段寻找。
三路划分一次性处理相同值；非正数已单独处理，所以除以 \(v\) 总是合法。
正确性与复杂度¶
交换论证保证只需寻找最便宜前缀。每次分支要么把搜索限制到前缀结束所在的较小段，要么确定地消费完整较小段和可支付的相等段，所以保持答案与剩余预算的不变量。区间耗尽或无法付清相等段时，不存在可再加入的更小值，得到最大数量。
对均匀随机枢轴，选择阶段期望线性，连同生成共期望 \(O(n)\) 时间、\(O(n)\) 空间。最坏时间可达 \(O(n^2)\) .代码采用固定伪随机种子方便复现，这不提供针对任意输入的最坏线性保证。使用完整区间的均匀分布，不把范围很小的 rand() 输出直接当成大区间内均匀下标。
排序前缀方案有确定的 \(O(n\log n)\) 时间，见程序。它提供更直接的排序结构，但在参考环境的完整压力数据上超过本题预估时限，因此作为备用和结果核对程序；标准程序采用出题人的划分算法。
实现与验证¶
参考环境中标准程序最慢中位数 0.258953 秒，峰值 81.48 MiB，校准时限 1.0 秒。每例独立运行五次。