P12463 [Ynoi Easy Round 2018] Hoshino Rubii


Hoshino Rubii likes to wander on a 2D plane. She is always on integer grid points, and each step can only choose one of up, down, left, or right (that is, increase or decrease the $x$-coordinate or $y$-coordinate by $1$). For $N$ $(N \ge 1)$ integer points $(X_1, Y_1), (X_2, Y_2), \dots, (X_N, Y_N)$ on the plane, we call the **tour** they describe a process where Hoshino Rubii starts from $(X_1, Y_1)$, visits $(X_2, Y_2), (X_3, Y_3), \dots, (X_N, Y_N)$ in order, and then returns to $(X_1, Y_1)$. The **minimum number of steps** Hoshino Rubii needs for a tour is called the tour’s **excitement value**. Now Hoshino Rubii wants to take a tour. She first chooses $n$ integer points $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ on the plane, and plans to insert some additional points among them to determine the sequence of points her next tour must pass through. So she finds another $m$ integer points $(x'_1, y'_1), (x'_2, y'_2), \dots, (x'_m, y'_m)$ on the plane. Each point $(x'_j, y'_j)$ has a **profit** $w_j$ (possibly negative). She may choose one of the previous $n$ points $(x_i, y_i)$ and **insert** $(x'_j, y'_j)$ **right after** $(x_i, y_i)$. Of course, she may also choose not to insert it anywhere. However, to avoid making the tour too complicated, she requires that after each $(x_i, y_i)$, at most one integer point can be inserted. Now, for $k = 1, 2, \dots, n$, she wants to know: after inserting **exactly** $k$ points, what is the maximum possible value of the sum of the next tour’s excitement value and the total profit of the inserted points.

The first line contains two positive integers $n, m$. The next $n$ lines: the $i$-th line contains two integers $x_i, y_i$. The next $m$ lines: the $j$-th line contains three integers $x'_j, y'_j, w_j$.

Output one line with $n$ integers, representing the answers for $k = 1, 2, \dots, n$.

Idea: Aleph1022, Solution: Aleph1022&zx2003, Code: Aleph1022, Data: Aleph1022 ### Sample Explanation #1 One optimal solution when choosing $1$ point changes the tour to $(1, 1), (7, 9), (2, 2), (4, 3)$. The excitement value is $34$, and the profit is $1$, totaling $35$. One optimal solution when choosing $2$ points changes the tour to $(1, 1), (7, 9), (2, 2), (4, 3), (6, 6)$. The excitement value is $44$, and the profit is $3$, totaling $47$. One optimal solution when choosing $3$ points changes the tour to $(1, 1), (7, 9), (2, 2), (5, 4), (4, 3), (6, 6)$. The excitement value is $48$, and the profit is $0$, totaling $48$. ### Sample Explanation #2 One optimal plan when choosing $1$ point is $(0, 4), (5, 1), (3, 4), (0, 1)$. One optimal plan when choosing $2$ points is $(0, 4), (5, 1), (0, 1), (3, 4), (3, 1)$. One optimal plan when choosing $3$ points is $(0, 4), (4, 3), (5, 1), (0, 1), (3, 4), (3, 1)$. ## Constraints For $15\%$ of the testdata, $m \le 10$. For $30\%$ of the testdata, $m \le 200$. For $40\%$ of the testdata, $m \le 600$. For $60\%$ of the testdata, $m \le 10^3$. For $100\%$ of the testdata, $1 \le n \le m \le 10^5$, $|x_i|, |y_i|, |x'_j|, |y'_j|, |w_j| \le 10^8$. Translated by ChatGPT 5