Login with GitHub. Nope?
修正 C++ 的程式碼在使用一定量動態記憶體後會產生 RF 的問題 @ 2019/12/6 4:45pm NeoHOJ 強勢復活中 (Open beta)
Submit  Ranklist

Problem : 200 - SETNJA

Problem Statistics

Solved Member: 3  Submission: 6  User Tried: 4

Statement:

Mirko 大大想要帶他的朋友們去一場將在 Zagreb 舉行的 "Zaz" 演唱會。他已經拿到足夠的票了,因此他現在正在他家附近散步,順便將票分給他的朋友們。

Mirko 家附近可以用一個笛卡爾坐標系來表示。當 Mirko 大大在走路的時候,他只會踩在格子點上〈即x, y座標均為整數〉。他走路時有八個方向,分別是上下左右和對角四方位。

Mirko 的每位朋友也都住在格子點上,並且他們會走到他們家附近和 Mirko 會面。Mirko 只能和朋友在格子點上會面,而且因為每個朋友都有屬於自己的懶惰程度 P,因此只能在離每位朋友家 P 步的距離碰面。

Mirko 回家之後,他記得他拜訪朋友們的順序,請你依照這個順序計算出他所需要走的步數最小值為多少。

請注意,Mirko 的起點和終點是未知的。

Input:Output:

第一行有一個整數 N(2 ≤ N ≤ 200 000),代表 Mirko 的朋友數量。

接下來有 N 行,每行有三個整數,分別代表這位朋友家的 x, y 座標和懶惰程度 P。

這N行資訊依照 Mirko 的拜訪順序排序。
請輸出唯一一行,代表 Mirko 完成他的任務所需要走的最少步數。

Sample Input:Sample Output:

SAMPLE A:
3
3 10 2
8 4 2
2 5 2

SAMPLE B:
4
3 3 5
7 11 5
20 8 10
30 18 3
SAMPLE A:
4

SAMPLE B:
19

HINT:

占分 30% 的測資裡,N 最大值為 200。
另外 30% 的測資,P 不會超過 10。

第一筆範例測資中,Mirko 從 (4, 8) 碰到他的第一個朋友,並在 (6, 6) 碰到第二個朋友,並在 (4, 5) 碰到他的第三個朋友。

Source:

COI 2012

Problem Setter

Testdata:

TestTimeMemoryScore
0-13000ms262144kb
0-23000ms262144kb
13000ms262144kb10
23000ms262144kb10
33000ms262144kb10
43000ms262144kb10
53000ms262144kb10
63000ms262144kb10
73000ms262144kb10
83000ms262144kb10
93000ms262144kb10
103000ms262144kb10