P15350 [COCI 2025/2026 #4] Zombie Apocalypse / Zombie Apocalypse

There are $m$ zombies that are going to attack the city. The zombies set off one by one from a zombie nest that is $(n+1)$ meters away from the city. Each zombie moves at a speed of $1$ meter per second, towards the city. The time interval between consecutive zombies leaving the nest is $1$ second. Let the time when the first zombie departs be the beginning of the $1$-st second. This means: - At the end of the $1$-st second, there is a zombie $1$ meter away from the nest. - At the end of the $2$-nd second, there are zombies $1,2$ meters away from the nest. - At the end of the $3$-rd second, there are zombies $1,2,3$ meters away from the nest. - And so on. When a zombie is $(n+1)$ meters away from the nest, it arrives at the city. Now we place $k$ bombs on the road to defend the city. For each bomb, we know the following information: - The bomb's position (i.e., its distance from the nest). - The bomb's explosion radius. - The time when the bomb is installed. For a bomb with radius $r$, suppose it is installed at position $x$ at time $t$. This bomb will kill a zombie located at position $y$ if and only if $|x-y|\le r$ holds at time $t$. Zombies that have already arrived in the city will not be killed. A killed zombie cannot continue moving. Bombs may be installed at any time and position; in particular, there may be multiple bombs at the same time (and/or) at the same position. Find the number of zombies that arrive in the city.

The first line contains three positive integers $n,m,k$ ($1\le n,m,k\le 200$). The next $k$ lines each contain three integers $x,r,t$ ($1\le x\le n$，$0\le r\le n$，$1\le t\le 500$), describing a bomb, where: - The bomb is installed $x$ meters away from the nest. - The explosion radius is $r$ meters. - The installation time is at the end of the $t$-th second.

Output one line with one integer: the number of zombies that arrive in the city.

### Sample Explanation The explanation for sample 1 is shown in the table below. | Time (end of the $i$-th second) | In the nest | On the road to the city | In the city | | :-: | :-: | :-: | :-: | | Initial state | $\{z, z, z\}$ | $(0, 0, 0, 0, 0, 0)$ | $\{\}$ | | $1$ | $\{z, z\}$ | $(z, 0, 0, 0, 0, 0)$ | $\{\}$ | | $2$ | $\{z\}$ | $(z, z, 0, 0, 0, 0)$ | $\{\}$ | | $2$ | $\{z\}$ | $(z, \underline{z, \mathbf{0}, 0}, 0, 0)$ | $\{\}$ | | $2$ | $\{z\}$ | $(z, 0, 0, 0, 0, 0)$ | $\{\}$ | | $3$ | $\{\}$ | $(z, z, 0, 0, 0, 0)$ | $\{\}$ | | $4$ | $\{\}$ | $(0, z, z, 0, 0, 0)$ | $\{\}$ | | $5$ | $\{\}$ | $(0, 0, z, z, 0, 0)$ | $\{\}$ | | $6$ | $\{\}$ | $(0, 0, 0, z, z, 0)$ | $\{\}$ | | $7$ | $\{\}$ | $(0, 0, 0, 0, z, z)$ | $\{\}$ | | $7$ | $\{\}$ | $(0, 0, 0, 0, \underline{\bf z}, z)$ | $\{\}$ | | $7$ | $\{\}$ | $(0, 0, 0, 0, 0, z)$ | $\{\}$ | | $8$ | $\{\}$ | $(0, 0, 0, 0, 0, 0)$ | $\{z\}$ | | $8$ | $\{\}$ | $(\underline{0, 0, 0, \mathbf{0}, 0, 0})$ | $\{z\}$ | | $8$ | $\{\}$ | $(0, 0, 0, 0, 0, 0)$ | $\{z\}$ | ### Subtasks | Subtask ID | Score | Constraints | | :-: | :-: | :-: | | $1$ | $ 13 $ | $m=1$ | | $2$ | $ 27 $ | $k=1$ | | $3$ | $ 30 $ | No additional constraints. | Translated by ChatGPT 5