题目详情题解（0）讨论（0）提交记录（0）

AT_joi2025_yo2_c.ソフトクリーム (Softcream)

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Alice 和 Bob 来到软冰淇淋店 JOICE。在这家店里，顾客可以各自选择一种口味、一种蛋筒和一种配料，由此点单软冰淇淋。

  • 口味共有 XX 种，对应的价格为 A1,A2,…,AXA_1, A_2, \dots, A_X。
  • 蛋筒共有 YY 种，对应的价格为 B1,B2,…,BYB_1, B_2, \dots, B_Y。
  • 配料共有 ZZ 种，对应的价格为 C1,C2,…,CZC_1, C_2, \dots, C_Z。

软冰淇淋的价格为所选口味、蛋筒和配料价格之和。此时，给定一个整数 PP，软冰淇淋的分数定义为其价格与 PP 的差的绝对值。

Alice 和 Bob 两个人打算一起点一个软冰淇淋，但他们想点的冰淇淋完全相反。具体地说，Alice 希望最大化分数，Bob 则希望最小化分数。因此，选择软冰淇淋口味、蛋筒和配料的方法如下：

  1. 首先，Alice 选择口味。
  2. 接着，Bob 选择蛋筒。
  3. 最后，Alice 选择配料。

现给出口味、蛋筒、配料的信息以及整数 PP，请编写程序，当两人都尽力作出最优选择时，输出最终点单的软冰淇淋分数。

输入格式

输入格式如下：

X Y Z P A1 A2 ⋯ AX B1 B2 ⋯ BY C1 C2 ⋯ CZX\ 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

    1 1 3 22
5
10
9 2 3

    输出#1

    5

  • 输入#2

    1 2 2 100
11
33 44
40 60

    输出#2

    15

  • 输入#3

    2 2 2 0
15 23
5 16
23 45

    输出#3

    73

  • 输入#4

    3 3 3 50
12 5 5
2 19 37
10 5 15

    输出#4

    14

说明/提示

小题

  1. (77 分) X=1X=1，Y=1Y=1，Z≤100Z \leq 100。
  2. (1717 分) X=1X=1，Y≤100Y \leq 100，Z≤100Z \leq 100。
  3. (2121 分) X≤100X \leq 100，Y≤100Y \leq 100，Z≤100Z \leq 100。
  4. (2222 分) X≤4 000X \leq 4\,000，Y≤4 000Y \leq 4\,000，Z≤4 000Z \leq 4\,000。
  5. (3333 分) 无额外约束。

样例解释 1

口味、蛋筒、配料的选法共有以下 33 种：

  • 价格分别为 5,10,95,10,9：总价 2424，分数为 ∣24−22∣=2|24-22|=2
  • 价格分别为 5,10,25,10,2：总价 1717，分数为 ∣17−22∣=5|17-22|=5
  • 价格分别为 5,10,35,10,3：总价 1818，分数为 ∣18−22∣=4|18-22|=4

首先 Alice 选择价格为 55 的口味，然后 Bob 选择价格为 1010 的蛋筒。

最后，Alice 希望最大化分数，因此选择价格为 22 的配料，使得分数为 55，这是最优选择。

因此，双方最优选择下的分数为 55。

此输入样例满足所有子任务的约束。

样例解释 2

口味、蛋筒、配料的选法共有以下 44 种：

  • 价格分别为 11,33,4011,33,40：总价 8484，分数为 ∣84−100∣=16|84-100|=16
  • 价格分别为 11,33,6011,33,60：总价 104104，分数为 ∣104−100∣=4|104-100|=4
  • 价格分别为 11,44,4011,44,40：总价 9595，分数为 ∣95−100∣=5|95-100|=5
  • 价格分别为 11,44,6011,44,60：总价 115115，分数为 ∣115−100∣=15|115-100|=15

首先 Alice 选择价格为 1111 的口味。

接下来，Bob 可在价格为 3333 和 4444 的蛋筒中选择。这里 Bob 若选了某一个蛋筒，Alice 后续为最大化分数采取如下选择：

  • Bob 选择价格为 3333 的蛋筒时：Alice 选择价格为 4040 的配料，分数为 1616。
  • Bob 选择价格为 4444 的蛋筒时：Alice 选择价格为 6060 的配料，分数为 1515。

Bob 希望最小化分数，因此选择4444元的蛋筒，使分数为 1515，为最优选择。

因此，最终分数为 1515。

此样例满足子任务 2,3,4,52,3,4,5 的约束。

样例解释 3

当 P=0P=0 时，分数等价于所选口味、蛋筒和配料的总价，因此 Alice 会选价格最高的口味和配料，Bob 会选价格最低的蛋筒，最终对应的价格分别为 23,5,4523,5,45，分数为 7373。

此样例满足子任务 3,4,53,4,5 的约束。

样例解释 4

请注意，口味、蛋筒及配料可能存在相同价格的情况。

此样例满足子任务 3,4,53,4,5 的约束。

数据范围与约束

  • 1≤X≤200 0001 \leq X \leq 200\,000。
  • 1≤Y≤200 0001 \leq Y \leq 200\,000。
  • 1≤Z≤200 0001 \leq Z \leq 200\,000。
  • 0≤P≤3×1080 \leq P \leq 3 \times 10^8。
  • 0≤Ai≤1080 \leq A_i \leq 10^8（1≤i≤X1 \leq i \leq X）。
  • 0≤Bj≤1080 \leq B_j \leq 10^8（1≤j≤Y1 \leq j \leq Y）。
  • 0≤Ck≤1080 \leq C_k \leq 10^8（1≤k≤Z1 \leq k \leq Z）。
  • 所有输入值均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页