No.3597 Queen Score Attack 2
タグ : / 解いたユーザー数 61
作問者 : 👑
gomaazarasi
ぽえ
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
Problem Statement
There is a grid with $H$ rows and $W$ columns. The cell at the $i(1 \leq i \leq H)$-th row from the top and the $j(1 \leq j \leq W)$-th column from the left is denoted by cell $(i, j)$.
At time $0$, a queen piece is on cell $(sx, sy)$. The queen piece can freely enter and leave cells within the grid, but cannot enter or leave cells outside the grid.
From now on, at each of the times $1, 2, \dots, N$, you can choose and perform any $1$ of the following actions. Here, the time taken to move the queen is ignored.
- Choose $1$ cell that the queen piece can reach in $1$ move, and move the queen piece to that cell.
- Do not move the queen piece.
In addition, you obtain score if the queen piece is on a specific cell at a specific time. Specifically, the condition for obtaining score is as follows.
- If the queen piece is on cell $(x_i, y_i)$ at time $i + 0.5$, you obtain score $c_i$. $(1 \leq i \leq N)$
Find the maximum score that can be obtained by moving the queen piece appropriately.
About how the queen piece moves (click to open)
In $1$ move, the queen piece can advance any number of cells in the vertical, horizontal, or diagonal directions, as long as all cells on the path can be entered and left. However, staying on the current cell cannot be regarded as $1$ move. Strictly, a queen piece on cell $(i, j)$ can move as follows.
- For a positive integer $k$, it can move to cell $(i, j + k)$ if and only if the following condition is satisfied.
- For all integers $l$ satisfying $1 \leq l \leq k$, cell $(i, j + l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i, j - k)$ if and only if the following condition is satisfied.
- For all integers $l$ satisfying $1 \leq l \leq k$, cell $(i, j - l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i + k, j)$ if and only if the following condition is satisfied.
- For all integers $l$ satisfying $1 \leq l \leq k$, cell $(i + l, j)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i - k, j)$ if and only if the following condition is satisfied.
- For all integers $l$ satisfying $1 \leq l \leq k$, cell $(i - l, j)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i + k, j + k)$ if and only if the following condition is satisfied.
- For all integers $l$ satisfying $1 \leq l \leq k$, cell $(i + l, j + l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i + k, j - k)$ if and only if the following condition is satisfied.
- For all integers $l$ satisfying $1 \leq l \leq k$, cell $(i + l, j - l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i - k, j + k)$ if and only if the following condition is satisfied.
- For all integers $l$ satisfying $1 \leq l \leq k$, cell $(i - l, j + l)$ is a cell that the queen piece can enter and leave.
- For a positive integer $k$, it can move to cell $(i - k, j - k)$ if and only if the following condition is satisfied.
- For all integers $l$ satisfying $1 \leq l \leq k$, cell $(i - l, j - l)$ is a cell that the queen piece can enter and leave.
Constraints
- All input values are integers.
- $2 \leq H, W \leq 5 \times 10^5$
- $1 \leq N \leq 5 \times 10^5$
- $1 \leq sx \leq H$
- $1 \leq sy \leq W$
- $1 \leq x_i \leq H$
- $1 \leq y_i \leq W$
- $1 \leq c_i \leq 10^9$
Input
The input is given from standard input in the following format.
$H$ $W$ $sx$ $sy$ $N$ $x_1$ $y_1$ $c_1$ $x_2$ $y_2$ $c_2$ $\vdots$ $x_N$ $y_N$ $c_N$
Output
Output the answer.
Sample
Sample 1
Input
3 3 1 1 3 1 3 4 1 2 5 3 3 10
Output
14
If you move the queen piece to cell $(1, 3)$ at time $1$ and to cell $(3, 3)$ at time $3$, the score obtained is $4 + 10 = 14$.
No larger score can be obtained, so the answer is $14$.
Sample 2
Input
4 4 2 3 5 2 3 4 2 3 5 2 3 6 2 3 7 2 3 8
Output
30
By never moving the queen piece even $1$ time, the score obtained is $4 + 5 + 6 + 7 + 8 = 30$.
Sample 3
Input
4 4 1 1 10 1 2 324321814 2 4 721647114 4 1 453412415 4 3 939186981 3 1 121412531 2 2 781394161 2 4 531518965 1 1 353108590 4 4 731815057 3 2 247891365
Output
3761649393
Note that the answer may not fit in a $32$ bit integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。