P15246 [WC2026] Cat and Mouse

6s 1G. When submitting on Luogu, please use a language version no lower than C++17, and you do not need to include the `game.h` header file.

*Tom and Jerry* is a well-known cartoon. Based on it, Xiao G designed a game. In this game, the player needs to help Tom use robotic cats to catch Jerry. Jerry’s activity range is the interval $[0, m]$ on the number line. At the initial moment (i.e., at second $0$), Jerry may be at any position within this interval. After that, it can move freely within this interval, but its speed at any time will not exceed $1$ unit length per second. Tom has $n$ robotic cats available to deploy. The cost to deploy the $i$-th ($1 \le i \le n$) robotic cat is $w_i$. If the $i$-th ($1 \le i \le n$) robotic cat is deployed, it will appear at position $a_i$ at time $t_i$, then move uniformly at a speed of $1$ unit length per second toward position $b_i$, and disappear after it arrives. Jerry initially has $k$ health points. Each time it completely coincides with a robotic cat (i.e., there exists some moment when their positions are exactly the same), its health will decrease by $1$, and that robotic cat will also become invalid. When Jerry’s health is less than or equal to $0$, Tom successfully catches Jerry. Xiao G requires Tom to deploy the robotic cats at the initial moment. Therefore, the player needs to choose some robotic cats to deploy before the game starts. The player wins if and only if, after deploying the robotic cats, for all possible movement paths of Jerry, Tom can successfully catch Jerry. Xiao G designed many levels for this game and invited you to test them. To control the difficulty, Xiao G plans to set a reasonable upper bound on the total deployment cost. You need to help Xiao G find the minimum total cost of robotic cats that must be deployed for the player to win. ### 【Implementation Details】 Contestants do not need to, and should not, implement the `main` function. Contestants need to make sure the submitted program includes the header file `game.h`, i.e., add the following code at the beginning of the program: ```cpp #include "game.h" ``` In the submitted source file `game.cpp`, contestants need to implement the following two functions: ```cpp void init(int c, int t); ``` - $c, t$ denote the test point ID and the number of testdata groups, respectively. $c = 0$ means this test point is the sample. - For each test point, this function will be called by the interactive library exactly once when the program starts running. ```cpp long long game(int n, int m, int k, std::vector a, std::vector b, std::vector t, std::vector w); ``` - $n, m, k$ denote the number of robotic cats, Jerry’s activity range, and Jerry’s initial health points, respectively. - For $0 \le i < n$, $a_i, b_i, t_i, w_i$ denote the appearance position, final position, appearance time, and deployment cost of the $(i+1)$-th robotic cat, respectively. - This function should return the minimum total cost. In particular, if it is impossible to win even after deploying all robotic cats, return $-1$. - For each test point, this function will be called by the interactive library exactly $t$ times. Note: In all cases, the time required by the interactive library will not exceed $0.1$ seconds, and its memory usage is fixed and will not exceed $64$ MiB. ### 【How to Test with the Provided Program】 `grader.cpp` under the problem directory is a reference implementation of the interactive library. The interactive library used in the final test is different from this reference implementation, so contestants’ solutions should not rely on the implementation details of the interactive library. Contestants can compile an executable in this directory using the following command: ```bash g++ grader.cpp game.cpp -o game -O2 -std=c++14 -static ```

For the compiled executable: - The executable will read input from standard input in the following format: - The first line contains two non-negative integers $c, t$, denoting the test point ID and the number of testdata groups. - Then follow the testdata groups one by one. For each testdata group: * The first line contains three positive integers $n, m, k$, denoting the number of robotic cats, Jerry’s activity range, and Jerry’s initial health points. * The $(i+1)$-th line ($1 \le i \le n$) contains four non-negative integers $a_i, b_i, t_i, w_i$, denoting the appearance position, final position, appearance time, and deployment cost of the $i$-th robotic cat.

- The executable will output data to standard output in the following format: - For each testdata group, output one line with one integer, denoting the minimum total cost. In particular, if it is impossible to win even after deploying all robotic cats, output $-1$.

### 【Sample 1 Explanation】 This sample contains three testdata groups. For the first testdata group, the player can choose to deploy robotic cats $1, 2, 3$, with a total cost of $1 + 2 + 3 = 6$. If the player chooses to deploy robotic cats $1, 3$, then when Jerry is initially at position $7$ and moves uniformly from second $6$ at a speed of $1$ unit length per second to position $1$, Tom cannot successfully catch Jerry. For the second testdata group, when Jerry is initially at position $5.5$ and does not move, it will only completely coincide with robotic cat $1$ at second $3.5$, so it is impossible to win even after deploying all robotic cats. For the third testdata group, the player can choose to deploy robotic cats $1, 2, 3, 4, 5, 7$, with a total cost of $7 + 8 + 9 + 3 + 3 + 5 = 35$. ### 【Sample 2】 See `game/game2.in` and `game/game2.ans` in the contestant directory. This sample satisfies the constraints of test points $3, 4$. ### 【Sample 3】 See `game/game3.in` and `game/game3.ans` in the contestant directory. This sample satisfies the constraints of test points $5, 6$. ### 【Sample 4】 See `game/game4.in` and `game/game4.ans` in the contestant directory. This sample satisfies the constraints of test points $10 \sim 12$. ### 【Sample 5】 See `game/game5.in` and `game/game5.ans` in the contestant directory. This sample satisfies the constraints of test points $16 \sim 18$. ### 【Sample 6】 See `game/game6.in` and `game/game6.ans` in the contestant directory. This sample satisfies the constraints of test points $23, 24$. ### 【Sample 7】 See `game/game7.in` and `game/game7.ans` in the contestant directory. This sample satisfies the constraints of test point $25$. ### 【Description of Provided Files】 In this problem directory: 1. `grader.cpp` is the provided reference implementation of the interactive library. 2. `game.h` is the header file; contestants do not need to care about the specific content. 3. `template_game.cpp` is the provided sample code; contestants may refer to it and implement their own code. Contestants should back up all provided files properly. In the final evaluation, only `game.cpp` in this problem directory will be tested; modifications to files other than this program will not affect the evaluation result. ### 【Constraints】 Let $N, S$ be the sums of $n$ and $nk$ over all testdata within a single test point, respectively. For all testdata, we have: - $1 \le t \le 20$. - $1 \le n \le 5 \times 10^4$, $N \le 3 \times 10^5$. - $1 \le m \le 10^9$, $1 \le k \le 10$, $S \le 10^6$. - For all $1 \le i \le n$, $0 \le a_i, b_i \le m$, and $0 \le t_i, w_i \le 10^9$. ::cute-table{tuack} | Test point ID | $n \le$ | $k \le$ | Special property | |:-:|:-:|:-:|:-:| | $1, 2$ | $10$ | $10$ | A | | $3, 4$ | $10^3$ | $1$ | BC | | $5, 6$ | $5 \times 10^4$ | ^ | CD | | $7, 8$ | $10^3$ | $10$ | C | | $9$ | $5 \times 10^4$ | ^ | CD | | $10 \sim 12$ | ^ | ^ | C | | $13, 14$ | $10^3$ | $1$ | None | | $15$ | $5 \times 10^4$ | ^ | D | | $16 \sim 18$ | ^ | ^ | None | | $19 \sim 22$ | $80$ | $10$ | None | | $23, 24$ | $300$ | ^ | None | | $25$ | $5 \times 10^4$ | ^ | None | - Special property A: $m \le 10$, and for all $1 \le i \le n$, $t_i, w_i \le 10$. - Special property B: $m \le 10^3$, and for all $1 \le i \le n$, $t_i \le 10^6$. - Special property C: for all $1 \le i \le n$, $w_i = 0$. - Special property D: for all $1 \le i \le n$, $a_i \le b_i$. ### 【Scoring】 Note: - Contestants should not obtain internal information of the interactive library by illegal means, such as directly interacting with standard input/output streams. Such behavior will be regarded as cheating. - The interactive library used in the final evaluation is different from the sample interactive library. This problem is first subject to the same limits as traditional problems. For example, a compilation error will cause the entire problem to receive $0$ points; runtime error, time limit exceeded, memory limit exceeded, etc. will cause the corresponding test point to receive $0$ points. Contestants can only access variables they define and variables provided by the interactive library; attempting to access other address spaces may cause compilation errors or runtime errors. Based on the above conditions: - For each test point, the program gets full score if and only if the returned answer is correct for every call to the `game` function. Translated by ChatGPT 5