No.867 Evacuation Route
タグ : / 解いたユーザー数 39
作問者 :
e869120
/ テスター :
Problem Statement
E869120's house is represented by a grid with $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is called cell $(i, j)$. The top-left cell is $(1, 1)$, and the bottom-right cell is $(H, W)$.
In his house, the difficulty of movement of cell $(i, j)$ is $A_{i, j}$.
He can move around the house through cells that are vertically or horizontally adjacent.
When a disaster of level $K$ occurs, it takes E869120 the following amount of time to move through cells.
- Suppose that he passes through cells $(i_1, j_1)$, $(i_2, j_2)$, $(i_3, j_3)$, ..., $(i_G, j_G)$ in this order (including the starting and ending positions).
- Then, the movement takes $(K^2+A_{i_1,j_1}) + (K^2+A_{i_2,j_2}) + (K^2+A_{i_3,j_3}) + ... + (K^2+A_{i_G,j_G})$ seconds.
- He cannot pass through the same cell twice.
The emergency exit of his house is at cell $(gx, gy)$. Answer the following $Q$ queries.
- A disaster of level $k_i$ occurred while E869120 was at cell $(x_i, y_i)$. How many seconds does it take him to reach the emergency exit cell and escape?
Constraints
All input data satisfy the following constraints.
- $H$ is an integer between $1$ and $250$, inclusive.
- $W$ is an integer between $1$ and $250$, inclusive.
- $Q$ is an integer between $1$ and $500 \ 000$, inclusive.
- $A_{i, j}$ is an integer between $1$ and $99$, inclusive.
- $x_i$ is an integer between $1$ and $H$, inclusive.
- $y_i$ is an integer between $1$ and $W$, inclusive.
- $k_i$ is an integer between $1$ and $1 \ 000 \ 000$, inclusive.
- $gx$ is an integer between $1$ and $H$, inclusive.
- $gy$ is an integer between $1$ and $W$, inclusive.
Input
$H$ $W$
$gx$ $gy$
$A_{1, 1}$ $A_{1, 2}$ $A_{1, 3}$ ... $A_{1, W}$
$A_{2, 1}$ $A_{2, 2}$ $A_{2, 3}$ ... $A_{2, W}$
$A_{3, 1}$ $A_{3, 2}$ $A_{3, 3}$ ... $A_{3, W}$
...
$A_{H, 1}$ $A_{H, 2}$ $A_{H, 3}$ ... $A_{H, W}$
$Q$
$x_1$ $y_1$ $k_1$
$x_2$ $y_2$ $k_2$
$x_3$ $y_3$ $k_3$
...
$x_Q$ $y_Q$ $k_Q$
Output
Output $Q$ lines.
On the $i$-th line, output the answer to the $i$-th query.
Sample
Sample 1
Input
4 5 1 1 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 5 3 1 1 1 1 7 4 5 3 3 2 5 3 5 2
Output
20 52 102 114 54
In the $1$-st query, consider escaping from cell $(3, 1)$ during a disaster of level $1$.
In this case, by moving along cells $(3, 1)$ -> $(2, 1)$ -> $(1, 1)$, he can escape in $(1^2 + 5) + (1^2 + 9) + (1^2 + 3) = 20$ seconds.
Sample 2
Input
7 7 7 3 1 1 1 1 1 1 1 99 99 99 99 99 99 1 99 1 1 1 1 1 1 99 1 99 99 99 99 99 99 1 1 1 1 1 99 99 99 99 99 99 1 99 99 99 1 1 1 1 99 10 1 1 1 1 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 1 8 1 1 9 1 1 10
Output
50 125 248 349 430 529 646 781 934 1105
Sample 3
Input
7 7 7 6 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9 9 9 9 9 9 1 9 9 9 9 9 9 1 9 9 9 9 9 9 1 9 9 9 9 9 9 1 9 9 9 9 9 1 1 2 1 1 4 1 1 5
Output
238 352
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。