G. Snowstorm

No Submission Yet

Problem Statement

There was a heavy blizzard at LHS, and many students are trapped! Luckily, Jeff was able to identify everyone’s locations. LHS can be described as a \(N\) by \(N\) grid. Each block on the grid has a snow thickness of \(t_{ij}\). A shovel has \(2\) attributes, strength \(s\), and weight \(w\). A shovel of strength \(s\) can only shovel a maximum thickness of \(s\), and immediately breaks when is used with a thicker snow block. There are \(Q\) students scattered around the grid according to Jeff’s list, each stuck at \((a_i,b_i)\) and is trying to get to the exit at \((x,y)\). Each student has a shovel of strength \(s_i\) and weight \(w_i\). Let \(p\) be a rescue path(a sequence of blocks where adjacent ones share an edge, not necessarily simple) from \((a_i,b_i)\) to \((x,y)\), and let \(c\) be the first block of snow on the path that has a thickness greater than \(s_i\). Then the journey from \((a_i,b_i)\) to the block right before \(c\) takes \(0\) energy because the student can just shovel the snow. However, his shovel breaks when he attempts to shovel block \(c\), so he can no longer use it for the rest of the journey. From block \(c\) to \((x,y)\), the student has to manually dig out all the snow blocks while carrying his broken heavy shovel, so the energy cost is the sum of the snow’s thickness + \(d \times w_i\), where \(d\) is the number of snow blocks he digs without his shovel. Note that if \(c\) doesn't exist, then the energy cost is \(0\). There is another catch: the night is rapidly approaching, so the students will freeze to death if the number of snow blocks they have to dig without their shovel is greater than \(M\).

Since you are very intelligent, Jeff has asked you to find the optimal rescue paths. For each student, calculate the minimum energy cost possible (the answer for each student are independent from each other). It can be proven that a rescue path always exists under the given constraints.

Additional Notes

Time Limit:
C++: 3 seconds
Java, Python: 5 seconds
Memory Limit: 256mb


\(1 \leq a_i, b_i, x, y \leq N \leq 200\), \(2N - 1 \leq M \leq 400\), \(Q \leq 10^5\), and \(1 \leq s_i, w_i, t_{ij} \leq 10^9\).

Input format

The first line contains \(5\) numbers \(N\), \(M\), \(Q\), \(x\), and \(y\).
The next \(N\) lines each contain \(N\) numbers, which describe the school grid. The number on the \(i\)th row and \(j\)th column is \(t_{ij}\)
The last \(Q\) lines each contain \(4\) number, \(a_i'\), \(b_i'\), \(s_i'\), \(w_i'\):
\(a_i = (a_i' + lastAnswer - 1 \bmod N) + 1\)
\(b_i = (b_i' + lastAnswer - 1 \bmod N) + 1\)
\(s_i = (s_i' + lastAnswer - 1 \bmod 10^9) + 1\)
\(w_i = (w_i' + lastAnswer - 1 \bmod 10^9) + 1\)
\(lastAnswer\) is the answer of the previous query. Specificially for the first query, \(lastAnswer = 0\).

Output format

Output \(Q\) lines. The \(i\)th line should be the answer for the \(i\)th query.

Sample input:

3 10 2 3 2
5 5 5
3 2 2
3 4 4
2 3 2 3
3 2 999999996 999999994

Sample output


Sample Explanation

For the first query, the optimal path is \(\{(2,3),(2,2),(3,2)\}\). He can shovel the first two blocks with \(0\) energy cost, and the last snow block costs \(4 + 1 \times 3 = 7\), because the block has thickness \(4\), and he has to carry the shovel of weight \(3\) for \(1\) block.
Applying the formula gives us the second query, \((1,3,3,1)\). Since \((1,3)\) is already thicker than he can handle, he has to dig the rest of the way with his hand. The optimal path is \(\{(1,3),(2,3),(2,2),(3,2)\}\), which has the energy cost \(5 + 2 + 2 + 4 + 4 \times 1 = 17\).

Contact Us
LIT Discord Server