P8272 [USACO22OPEN] Apple Catching G

Apples are falling from the sky. At certain times, a fixed number of apples will fall onto the number line. At certain times, some of Farmer John’s cows will arrive on the number line and start catching apples. If an apple falls onto the number line without being caught by a cow, it disappears forever. If a cow and an apple arrive at the same time, the cow catches the apple. Each cow can move $1$ unit of distance per second. Once a cow catches an apple, she will leave the number line. If FJ’s cows cooperate in the best possible way, how many apples can they catch in total?

The first line contains $N$ ($1\le N\le 2\cdot 10^5$), the number of times apples fall onto the number line or FJ’s cows appear. Each of the next $N$ lines contains four integers $q_i$, $t_i$, $x_i$, and $n_i$ ($q_i\in \{1,2\}, 0\le t_i\le 10^9, 0\le x_i\le 10^9, 1\le n_i\le 10^3$). - If $q_i=1$, it means $n_i$ of FJ’s cows arrive at position $x_i$ on the number line at time $t_i$. - If $q_i=2$, it means $n_i$ apples fall at position $x_i$ on the number line at time $t_i$. The input guarantees that all ordered pairs $(t_i,x_i)$ are distinct.

Output the maximum total number of apples that FJ’s cows can catch.

[Sample Explanation 1] In this example, none of the $100$ apples that land at time $t=5$ can be caught. Here is one way to catch $10$ apples: - All six cows that arrive at time $t=4$ each catch one apple that lands at time $t=8$. - One cow that arrives at time $t=2$ catches one apple that lands at time $t=8$. - The remaining three cows that arrive at time $t=2$ each catch one apple that lands at time $t=6$. [Sample Explanation 2] Again, none of the apples that land at time $t=5$ can be caught. In addition, none of the cows that arrive at time $t=2$ can catch any apples that land at time $t=8$. Here is one way to catch $9$ apples: - All six cows that arrive at time $t=4$ each catch one apple that lands at time $t=8$. - The remaining three cows that arrive at time $t=2$ each catch one apple that lands at time $t=6$. Translated by ChatGPT 5