Background

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.

Problem Description

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:

#include "game.h"

In the submitted source file game.cpp, contestants need to implement the following two functions:

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.

long long game(int n, int m, int k, std::vector<int> a, std::vector<int> b, std::vector<int> t, std::vector<int> 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:

g++ grader.cpp game.cpp -o game -O2 -std=c++14 -static

Input Format

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.

Output Format

• 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$.

0 3
4 10 1
0 6 0 1
4 8 6 2
10 2 7 3
0 8 4 4
3 6 2
2 6 0 0
4 0 1 0
5 0 2 0
7 9 2
3 0 1 7
3 6 1 8
6 9 4 9
3 0 7 3
3 6 7 3
3 6 7 5
6 9 10 5

6
-1
35

Hint

【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}

• 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