TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

100.0% (6/6)

Submission's AC Ratio

24.0% (18/75)

Tags

Description

又是某天,蝸牛老師買了一塊大小為 R×C 的導火面板,將它鋪平並放在一間很大的教室中。而得知這件消息的搗蛋鬼小寧再次決定將這塊導火面板燒掉。

小寧的野心再次傳進了蝸牛老師耳中,他得知小寧打算設置 N 個起火點,第 i 個起火點將會在時間 ti 被設置在導火面板中 (xi,yi) 的位置(導火面板的左上角是 (0,0)、最右下角是 (R,C))。當起火點被設置的瞬間便會馬上開始燃燒並燃燒殆盡,且接下來會持續以 1 格的秒速向上下左右四個方向燃燒。也就是說,對於任何一個介於 (0,0)(R,C) 的實數點 (x,y),只要時間 t 存在一個起火點 i 滿足 |xix|+|yiy|tti,點 (x,y) 就會被視為燃燒殆盡。

不幸的是,蝸牛老師手邊有工作無法離身,不過他想知道這條導火面板要多久才會被燃燒殆盡,因為小寧肯定會等到導火面板燒完後才離開現場,這樣蝸牛老師就可以分配時間過去抓他。你可以告訴蝸牛老師在何時導火面板才會被燃燒殆盡嗎?注意到,因為蝸牛老師覺得小數點很煩,所以請你找出最早在哪個面板才會被燃燒殆盡。

註:若某個起火點要設置的當下,該位置已被燃燒完畢,則小寧會跳過這次的設置。
註2:若 R=0C=0,你可以把導火面板當作一條導火線;若 R=C=0,你可以把導火面板當作一個火種,即第一次點燃的瞬間整塊面板便瞬間被燃燒殆盡。

Input Format

首行有三個正整數 N,R,C,代表起火點的個數和導火面板的大小。
接下來 N 行,第 i 行三個整數 ti,xi,yi,代表第 i 個起火點的將會在時間 ti 被設置在導火面板中 (xi,yi) 的位置。
所有數字皆以單一空格隔開。

Output Format

輸出幾個整數秒後面板會被燃燒殆盡。

Sample Input 1

1 3 4
3 2 2

Sample Output 1

7

Sample Input 2

2 0 9
1 0 1
1 0 9

Sample Output 2

5

Sample Input 3

3 5 8
1 0 3
4 3 7
2 4 2

Sample Output 3

7

Hints

測資限制:

  • 1N5×104
  • 0R,C109
  • 1ti109
  • 0xiR
  • 0yiC

本題共有 4 組測試題組,條件限制如下所示。每一組可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。

  1. (26%) R=0
  2. (21%) R,C2000
  3. (37%) R,C105
  4. (16%) 無額外限制。

Problem Source

2021 板中TOI模考模擬賽

Subtasks

No. Testdata Range Constraints Score
1 3~23 R=0 26
2 24~52 R,C2000 21
3 24~73 R,C105 37
4 0~94 無額外限制。 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 524288 65536 4
1 5000 524288 65536 4
2 5000 524288 65536 4
3 5000 524288 65536 1 4
4 5000 524288 65536 1 4
5 5000 524288 65536 1 4
6 5000 524288 65536 1 4
7 5000 524288 65536 1 4
8 5000 524288 65536 1 4
9 5000 524288 65536 1 4
10 5000 524288 65536 1 4
11 5000 524288 65536 1 4
12 5000 524288 65536 1 4
13 5000 524288 65536 1 4
14 5000 524288 65536 1 4
15 5000 524288 65536 1 4
16 5000 524288 65536 1 4
17 5000 524288 65536 1 4
18 5000 524288 65536 1 4
19 5000 524288 65536 1 4
20 5000 524288 65536 1 4
21 5000 524288 65536 1 4
22 5000 524288 65536 1 4
23 5000 524288 65536 1 4
24 5000 524288 65536 2 3 4
25 5000 524288 65536 2 3 4
26 5000 524288 65536 2 3 4
27 5000 524288 65536 2 3 4
28 5000 524288 65536 2 3 4
29 5000 524288 65536 2 3 4
30 5000 524288 65536 2 3 4
31 5000 524288 65536 2 3 4
32 5000 524288 65536 2 3 4
33 5000 524288 65536 2 3 4
34 5000 524288 65536 2 3 4
35 5000 524288 65536 2 3 4
36 5000 524288 65536 2 3 4
37 5000 524288 65536 2 3 4
38 5000 524288 65536 2 3 4
39 5000 524288 65536 2 3 4
40 5000 524288 65536 2 3 4
41 5000 524288 65536 2 3 4
42 5000 524288 65536 2 3 4
43 5000 524288 65536 2 3 4
44 5000 524288 65536 2 3 4
45 5000 524288 65536 2 3 4
46 5000 524288 65536 2 3 4
47 5000 524288 65536 2 3 4
48 5000 524288 65536 2 3 4
49 5000 524288 65536 2 3 4
50 5000 524288 65536 2 3 4
51 5000 524288 65536 2 3 4
52 5000 524288 65536 2 3 4
53 5000 524288 65536 3 4
54 5000 524288 65536 3 4
55 5000 524288 65536 3 4
56 5000 524288 65536 3 4
57 5000 524288 65536 3 4
58 5000 524288 65536 3 4
59 5000 524288 65536 3 4
60 5000 524288 65536 3 4
61 5000 524288 65536 3 4
62 5000 524288 65536 3 4
63 5000 524288 65536 3 4
64 5000 524288 65536 3 4
65 5000 524288 65536 3 4
66 5000 524288 65536 3 4
67 5000 524288 65536 3 4
68 5000 524288 65536 3 4
69 5000 524288 65536 3 4
70 5000 524288 65536 3 4
71 5000 524288 65536 3 4
72 5000 524288 65536 3 4
73 5000 524288 65536 3 4
74 5000 524288 65536 4
75 5000 524288 65536 4
76 5000 524288 65536 4
77 5000 524288 65536 4
78 5000 524288 65536 4
79 5000 524288 65536 4
80 5000 524288 65536 4
81 5000 524288 65536 4
82 5000 524288 65536 4
83 5000 524288 65536 4
84 5000 524288 65536 4
85 5000 524288 65536 4
86 5000 524288 65536 4
87 5000 524288 65536 4
88 5000 524288 65536 4
89 5000 524288 65536 4
90 5000 524288 65536 4
91 5000 524288 65536 4
92 5000 524288 65536 4
93 5000 524288 65536 4
94 5000 524288 65536 4