Skip to content
Sign in

ソフトクリーム (Softcream)

Unrated
日本語

Language

Contribute a translation
Time limit
2000 ms
Memory limit
1024 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

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 は \(2\) 人で \(1\) つのソフトクリームを注文しようとしているが，\(2\) 人がどんなソフトクリームを注文したいかは真逆である．具体的には，Alice はスコアを最大化することを，Bob はスコアを最小化することを目的としている．そこで，以下の方法で，注文するソフトクリームのフレーバー・コーン・トッピングを選ぶことにした．

  1. 最初に，Alice がフレーバーを選ぶ．
  2. 次に，Bob がコーンを選ぶ．
  3. 最後に，Alice がトッピングを選ぶ．

フレーバー，コーン，トッピングに関する情報および整数 \(P\) が与えられたとき，両者が各選択で最善を尽くした場合に最終的に注文するソフトクリームのスコアを求めるプログラムを作成せよ．

Constraints

  • \(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\))．
  • 入力される値はすべて整数である．

Subtasks

  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\) 点) 追加の制約はない．

Input

入力は以下の形式で与えられる．

\(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\)

Output

最終的に注文するソフトクリームのスコアを \(1\) 行で出力せよ．

Examples

Sample input 1
1 1 3 22
5
10
9 2 3
Sample output 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\) のフレーバーを選び，次に Bob は値段 \(10\) のコーンを選ぶ．

最後に，Alice はスコアを最大化したいので，値段 \(2\) のトッピングを選んでスコアを \(5\) にするのが最善である．

よって，両者が最善を尽くした場合のスコアは \(5\) になる．

この入力例はすべての小課題の制約を満たす．

Sample input 2
1 2 2 100
11
33 44
40 60
Sample output 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\) のフレーバーを選ぶ．

次に Bob は値段 \(33\) のコーンと値段 \(44\) のコーンのうちいずれかを選ぶ． ここで Bob が選んだコーンに応じて，Alice はその後スコアを最大化するために以下のような行動をとる．

  • Bob が値段 \(33\) のコーンを選んだ場合：Alice は値段 \(40\) のトッピングを選び，スコアを \(16\) にする．
  • Bob が値段 \(44\) のコーンを選んだ場合：Alice は値段 \(60\) のトッピングを選び，スコアを \(15\) にする．

Bob はスコアを最小化したいので，値段 \(44\) のコーンを選んでスコアを \(15\) にするのが最善である．

よって，両者が最善を尽くした場合のスコアは \(15\) になる．

この入力例は小課題 \(2,3,4,5\) の制約を満たす．

Sample input 3
2 2 2 0
15 23
5 16
23 45
Sample output 3
73

\(P=0\) のとき，スコアは単に選んだフレーバー・コーン・トッピングの値段の合計となるので，Alice はより値段の高いフレーバー・トッピングを選び，Bob はより値段の低いコーンを選ぶのが最善である．

よって，選ぶフレーバー・コーン・トッピングの値段はそれぞれ \(23,5,45\) であり，スコアは \(73\) になる．

この入力例は小課題 \(3,4,5\) の制約を満たす．

Sample input 4
3 3 3 50
12 5 5
2 19 37
10 5 15
Sample output 4
14

同じ値段のフレーバーやコーン，トッピングが存在する場合もある事に注意せよ．

この入力例は小課題 \(3,4,5\) の制約を満たす．

Notes

JOI 2025 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source