409509: GYM103604 D Rainy Garden

Memory Limit：1024 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

D. Rainy Gardentime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

Farmer Dave has a big parcel where he harvests veggies. Unfortunately, there was a terrible storm which flooded some of the regions of his beloved parcel. You can visualize the parcel like a grid of $$$N$$$x$$$M$$$, where every region (cell) is having a non-negative quantity of water.

Farmer Dave happens to live in capitalism, where having a second job is strongly encouraged. He's not only a farmer, but also a part-time wizard! One magic trick with his wand allows him to slide all of the cells towards any cardinal point (North, South, East, West). By "sliding" is understood that all of the cells will shift towards the chosen direction. Any two adjacent cells holding the same quantity of water and moving towards the same cardinal point will merge into one having the same quantity incremented by one. Merging happens only if there is a strictly positive quantity of water in the cells to be merged and (it happens) continuously until no merge is possible. The order in which the cells get merged is opposite to the direction towards the cells are moving. For instance, if North is chosen, the first merged cells will be the northernmost ones and then further the southern cells.

If he plans to use the magic trick, the nature will punish Dave with one drop of water in the first available empty cell, North to South and then from West to East. If the nature can't apply the punishment (due to no empty cell available) then the nature will burn his magic wand so that he won't be able to do his magic anymore.

For example, for the following matrix the application of one magic trick towards North results in:

$$$$$$ \begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \cr \hline 1 & 2 & 3 & 4 \cr \hline 1 & 1 & 3 & 5 \cr \hline 1 & 1 & 4 & 0 \cr \hline \end{array} $$$$$$ Figure 1: Initial parcel
$$$$$$ \begin{array}{|c|c|c|c|} \hline 1 & 2 & 3 & 4 \cr \hline 1 & 2 & 3 & 4 \cr \hline 1 & 1 & 3 & 5 \cr \hline 1 & 1 & 4 & 1 \cr \hline \end{array} $$$$$$ Figure 2: Mother nature punishes the wizard. One drop of water appears in cell (4, 4)
$$$$$$ \begin{array}{|c|c|c|c|} \hline 2 & 3 & 4 & 5 \cr \hline 2 & 2 & 3 & 5 \cr \hline 0 & 0 & 4 & 1 \cr \hline 0 & 0 & 0 & 0 \cr \hline \end{array} $$$$$$ Figure 3: Slide towards North, first merge round, still 1st magic trick
$$$$$$ \begin{array}{|c|c|c|c|} \hline 3 & 3 & 4 & 6 \cr \hline 0 & 2 & 3 & 1 \cr \hline 0 & 0 & 4 & 0 \cr \hline 0 & 0 & 0 & 0 \cr \hline \end{array} $$$$$$ Figure 4: Slide towards North, second merge round, still 1st magic trick

As another example, for the following matrix the application of one magic trick towards East results in:

$$$$$$ \begin{array}{|c|c|c|c|} \hline 1 & 0 & 0 & 0 \cr \hline 0 & 0 & 0 & 0 \cr \hline 1 & 0 & 0 & 0 \cr \hline 2 & 0 & 0 & 2 \cr \hline \end{array} $$$$$$ Figure 5: Initial parcel
$$$$$$ \begin{array}{|c|c|c|c|} \hline 1 & 1 & 0 & 0 \cr \hline 0 & 0 & 0 & 0 \cr \hline 1 & 0 & 0 & 0 \cr \hline 2 & 0 & 0 & 2 \cr \hline \end{array} $$$$$$ Figure 6: Mother nature punishes the wizard. One drop of water appears in cell (1, 2)
$$$$$$ \begin{array}{|c|c|c|c|} \hline 0 & 0 & 0 & 2 \cr \hline 0 & 0 & 0 & 0 \cr \hline 0 & 0 & 0 & 1 \cr \hline 0 & 0 & 0 & 3 \cr \hline \end{array} $$$$$$ Figure 7: Slide towards Eas

Farmer Dave got at most $$$K$$$ magic tricks available and he believes that he will dry his parcel the fastest if he uses his super-skills to reach the highest possible quantity of water in a single cell. We believe this is stupid and that it does not make any sense, but let's prove that to him.

As Dave needs more data samples to understand that this approach is not a good heuristic for his parcel to get dry quicker, he will want you to compute the answer for more parcels.

Input

he first line contains three integers: $$$N$$$ $$$(1 \leq N \leq 2500)$$$, $$$M$$$ $$$(1 \leq M \leq 2500)$$$ and $$$K$$$ $$$(1 \leq K * K \leq min(N, M))$$$. Moreover, $$$(1 \leq N * M \leq 2500)$$$.

The following $$$N$$$ lines will each contain $$$M$$$ integers, having the values in the interval [$$$0,10^6$$$].

The aforementioned format will apply to the subsequent parcels, so the contestants are advised to read until the end-of-file marker. It is guaranteed that the total number of cells (among all of the tests) is at most $$$2500$$$.

Output

There will be as many lines as tests and each of them will contain an integer, the highest quantity of water which can end up in a cell using the optional given magic trick allowance.

ExampleInput
4 4 1
1 2 3 4
1 2 3 4
1 1 3 5
1 1 4 0
4 4 2
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Output
6
2

Source/Category

加入题单

算法标签：