← 返回题目列表

AtCoder · joi2025_yo2_c

C. 软奶油

中文机器翻译题面 查看原题

配点: 100 点

問題文

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 之差的绝对值。

爱丽丝和鲍勃是 2 在人中 1 我想点两份软冰淇淋。2 人们想要点什么样的软冰淇淋却恰恰相反。具体来说,Alice 的目标是最大化分数,Bob 的目标是最小化分数。因此,我决定使用以下方法来选择我想要订购的软冰淇淋的口味、玉米和配料。

  1. 首先,爱丽丝选择一种口味。
  2. 接下来,Bob 选择一个圆锥体。
  3. 最后,爱丽丝选择了配料。

风味、玉米、配料信息和整数 给定 P ,编写一个程序,计算如果双方都尽力而为每个选择,将订购的软冰淇淋的分数。

制約

  • 1 \leqq X \leqq 200\,000.
  • 1 \leqq Y \leqq 200\,000.
  • 1 \leqq Z \leqq 200\,000.
  • 0 \leqq P \leqq 3 \times 10^8.
  • 0 \leqq A_i \leqq 10^8 (1\leqq i \leqq X).
  • 0 \leqq B_j \leqq 10^8 (1\leqq j \leqq Y).
  • 0 \leqq C_k \leqq 10^8 (1\leqq k \leqq Z).
  • 所有输入值都是整数。

小課題

  1. (7 点) X = 1, Y = 1, Z \leqq 100.
  2. (17 点) X = 1, Y \leqq 100, Z \leqq 100.
  3. (21 点) X \leqq 100, Y \leqq 100, Z \leqq 100.
  4. (22 点) X \leqq 4\,000, Y \leqq 4\,000, Z \leqq 4\,000.
  5. (33 点)没有额外的限制。

入力

输入按以下格式给出。

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 行。 在


入力例 1

1 1 3 22
5
10
9 2 3

出力例 1

5

如何选择口味、玉米和配料如下。 3 方法有很多。

  • 价格有所不同 5,10,9:总价 24 ,所以分数是 24 和 22 之间的差的绝对值 2
  • 价格有所不同 5,10,2:总价 17 ,所以分数是 17 和 22 之间的差的绝对值 5
  • 价格有所不同 5,10,3:总价 18 ,所以分数是 18 和 22 之间的差的绝对值 4

首先Alice是一个价格 5 鲍勃选择口味,然后鲍勃选择价格 10 的圆锥体。

最后,爱丽丝想要最大化她的分数,所以价格 选择您的 2 配料并得分 最好使用 5 。

因此,双方都尽力时的得分为 它变成 5 。

此输入示例满足所有子任务约束。 选择


入力例 2

1 2 2 100
11
33 44
40 60

出力例 2

15

如何选择口味、玉米和配料如下。 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 的口味。

接下来,鲍勃有价格 33 锥体和价格 44 中的圆锥体之一。 根据鲍勃选择的圆锥体,爱丽丝将采取以下行动来最大化她的分数。

  • 鲍勃是价格 如果您选择 33 圆锥体:爱丽丝就是价格 选择您的 40 配料并得分 将其设置为 16 。
  • 鲍勃是价格 如果您选择 44 圆锥体:爱丽丝就是价格 选择您的 60 配料并得分 将其设置为 15 。

Bob想要最小化分数,所以价格 选择 44 圆锥并得分 15 。

因此,双方都尽力时的得分为 它变成 15 。

此输入示例是一个小作业。 2,3,4,5 满足约束。 当


入力例 3

2 2 2 0
15 23
5 16
23 45

出力例 3

73

P=0 时,分数只是所选风味玉米配料的价格总和,因此爱丽丝最好选择更昂贵的风味配料,而鲍勃选择较便宜的玉米。

因此,您选择的口味、玉米和配料的价格为 23,5,45 得分为 73 。

此输入示例是一个小作业。 3,4,5 满足约束。 当


入力例 4

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

出力例 4

14

请注意,相同价格可能还有其他口味、甜筒或配料。

此输入示例是一个小作业。 3,4,5 满足约束。 当