codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/4b3aa0367c1a9a817d2476d320d2b05a865187bf.png) 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  ![](https://espresso.codeforces.com/22f9280b9aa6eb557ec71c7245a850a294561fa4.png) 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.