P17024 [ROI 2026 Day2] 火星背包

由于本题测试数据远大于 4GB，超过洛谷评测上限，子任务 9 中部分测试点被删除，请在 https://www.luogu.com.cn/problem/U697179 中评测。 由于测试数据较大，评测时可能需要 2-4 分钟时间加载测试数据。本题无法开放测试数据下载。您也可以先在上述链接中进行自测，然后再提交本题，以降低等待时间。

火星人马文正在整理背包。他面前摆着 $n$ 件物品，编号为 $1$ 到 $n$。每件物品有两个属性：第 $i$ 件物品具有**奇怪度** $w_i$ 和**价值** $c_i$。奇怪度是一个非负整数，其二进制表示不超过 $k$ 位（$0 \le w_i < 2^k$）；价值是一个非负整数，不超过 $10^9$（$0 \le c_i \le 10^9$）。 一组物品的总价值等于其中所有物品的价值之和，而总奇怪度定义为其中所有物品奇怪度的按位“或”运算结果。 马文称一组物品是**有价值的**，当且仅当其总价值不小于 $C$。对于每个 $i$（$1 \le i \le n$），马文希望从编号不超过 $i$ 的物品中选出一个有价值的子集，使得该子集的总奇怪度尽可能小。 一组整数的按位“或”运算定义如下：考虑这些数的二进制表示，则结果数的第 $i$ 位为 $1$，当且仅当这些数中至少有一个数的第 $i$ 位为 $1$。在编程语言中，该运算用符号 $\mid$ 表示。例如，$(10 \mid 3 \mid 9) = (1010_2 \mid 0011_2 \mid 1001_2) = 1011_2 = 11$。

第一行包含三个整数 $n$, $k$, $C$（$1 \le n \le 2\,000\,000$，$1 \le k \le 22$，$1 \le C \le 10^{15}$），分别表示物品数量、奇怪度二进制位数的上限以及有价值子集的最低总价值。 接下来的 $n$ 行，每行包含两个整数 $w_i$ 和 $c_i$（$0 \le w_i < 2^k$，$0 \le c_i \le 10^9$），分别表示第 $i$ 件物品的奇怪度和价值。

输出 $n$ 个数，第 $i$ 个数应等于从前 $i$ 个物品中选出的有价值子集的最小总奇怪度。如果无法选出这样的子集，则输出 $-1$。

### 说明 对于 $i = 1$，只有一件物品，奇怪度为 $8$，价值为 $7$。由于无法选出总价值不小于 $12$ 的子集，答案为 $-1$。 对于 $i = 2$，有两件物品，唯一有价值的选择是取全部两件物品，总奇怪度为 $8 \mid 2 = 10$。 对于 $i = 3$，任意包含至少两件物品的子集都是有价值的。最优方案是选取第二件和第三件，总奇怪度为 $2 \mid 3 = 3$。 对于 $i = 4$，可以只取第四件物品，其价值已足够，奇怪度为 $1$，达到了最小可能值。对于 $i = 5$，同样只取第四件物品是最优的。 ### 子任务 | 子任务 | 分数 | $n$ | $k$ | 额外限制 | 依赖子任务 | |:---:|:---:|:---:|:---:|:---|:---:| | 1 | 10 | $n \le 20$ | $k \le 10$ | -- | | | 2 | 11 | $n \le 100$ | $k \le 10$ | -- | 1 | | 3 | 14 | $n \le 50\,000$ | $k \le 10$ | -- | 1–2 | | 4 | 13 | $n \le 1\,000\,000$ | $k \le 19$ | 所有 $w_i$ 均为 $2$ 的幂 | -- | | 5 | 11 | $n \le 2\,000$ | -- | -- | 1–2 | | 6 | 18 | $n \le 500\,000$ | $k \le 16$ | -- | 1–3 | | 7 | 6 | $n \le 1\,000\,000$ | $k \le 19$ | -- | 1–4, 6 | | 8 | 6 | -- | $k \le 19$ | -- | 1–4, 6–7 | | 9 | 11 | -- | -- | -- | 1–8 | 翻译由 DeepSeek V4 Pro 完成