851 . 治癒人類計畫

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

BINS

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

apcsc apcsc-exam5

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

Sample Output 1

2

Sample Input 2

5 1
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

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2 3 4
1 1000 524288 65536 1 2 3 4
2 1000 524288 65536 1 2 3 4
3 1000 524288 65536 2 3 4
4 1000 524288 65536 2 3 4
5 1000 524288 65536 2 3 4
6 1000 524288 65536 2 3 4
7 1000 524288 65536 2 3 4
8 1000 524288 65536 2 3 4
9 1000 524288 65536 2 3 4
10 1000 524288 65536 2 3 4
11 1000 524288 65536 2 3 4
12 1000 524288 65536 3 4
13 1000 524288 65536 3 4
14 1000 524288 65536 3 4
15 1000 524288 65536 3 4
16 1000 524288 65536 3 4
17 1000 524288 65536 3 4
18 1000 524288 65536 3 4
19 1000 524288 65536 3 4
20 1000 524288 65536 3 4
21 1000 524288 65536 4
22 1000 524288 65536 4
23 1000 524288 65536 4
24 1000 524288 65536 4
25 1000 524288 65536 4
26 1000 524288 65536 4
27 1000 524288 65536 4
28 1000 524288 65536 4
29 1000 524288 65536 4
Submit
Back to Top