NTUCPC Speed Run! #1 比賽已結束，感謝大家的參與！題目連結
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
851 . 治癒人類計畫
TopCoder
Tags
Description
貓咪國是一個人與貓和平相處的國度，人類養活貓咪，貓咪治癒人類，真是烏托邦一般的世界。然而，貓咪們卻發現這年頭人類過得越來越不開心了，需要想個辦法讓人類天天都能看到可愛的貓咪，這樣所有的憂鬱問題都能一口氣得到解決。
具體來說，貓咪國建立在一個一維數線上，數線上共住著 $N$ 隻貓和 $N$ 個人，其中第 $i$ 個人的家位於座標 $Y_i$，第 $i$ 隻貓的窩位於座標 $X_i$，且第 $i$ 隻貓的可愛度是 $V_i$。每一天，所有貓咪會共同選一個數字 $R$，代表今天每一隻貓咪們要拜訪距離他們貓窩 $R$ 單位以內的每一戶人類家裡；換句話說，第 $i$ 隻貓會拜訪第 $j$ 個人若且唯若 $|X_i - Y_j| \le R$。一個人獲得的治癒度會是他今天被拜訪過的所有貓咪的可愛度最大值，但如果他沒有被拜訪到，將不會獲得任何治癒度。
貓咪國首領為了解決人類心理健康問題，訂下一個治癒度目標 $K$，但貓咪們比起走路更想在家躺平，因此他們求助於你：能不能請你找出最小的 $R$，使得一天結束後每一個人獲得的治癒度總和至少是 $K$？
Input Format
第一行有兩個整數 $N, K$。
接下來的三行各有 $N$ 個整數，依序分別代表 $X_i, V_i, Y_i$。
- $1 \le N \le 3 \times 10^ 5$
- $1 \le K \le 10^ {18}$
- $0 \le |X_i|, |Y_i| \le 10^ 9$
- $1 \le V_i \le 10^ 9$
- $X_i, Y_i$ 嚴格遞增
Output Format
請輸出最小的整數 $R$，使得一天結束後每一個人獲得的治癒度總和至少是 $K$。若無論 $R$ 多大都沒辦法滿足條件，請輸出 -1。
Sample Input 1
5 23
1 2 3 4 5
5 3 1 4 2
1 2 3 4 5
1 2 3 4 5
5 3 1 4 2
1 2 3 4 5
Sample Output 1
2
Sample Input 2
5 1
1 2 3 4 5
5 3 1 4 2
1 2 3 4 5
1 2 3 4 5
5 3 1 4 2
1 2 3 4 5
Sample Output 2
0
Sample Input 3
1 1000
1
8
1
1
8
1
Sample Output 3
-1
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 0~11 | $N \le 50$ | 10 |
| 3 | 0~20 | $N \le 2000$ | 30 |
| 4 | 0~29 | 無額外限制 | 60 |