2191 . D. 質感測試

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

84.9% (146/172)

Submission's AC Ratio

22.4% (242/1079)

Tags

TOI TOI-pre 2020-TOI-pre

Description

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

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

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

Input Format

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

Output Format

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

Sample Input 1

4
2 1 -1
-5 1 3
-3 1 -2
0 1 4

Sample Output 1

6

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 2

3

Hints

• 1≤n≤3×105，且 n 為整數。
• xi,yi 皆為 −105 到 105 之間的整數 (包含 −105 與 105)。
• −1000≤wi≤1000，且 wi 為整數。
• 對所有 1≤i<j≤n，滿足 xi≠xj 或 yi≠yj。
• 對所有 1≤i≤n，滿足 xi≠0 或 yi≠0。

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

Problem Source

2020 TOI 入營考
testdata set by Omelet

Subtasks

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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
Submit
Back to Top