TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

94.1% (112/119)

Submission's AC Ratio

58.6% (217/370)

Tags

Description

  飛天桑妮(?)是一隻運動神經很好的鼯鼠,她很喜歡在樹木間移動,尤其最愛從高處一躍而下,享受滑翔的快感。她所居住的森林裡有$ N $棵樹木,已知每棵樹$ t_i (1 \leq i \leq N) $的位置$ (x_i , y_i )$ 和高度$ h_i$。桑妮的家$ t_1 $位於$ (0, 0)$,而桑妮的奶奶家$ t_N $位於$ (10000, 10000)$的位置。這個週末她要去奶奶家,因而尋求你的協助。
  從家裡前往奶奶家的旅程可定義為由$ K (2 \leq K \leq N) $棵相異樹木構成的序列
  $\pi = [\pi(1) = 1, \pi(2), …, \pi(K) = N]$。
由於桑妮想要快點到奶奶家,所以旅程後段的樹木不能比前段的樹木離桑妮家還近,也就是$ d(t_1, t_{\pi(i+1)}) \geq d(t_1, t_{\pi(i)})$,其中$ d(t_i, t_j) $表示兩棵樹$ t_i $和$ t_j $的直線距離。當桑妮從一棵較高的樹$ t_{\pi(i)} $跳到下一棵樹$ t_{\pi(i+1)} $ 時,如果是由高到低,她就能使出滑翔絕技,享受樂趣。高度差越大,樂趣就越大,因此我們可以把樂趣值定為$ \max \{ 0, h_{\pi(i)} - h_{\pi(i+1)} \} $。她希望這段旅程中可以享受到最大的樂趣,因此想請你幫忙寫一個程式,計算所有可能的旅程中,最大的樂趣值為多少。

  以上圖為例,森林中有五棵樹,其位置和高度如圖所示。如果桑妮的旅程是$ [1, 2, 3, 4,5]$,則這段旅程的最大樂趣為$ t_3$ 到$ t_4 $得到的樂趣值$ 300 – 100 = 200$;如果旅程是$ [1, 3,5]$,則最大樂趣為 $t_3 $到$ t_5 $得到的樂趣值$ 300 – 150 = 150$。旅程$ [1, 3, 2, 5] $是不合理的,因為$ t_2 $比$ t_3 $離桑妮家還要近。旅程$ [1, 5] $是合理的(記得飛天桑妮的運動神經很好嗎),但最大樂趣值是$ 0$。

Input Format

第一列有一個正整數$N(\leq 10^ 5)$,代表森林中的樹木數。接下來的$N$列,每一列有三個正整數$x_i,y_i(\leq 10^ 4)$和$h_i(\leq 10^ 5)$,彼此間以一個空白隔開,代表第$i$棵樹$t_i$在位置$(x_i, y_i)$,且該樹高度為$h_i$。

Output Format

請輸出所有合理旅程中,最大的樂趣值。

Sample Input 1

7
0 0 42
5726 1480 29359
6965 4465 5706
8148 3284 16828
6335 6503 19170
9962 492 2996
10000 10000 18468

Sample Output 1

26363

Hints

Problem Source

臺北市105學年度高級中學資訊學科能力競賽程式設計試題第一題
Set by Yihda Yol

Subtasks

No. Testdata Range Score
1 0~2 30
2 0~6 30
3 0~11 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 262144 1 2 3
1 1000 524288 262144 1 2 3
2 1000 524288 262144 1 2 3
3 1000 524288 262144 2 3
4 1000 524288 262144 2 3
5 1000 524288 262144 2 3
6 1000 524288 262144 2 3
7 1000 524288 262144 3
8 1000 524288 262144 3
9 1000 524288 262144 3
10 1000 524288 262144 3
11 1000 524288 262144 3