AT_joi2025_yo2_c ソフトクリーム (Softcream)

Alice 和 Bob 来到软冰淇淋店 JOICE。在这家店里，顾客可以各自选择一种口味、一种蛋筒和一种配料，由此点单软冰淇淋。 - 口味共有 $X$ 种，对应的价格为 $A_1, A_2, \dots, A_X$。 - 蛋筒共有 $Y$ 种，对应的价格为 $B_1, B_2, \dots, B_Y$。 - 配料共有 $Z$ 种，对应的价格为 $C_1, C_2, \dots, C_Z$。 软冰淇淋的价格为所选口味、蛋筒和配料价格之和。此时，给定一个整数 $P$，软冰淇淋的**分数**定义为其价格与 $P$ 的差的绝对值。 Alice 和 Bob 两个人打算一起点一个软冰淇淋，但他们想点的冰淇淋完全相反。具体地说，Alice 希望最大化分数，Bob 则希望最小化分数。因此，选择软冰淇淋口味、蛋筒和配料的方法如下： 1. 首先，Alice 选择口味。 2. 接着，Bob 选择蛋筒。 3. 最后，Alice 选择配料。 现给出口味、蛋筒、配料的信息以及整数 $P$，请编写程序，当两人都尽力作出最优选择时，输出最终点单的软冰淇淋分数。

输入格式如下： > $X\ Y\ Z\ P\ A_1\ A_2\ \cdots\ A_X\ B_1\ B_2\ \cdots\ B_Y\ C_1\ C_2\ \cdots\ C_Z$

请输出最终点单的软冰淇淋分数，仅一行。

## 小题 1. ($7$ 分) $X=1$，$Y=1$，$Z \leq 100$。 2. ($17$ 分) $X=1$，$Y \leq 100$，$Z \leq 100$。 3. ($21$ 分) $X \leq 100$，$Y \leq 100$，$Z \leq 100$。 4. ($22$ 分) $X \leq 4\,000$，$Y \leq 4\,000$，$Z \leq 4\,000$。 5. ($33$ 分) 无额外约束。 ## 样例解释 1 口味、蛋筒、配料的选法共有以下 $3$ 种： - 价格分别为 $5,10,9$：总价 $24$，分数为 $|24-22|=2$ - 价格分别为 $5,10,2$：总价 $17$，分数为 $|17-22|=5$ - 价格分别为 $5,10,3$：总价 $18$，分数为 $|18-22|=4$ 首先 Alice 选择价格为 $5$ 的口味，然后 Bob 选择价格为 $10$ 的蛋筒。 最后，Alice 希望最大化分数，因此选择价格为 $2$ 的配料，使得分数为 $5$，这是最优选择。 因此，双方最优选择下的分数为 $5$。 此输入样例满足所有子任务的约束。 ## 样例解释 2 口味、蛋筒、配料的选法共有以下 $4$ 种： - 价格分别为 $11,33,40$：总价 $84$，分数为 $|84-100|=16$ - 价格分别为 $11,33,60$：总价 $104$，分数为 $|104-100|=4$ - 价格分别为 $11,44,40$：总价 $95$，分数为 $|95-100|=5$ - 价格分别为 $11,44,60$：总价 $115$，分数为 $|115-100|=15$ 首先 Alice 选择价格为 $11$ 的口味。 接下来，Bob 可在价格为 $33$ 和 $44$ 的蛋筒中选择。这里 Bob 若选了某一个蛋筒，Alice 后续为最大化分数采取如下选择： - Bob 选择价格为 $33$ 的蛋筒时：Alice 选择价格为 $40$ 的配料，分数为 $16$。 - Bob 选择价格为 $44$ 的蛋筒时：Alice 选择价格为 $60$ 的配料，分数为 $15$。 Bob 希望最小化分数，因此选择$44$元的蛋筒，使分数为 $15$，为最优选择。 因此，最终分数为 $15$。 此样例满足子任务 $2,3,4,5$ 的约束。 ## 样例解释 3 当 $P=0$ 时，分数等价于所选口味、蛋筒和配料的总价，因此 Alice 会选价格最高的口味和配料，Bob 会选价格最低的蛋筒，最终对应的价格分别为 $23,5,45$，分数为 $73$。 此样例满足子任务 $3,4,5$ 的约束。 ## 样例解释 4 请注意，口味、蛋筒及配料可能存在相同价格的情况。 此样例满足子任务 $3,4,5$ 的约束。 # 数据范围与约束 - $1 \leq X \leq 200\,000$。 - $1 \leq Y \leq 200\,000$。 - $1 \leq Z \leq 200\,000$。 - $0 \leq P \leq 3 \times 10^8$。 - $0 \leq A_i \leq 10^8$（$1 \leq i \leq X$）。 - $0 \leq B_j \leq 10^8$（$1 \leq j \leq Y$）。 - $0 \leq C_k \leq 10^8$（$1 \leq k \leq Z$）。 - 所有输入值均为整数。 由 ChatGPT 5 翻译