TopCoder

Thumb tan2
skylinebaby
激しい「喜び」はいらない… そのかわり深い「絶望」もない……… 「植物の心」のような人生を… そんな「平穏な生活」こそ私の目標だったのに………

User's AC Ratio

85.7% (48/56)

Submission's AC Ratio

57.2% (95/166)

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

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

Sample Output

26363

Hints

Problem Source

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

Subtasks

For Testdata: 0 ~ 2, Score: 30
For Testdata: 0 ~ 6, Score: 30
For Testdata: 0 ~ 11, Score: 40
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 524288 262144
1 1000 524288 262144
2 1000 524288 262144
3 1000 524288 262144
4 1000 524288 262144
5 1000 524288 262144
6 1000 524288 262144
7 1000 524288 262144
8 1000 524288 262144
9 1000 524288 262144
10 1000 524288 262144
11 1000 524288 262144