配点: 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 的目标是最小化分数。因此,我决定使用以下方法来选择我想要订购的软冰淇淋的口味、玉米和配料。
- 首先,爱丽丝选择一种口味。
- 接下来,Bob 选择一个圆锥体。
- 最后,爱丽丝选择了配料。
风味、玉米、配料信息和整数 给定 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).
- 所有输入值都是整数。
小課題
- (7 点) X = 1, Y = 1, Z \leqq 100.
- (17 点) X = 1, Y \leqq 100, Z \leqq 100.
- (21 点) X \leqq 100, Y \leqq 100, Z \leqq 100.
- (22 点) X \leqq 4\,000, Y \leqq 4\,000, Z \leqq 4\,000.
- (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 满足约束。 当