A13801 | The Hard Work of Paparazzi
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You are a paparazzi working in Manhattan.
Manhattan has $r$ south-to-north streets, denoted by numbers $1, 2,\ldots, r$ in order from west to east, and $r$ west-to-east streets, denoted by numbers $1,2,\ldots,r$ in order from south to north. Each of the $r$ south-to-north streets intersects each of the $r$ west-to-east streets; the intersection between the $x$ -th south-to-north street and the $y$ -th west-to-east street is denoted by $(x, y)$ . In order to move from the intersection $(x,y)$ to the intersection $(x', y')$ you need $|x-x'|+|y-y'|$ minutes.
You know about the presence of $n$ celebrities in the city and you want to take photos of as many of them as possible. More precisely, for each $i=1,\dots, n$ , you know that the $i$ -th celebrity will be at the intersection $(x_i, y_i)$ in exactly $t_i$ minutes from now (and he will stay there for a very short time, so you may take a photo of him only if at the $t_i$ -th minute from now you are at the intersection $(x_i, y_i)$ ). You are very good at your job, so you are able to take photos instantaneously. You know that $t_i < t_{i+1}$ for any $i=1,2,\ldots, n-1$ .
Currently you are at your office, which is located at the intersection $(1, 1)$ . If you plan your working day optimally, what is the maximum number of celebrities you can take a photo of?
Manhattan has $r$ south-to-north streets, denoted by numbers $1, 2,\ldots, r$ in order from west to east, and $r$ west-to-east streets, denoted by numbers $1,2,\ldots,r$ in order from south to north. Each of the $r$ south-to-north streets intersects each of the $r$ west-to-east streets; the intersection between the $x$ -th south-to-north street and the $y$ -th west-to-east street is denoted by $(x, y)$ . In order to move from the intersection $(x,y)$ to the intersection $(x', y')$ you need $|x-x'|+|y-y'|$ minutes.
You know about the presence of $n$ celebrities in the city and you want to take photos of as many of them as possible. More precisely, for each $i=1,\dots, n$ , you know that the $i$ -th celebrity will be at the intersection $(x_i, y_i)$ in exactly $t_i$ minutes from now (and he will stay there for a very short time, so you may take a photo of him only if at the $t_i$ -th minute from now you are at the intersection $(x_i, y_i)$ ). You are very good at your job, so you are able to take photos instantaneously. You know that $t_i < t_{i+1}$ for any $i=1,2,\ldots, n-1$ .
Currently you are at your office, which is located at the intersection $(1, 1)$ . If you plan your working day optimally, what is the maximum number of celebrities you can take a photo of?
输入格式
The first line of the input contains two positive integers $r, n$ ( $1\le r\le 500$ , $1\le n\le 100,000$ ) – the number of south-to-north/west-to-east streets and the number of celebrities.
Then $n$ lines follow, each describing the appearance of a celebrity. The $i$ -th of these lines contains $3$ positive integers $t_i, x_i, y_i$ ( $1\le t_i\le 1,000,000$ , $1\le x_i, y_i\le r$ ) — denoting that the $i$ -th celebrity will appear at the intersection $(x_i, y_i)$ in $t_i$ minutes from now.
It is guaranteed that $t_i<t_{i+1}$ for any $i=1,2,\ldots, n-1$ .
Then $n$ lines follow, each describing the appearance of a celebrity. The $i$ -th of these lines contains $3$ positive integers $t_i, x_i, y_i$ ( $1\le t_i\le 1,000,000$ , $1\le x_i, y_i\le r$ ) — denoting that the $i$ -th celebrity will appear at the intersection $(x_i, y_i)$ in $t_i$ minutes from now.
It is guaranteed that $t_i<t_{i+1}$ for any $i=1,2,\ldots, n-1$ .
输出格式
Print a single integer, the maximum number of celebrities you can take a photo of.
输入输出样例
输入 #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
Explanation of the first testcase: There is only one celebrity in the city, and he will be at intersection $(6,8)$ exactly $11$ minutes after the beginning of the working day. Since you are initially at $(1,1)$ and you need $|1-6|+|1-8|=5+7=12$ minutes to reach $(6,8)$ you cannot take a photo of the celebrity. Thus you cannot get any photo and the answer is $0$ .
Explanation of the second testcase: One way to take $4$ photos (which is the maximum possible) is to take photos of celebrities with indexes $3, 5, 7, 9$ (see the image for a visualization of the strategy):
- To move from the office at $(1,1)$ to the intersection $(5,5)$ you need $|1-5|+|1-5|=4+4=8$ minutes, so you arrive at minute $8$ and you are just in time to take a photo of celebrity $3$ .
- Then, just after you have taken a photo of celebrity $3$ , you move toward the intersection $(4,4)$ . You need $|5-4|+|5-4|=1+1=2$ minutes to go there, so you arrive at minute $8+2=10$ and you wait until minute $12$ , when celebrity $5$ appears.
- Then, just after you have taken a photo of celebrity $5$ , you go to the intersection $(6,6)$ . You need $|4-6|+|4-6|=2+2=4$ minutes to go there, so you arrive at minute $12+4=16$ and you wait until minute $17$ , when celebrity $7$ appears.
- Then, just after you have taken a photo of celebrity $7$ , you go to the intersection $(5,4)$ . You need $|6-5|+|6-4|=1+2=3$ minutes to go there, so you arrive at minute $17+3=20$ and you wait until minute $21$ to take a photo of celebrity $9$ .
Explanation of the third testcase: The only way to take $1$ photo (which is the maximum possible) is to take a photo of the celebrity with index $1$ (since $|2-1|+|1-1|=1$ , you can be at intersection $(2,1)$ after exactly one minute, hence you are just in time to take a photo of celebrity $1$ ).
Explanation of the fourth testcase: One way to take $3$ photos (which is the maximum possible) is to take photos of celebrities with indexes $3, 8, 10$ :
- To move from the office at $(1,1)$ to the intersection $(101,145)$ you need $|1-101|+|1-145|=100+144=244$ minutes, so you can manage to be there when the celebrity $3$ appears (at minute $341$ ).
- Then, just after you have taken a photo of celebrity $3$ , you move toward the intersection $(149,379)$ . You need $|101-149|+|145-379|=282$ minutes to go there, so you arrive at minute $341+282=623$ and you wait until minute $682$ , when celebrity $8$ appears.
- Then, just after you have taken a photo of celebrity $8$ , you go to the intersection $(157,386)$ . You need $|149-157|+|379-386|=8+7=15$ minutes to go there, so you arrive at minute $682+15=697$ and you wait until minute $855$ to take a photo of celebrity $10$ .
Explanation of the second testcase: One way to take $4$ photos (which is the maximum possible) is to take photos of celebrities with indexes $3, 5, 7, 9$ (see the image for a visualization of the strategy):
- To move from the office at $(1,1)$ to the intersection $(5,5)$ you need $|1-5|+|1-5|=4+4=8$ minutes, so you arrive at minute $8$ and you are just in time to take a photo of celebrity $3$ .
- Then, just after you have taken a photo of celebrity $3$ , you move toward the intersection $(4,4)$ . You need $|5-4|+|5-4|=1+1=2$ minutes to go there, so you arrive at minute $8+2=10$ and you wait until minute $12$ , when celebrity $5$ appears.
- Then, just after you have taken a photo of celebrity $5$ , you go to the intersection $(6,6)$ . You need $|4-6|+|4-6|=2+2=4$ minutes to go there, so you arrive at minute $12+4=16$ and you wait until minute $17$ , when celebrity $7$ appears.
- Then, just after you have taken a photo of celebrity $7$ , you go to the intersection $(5,4)$ . You need $|6-5|+|6-4|=1+2=3$ minutes to go there, so you arrive at minute $17+3=20$ and you wait until minute $21$ to take a photo of celebrity $9$ .
Explanation of the third testcase: The only way to take $1$ photo (which is the maximum possible) is to take a photo of the celebrity with index $1$ (since $|2-1|+|1-1|=1$ , you can be at intersection $(2,1)$ after exactly one minute, hence you are just in time to take a photo of celebrity $1$ ).
Explanation of the fourth testcase: One way to take $3$ photos (which is the maximum possible) is to take photos of celebrities with indexes $3, 8, 10$ :
- To move from the office at $(1,1)$ to the intersection $(101,145)$ you need $|1-101|+|1-145|=100+144=244$ minutes, so you can manage to be there when the celebrity $3$ appears (at minute $341$ ).
- Then, just after you have taken a photo of celebrity $3$ , you move toward the intersection $(149,379)$ . You need $|101-149|+|145-379|=282$ minutes to go there, so you arrive at minute $341+282=623$ and you wait until minute $682$ , when celebrity $8$ appears.
- Then, just after you have taken a photo of celebrity $8$ , you go to the intersection $(157,386)$ . You need $|149-157|+|379-386|=8+7=15$ minutes to go there, so you arrive at minute $682+15=697$ and you wait until minute $855$ to take a photo of celebrity $10$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted