1941E.md (3338B)
1 Source: https://codeforces.com/problemset/problem/1941/E 2 3 E. Rudolf and k Bridges 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Bernard loves visiting Rudolf, but he is always running late. The problem is that Bernard has to cross the river on a ferry. Rudolf decided to help his friend solve this problem. 22 23 The river is a grid of $n$ rows and $m$ columns. The intersection of the $i$-th row and the $j$-th column contains the number $a_{i,j}$ — the depth in the corresponding cell. All cells in the first and last columns correspond to the river banks, so the depth for them is $0$. 24 25  The river may look like this. 26 27 Rudolf can choose the row $(i,1), (i,2), \ldots, (i,m)$ and build a bridge over it. In each cell of the row, he can install a support for the bridge. The cost of installing a support in the cell $(i,j)$ is $a_{i,j}+1$. Supports must be installed so that the following conditions are met: 28 29 1. A support must be installed in cell $(i,1)$; 30 2. A support must be installed in cell $(i,m)$; 31 3. The distance between any pair of adjacent supports must be no more than $d$. The distance between supports $(i, j_1)$ and $(i, j_2)$ is $|j_1 - j_2| - 1$. 32 33 Building just one bridge is boring. Therefore, Rudolf decided to build $k$ bridges on consecutive rows of the river, that is, to choose some $i$ ($1 \le i \le n - k + 1$) and independently build a bridge on each of the rows $i, i + 1, \ldots, i + k - 1$. Help Rudolf minimize the total cost of installing supports. 34 35 Input 36 37 The first line contains a single integer $t$ $(1 \le t \le 10^3)$ — the number of test cases. The descriptions of the test cases follow. 38 39 The first line of each test case contains four integers $n$, $m$, $k$, and $d$ ($1 \le k \le n \le 100$, $3 \le m \le 2 \cdot 10^5$, $1 \le d \le m$) — the number of rows and columns of the field, the number of bridges, and the maximum distance between supports. 40 41 Then follow $n$ lines, $i$-th line contains $m$ positive integers $a_{i, j}$ ($0 \le a_{i, j} \le 10^6$, $a_{i, 1} = a_{i, m} = 0$) — the depths of the river cells. 42 43 It is guaranteed that the sum of $n \cdot m$ for all sets of input data does not exceed $2 \cdot 10^5$. 44 45 Output 46 47 For each test case, output a single number — the minimum total cost of supports installation. 48 49 Example 50 51 Input 52 53 ``` 54 5 55 56 3 11 1 4 57 58 0 1 2 3 4 5 4 3 2 1 0 59 60 0 1 2 3 2 1 2 3 3 2 0 61 62 0 1 2 3 5 5 5 5 5 2 0 63 64 4 4 2 1 65 66 0 3 3 0 67 68 0 2 1 0 69 70 0 1 2 0 71 72 0 3 3 0 73 74 4 5 2 5 75 76 0 1 1 1 0 77 78 0 2 2 2 0 79 80 0 2 1 1 0 81 82 0 3 2 1 0 83 84 1 8 1 1 85 86 0 10 4 8 4 4 2 0 87 88 4 5 3 2 89 90 0 8 4 4 0 91 92 0 3 4 8 0 93 94 0 8 1 10 0 95 96 0 10 1 5 0 97 ``` 98 99 Output 100 101 ``` 102 4 103 8 104 4 105 15 106 14 107 ``` 108 109 Note 110 111 In the first test case, it is most profitable to build a bridge on the second row. 112 113  It is not a top view, but side view: gray cells — bridge itself, white cells are empty, black cells — supports, blue cells — water, brown cells — river bottom. 114 115 In the second test case, it is most profitable to build bridges on the second and third rows. The supports will be placed in cells $(2, 3)$, $(3, 2)$, and on the river banks. 116 117 In the third test case the supports can be placed along the river banks.