← 返回题目列表

Codeforces · 1427/C

C. 狗仔队的辛苦工作

中文机器翻译题面 查看原题

你是在曼哈顿工作的狗仔队。

曼哈顿有 $$$r$$$ 从南到北的街道,从西到东依次用数字 $$$1, 2,\ldots, r$$$ 表示,还有 $$$r$$$ 从西到东的街道,从南到北依次用数字 $$$1,2,\ldots,r$$$ 表示。每条从南到北的 $$$r$$$ 街道均与每条从西到东的 $$$r$$$ 街道相交;第$$$x$$$条从南向北的街道与第$$$y$$$条从西向东的街道之间的交叉点用$$$(x, y)$$$表示。为了从交叉点 $$$(x,y)$$$ 移动到交叉点 $$$(x', y')$$$,您需要 $$$|x-x'|+|y-y'|$$$ 分钟。

您知道这座城市中有 $$$n$$$ 名人,并且您想为尽可能多的人拍摄照片。更准确地说,对于每个 $$$i=1,\dots, n$$$,您知道第 $$$i$$$ 位名人将在 $$$t_i$$$ 分钟后到达十字路口 $$$(x_i, y_i)$$$ (并且他会在那里停留很短的时间,因此只有在从现在开始的第 $$$t_i$$$ 分钟您位于十字路口时,您才可以给他拍照$$$(x_i,y_i)$$$)。你的工作非常出色,所以你可以瞬间拍照。您知道对于任何 $$$i=1,2,\ldots, n-1$$$,$$$t_i < t_{i+1}$$$。

目前您位于办公室,位于十字路口 $$$(1, 1)$$$。如果您以最佳方式计划您的工作日,您最多可以拍摄多少位名人?

输入

输入的第一行包含两个正整数 $$$r, n$$$ ($$$1\le r\le 500$$$, $$$1\le n\le 100,000$$$) – 从南到北/从西到东的街道数量和名人数量。

接下来是 $$$n$$$ 行,每行描述一位名人的外貌。这些行中的第 $$$i$$$ 包含 $$$3$$$ 正整数 $$$t_i, x_i, y_i$$$ ($$$1\le t_i\le 1,000,000$$$, $$$1\le x_i, y_i\le r$$$) — 表示第 $$$i$$$ 位名人将出现在路口$$$(x_i, y_i)$$$ 从现在开始 $$$t_i$$$ 分钟后。

对于任何$$$i=1,2,\ldots, n-1$$$,保证$$$t_i<t_{i+1}$$$。

输出

打印一个整数,即您可以拍摄照片的最大名人数量。

示例

输入 #1

10 1
11 6 8

输出 #1

0

输入 #2

6 9
1 2 6
7 5 1
8 5 5
10 3 1
12 4 4
13 6 2
17 6 6
20 1 4
21 5 4

输出 #2

4

输入 #3

10 4
1 2 1
5 10 9
13 8 8
15 9 9

输出 #3

1

输入#4

500 10
69 477 122
73 186 235
341 101 145
372 77 497
390 117 440
494 471 37
522 300 498
682 149 379
821 486 359
855 157 386

输出#4

3

注意

第一个测试用例的解释:城市中只有一个名人,他将在工作日开始后 $$$(6,8)$$$ 恰好 $$$11$$$ 分钟到达十字路口。由于您最初位于 $$$(1,1)$$$ 并且需要 $$$|1-6|+|1-8|=5+7=12$$$ 分钟才能到达 $$$(6,8)$$$,因此您无法拍摄名人的照片。因此你无法获得任何照片,答案是$$$0$$$。

第二个测试用例的说明:拍摄 $$$4$$$ 照片(这是最大可能)的一种方法是拍摄索引为 $$$3, 5, 7, 9$$$ 的名人照片(请参阅该策略的可视化图像):

- 要从 $$$(1,1)$$$ 的办公室移动到十字路口 $$$(5,5)$$$,您需要 $$$|1-5|+|1-5|=4+4=8$$$ 分钟,因此您在 $$$8$$$ 分钟到达,正好可以为名人 $$$3$$$ 拍照。
- 然后,在你拍完名人 $$$3$$$ 的照片后,你向十字路口 $$$(4,4)$$$ 移动。您需要 $$$|5-4|+|5-4|=1+1=2$$$ 分钟才能到达那里,因此您在 $$$8+2=10$$$ 分钟到达,然后等到 $$$12$$$ 分钟,此时名人 $$$5$$$ 出现。
- 然后,在你拍完名人$$$5$$$的照片后,你就到了十字路口$$$(6,6)$$$。您需要 $$$|4-6|+|4-6|=2+2=4$$$ 分钟才能到达那里,因此您在 $$$12+4=16$$$ 分钟到达,然后等到 $$$17$$$ 分钟,此时名人 $$$7$$$ 出现。
- 然后,在你拍完名人$$$7$$$的照片后,你就到了十字路口$$$(5,4)$$$。您需要 $$$|6-5|+|6-4|=1+2=3$$$ 分钟才能到达那里,因此您在 $$$17+3=20$$$ 分钟到达,等到 $$$21$$$ 分钟才给名人 $$$9$$$ 拍照。

第三个测试用例的说明:拍摄$$$1$$$照片(这是最大可能)的唯一方法是拍摄索引为$$$1$$$的名人照片(因为$$$|2-1|+|1-1|=1$$$,你可以在一分钟后到达十字路口$$$(2,1)$$$,因此你正好可以拍摄名人照片$$$1$$$)。

第四个测试用例的说明:拍摄 $$$3$$$ 照片(这是最大可能)的一种方法是拍摄索引为 $$$3, 8, 10$$$ 的名人照片:

- 要从 $$$(1,1)$$$ 的办公室移动到十字路口 $$$(101,145)$$$,您需要 $$$|1-101|+|1-145|=100+144=244$$$ 分钟,这样您就可以在名人 $$$3$$$ 出现时(在 $$$341$$$ 分钟)到达那里。
- 然后,在你拍完名人 $$$3$$$ 的照片后,你向十字路口 $$$(149,379)$$$ 移动。您需要 $$$|101-149|+|145-379|=282$$$ 分钟才能到达那里,因此您在 $$$341+282=623$$$ 分钟到达,然后等到 $$$682$$$ 分钟,此时名人 $$$8$$$ 出现。
- 然后,在你拍完名人$$$8$$$的照片后,你就到了十字路口$$$(157,386)$$$。您需要 $$$|149-157|+|379-386|=8+7=15$$$ 分钟才能到达那里,因此您在 $$$682+15=697$$$ 分钟到达,然后等到 $$$855$$$ 分钟才拍摄名人 $$$10$$$ 的照片。