TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (33/33)

Submission's AC Ratio

45.2% (47/104)

Tags

Description

「每個人兩腿之間都有一個異次元新世界。」某個最後死於直腸出血的人曾這麼說過。

修羅少年在失去了魔獸世界之後,決定開發自己潛在的異次元世界,於是他上了某個知名網站,觀摩其他前輩進行異次元突破的過程。

「看起來好痛!我愛台灣!」

沒吃過苦的修羅少年,這時打開了「股溝控」(某知名瀏覽器),連上「股溝」(某知名搜尋引擎),在搜尋列打了「無痛異次元突破」的字樣開始搜尋。

他發現無痛異次元突破是不可能的,可是他找到了一篇學術研究,上面寫著:
「所謂異次元突破,就是使用一個厚壁空心圓柱的工具(亦即外圈跟內圈是同心圓,兩圈之間是實心的),將圓柱圓心對準異次元邊界的中心捅下去的過程。異次元突破是每個男人必經的過程,基於人怕痛的心理,自然希望突破造成的疼痛愈少愈好,但經過英國研究證明,疼痛是不可能降低的。每個人異次元的邊界上會有很多關鍵點,每個關鍵點被捅到時會產生不同的爽度(當然也有負的),爽度是可以覆蓋掉疼痛的。藉此可以間接減輕疼痛。」
修羅少年想請你幫他找出最爽可以多爽。

Input Format

第一行有一個整數 $N$,表示有多少關鍵點。

接下來有 $N$ 行,每行有三個數字 $X_i, Y_i, K_i$,用來描述第 $i$ 個關鍵點。

$(X_i, Y_i)$ 表示第 $i$ 個關鍵點的位置、$K_i$ 表示該關鍵點被捅到的爽度。

$-10^ 9\leq X_i, Y_i \leq 10^ 9$
$-10^ 4 \leq K_i\leq 10^ 4$

另外,異次元邊界的中心永遠在 $(0, 0)$

Output Format

輸出一個整數代表最大爽度。

Sample Input 1

6
1 0 1
0 2 3
-3 0 -5
0 -4 5
5 0 4
0 6 -10

Sample Output 1

9

Hints

對於 $50\%$ 測資,$N \leq 10^ 3$
對於 $70\%$ 測資,$N \leq 10^ 4$
對於 $100\%$ 測資,$N \leq 10^ 5$

(範例測資中,外圈半徑 = 5, 內圈半徑 = 4)

Problem Source

原TIOJ1638 / Problem Setter: ATP
Description By DarkBtf
Special Thanks: yuscvscv

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

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