TopCoder

User's AC Ratio

76.7% (33/43)

Submission's AC Ratio

26.7% (82/307)

Description

法國設計師「西當・普里斯」設計了一款新潮的燈具,這盞燈具的造型是一個圓盤,上面佈設了許多單顆的 LED 燈泡,開啟燈具上 LED 的方式,是利用一支與圓盤直徑等長的棒狀感應器,此感應器的中心點固定於圓盤圓心,且可順時針以圓心為固定點旋轉,旋轉時它所接觸到的 LED 皆會被開啟。以下圖為例,黑點代表未開啟的燈泡,開關由 L1 移動至 L2 後,燈泡開啟的狀況如下。

每次開啟的 LED 燈泡會落在棒狀感應器經過的兩個扇形區域。另外,我們假設旋轉開始或結束時,若感應器下方有 LED 燈泡,則它們也會被開啟。

然而,廠商在製造燈具時沒有控管材料,做出來的燈具上所佈設的 LED 亮度與顏色不一,導致整體的整體質感受到了影響。西當普里斯請廠商把每顆 LED 開啟時的呈現的質感量化為一個整數,稱為質感係數;整盞燈具的質感可由開啟的 LED 之質感係數加總而得,若一個 LED 都沒有開啟,則質感為 $0$。已知我們可以選擇感應器初始擺放的角度,在初始所有 LED 燈泡皆是關閉的狀態下,請寫程式幫助西當普里斯,計算這盞燈具最大可能的質感。

Input Format

輸入共 $n + 1$ 行,第一行有一個整數 $n$,表示 LED 燈泡的個數。假設圓心位於原點 $(0, 0)$。接下來 $n$ 行,第 i 行有三個整數 $x_i , y_i , w_i$,其中 $(x_i , y_i)$ 表示第 $i$ 個 LED 燈泡的座標,任二 LED 燈泡的座標皆不同且燈泡座標不會在原點上,$w_i$ 表示該燈泡的質感係數。

Output Format

輸出為一整數,表示此燈具的最大質感。

Sample Input

Sample Input 1
4
2 1 -1
-5 1 3
-3 1 -2
0 1 4

Sample Input 2
7
1 -1 -1
1 3 1
0 -1 -4
0 4 5
-1 1 1
-1 -3 1
-2 2 -2

Sample Output

Sample Output 1
6

Sample Output 2
3

Hints

• $1 \leq n \leq 3 \times 10^ 5$,且 $n$ 為整數。
• $x_i , y_i$ 皆為 $−10^ 5$ 到 $10^ 5$ 之間的整數 (包含 $−10^ 5$ 與 $10^ 5$)。
• $−1000 \leq w_i \leq 1000$,且 $w_i$ 為整數。
• 對所有 $1 \leq i < j \leq n$,滿足 $x_i \neq x_j$ 或 $y_i \neq y_j$。
• 對所有 $1 \leq i \leq n$,滿足 $x_i \neq 0$ 或 $y_i \neq 0$。

本題共有四組測試題組,條件限制如下所示。每一組可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。
1. ($21\%$) 所有 LED 燈泡的 $y$ 座標相同,$n \leq 100$。
2. ($35\%$) 所有 LED 燈泡的 $y$ 座標相同,$n \leq 10^ 4$。
3. ($11\%$) $n \leq 10^ 4$。
4. ($33\%$) 無額外限制。

Problem Source

2020 TOI 入營考
testdata set by Omelet

Subtasks

No. Testdata Range Constraints Score
1 0~9 所有 LED 燈泡的 $y$ 座標相同,$n \leq 100$ 21
2 0~19 所有 LED 燈泡的 $y$ 座標相同,$n \leq 10^ 4$ 35
3 0~49 $n \leq 10^ 4$ 11
4 0~59 無額外限制 33

Testdata and Limits

No. Time Limit (ms) Memory Limit (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 1 2 3 4
4 1000 524288 65536 1 2 3 4
5 1000 524288 65536 1 2 3 4
6 1000 524288 65536 1 2 3 4
7 1000 524288 65536 1 2 3 4
8 1000 524288 65536 1 2 3 4
9 1000 524288 65536 1 2 3 4
10 1000 524288 65536 2 3 4
11 1000 524288 65536 2 3 4
12 1000 524288 65536 2 3 4
13 1000 524288 65536 2 3 4
14 1000 524288 65536 2 3 4
15 1000 524288 65536 2 3 4
16 1000 524288 65536 2 3 4
17 1000 524288 65536 2 3 4
18 1000 524288 65536 2 3 4
19 1000 524288 65536 2 3 4
20 1000 524288 65536 3 4
21 1000 524288 65536 3 4
22 1000 524288 65536 3 4
23 1000 524288 65536 3 4
24 1000 524288 65536 3 4
25 1000 524288 65536 3 4
26 1000 524288 65536 3 4
27 1000 524288 65536 3 4
28 1000 524288 65536 3 4
29 1000 524288 65536 3 4
30 1000 524288 65536 3 4
31 1000 524288 65536 3 4
32 1000 524288 65536 3 4
33 1000 524288 65536 3 4
34 1000 524288 65536 3 4
35 1000 524288 65536 3 4
36 1000 524288 65536 3 4
37 1000 524288 65536 3 4
38 1000 524288 65536 3 4
39 1000 524288 65536 3 4
40 1000 524288 65536 3 4
41 1000 524288 65536 3 4
42 1000 524288 65536 3 4
43 1000 524288 65536 3 4
44 1000 524288 65536 3 4
45 1000 524288 65536 3 4
46 1000 524288 65536 3 4
47 1000 524288 65536 3 4
48 1000 524288 65536 3 4
49 1000 524288 65536 3 4
50 1000 524288 65536 4
51 1000 524288 65536 4
52 1000 524288 65536 4
53 1000 524288 65536 4
54 1000 524288 65536 4
55 1000 524288 65536 4
56 1000 524288 65536 4
57 1000 524288 65536 4
58 1000 524288 65536 4
59 1000 524288 65536 4