2121C.md (2174B)
1 Source: https://codeforces.com/problemset/problem/2121/C 2 3 C. Those Who Are With Us 4 5 time limit per test 6 7 1 second 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 You are given a matrix of integers with $n$ rows and $m$ columns. The cell at the intersection of the $i$-th row and the $j$-th column contains the number $a_{ij}$. 22 23 You can perform the following operation exactly once: 24 25 * Choose two numbers $1 \leq r \leq n$ and $1 \leq c \leq m$. 26 * For all cells $(i, j)$ in the matrix such that $i = r$ or $j = c$, decrease $a_{ij}$ by one. 27 28 You need to find the minimal possible maximum value in the matrix $a$ after performing exactly one such operation. 29 30 Input 31 32 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows. 33 34 The first line of each test case contains two integers $n$ and $m$ ($1 \leq n \cdot m \leq 10^5$) — the number of rows and columns in the matrix. 35 36 The next $n$ lines of each test case describe the matrix $a$. The $i$-th line contains $m$ integers $a_{i1}, a_{i2}, \ldots, a_{im}$ ($1 \leq a_{ij} \leq 100$) — the elements in the $i$-th row of the matrix. 37 38 It is guaranteed that the sum of $n \cdot m$ across all test cases does not exceed $2 \cdot 10^5$. 39 40 Output 41 42 For each test case, output the minimum maximum value in the matrix $a$ after performing exactly one operation. 43 44 Example 45 46 Input 47 48 ``` 49 10 50 51 1 1 52 53 1 54 55 1 2 56 57 1 2 58 59 2 1 60 61 2 62 63 1 64 65 2 2 66 67 4 2 68 69 3 4 70 71 3 4 72 73 1 2 3 2 74 75 3 2 1 3 76 77 2 1 3 2 78 79 4 3 80 81 1 5 1 82 83 3 1 3 84 85 5 5 5 86 87 3 5 1 88 89 4 4 90 91 1 3 3 2 92 93 2 3 2 2 94 95 1 2 2 1 96 97 3 3 2 3 98 99 2 2 100 101 2 2 102 103 1 2 104 105 3 2 106 107 1 2 108 109 2 1 110 111 1 2 112 113 3 3 114 115 2 1 1 116 117 1 2 1 118 119 1 1 2 120 ``` 121 122 Output 123 124 ``` 125 0 126 1 127 1 128 3 129 2 130 4 131 3 132 1 133 1 134 2 135 ``` 136 137 Note 138 139 In the first three test cases, you can choose $r = 1$ and $c = 1$. 140 141 In the fourth test case, you can choose $r = 1$ and $c = 2$. 142 143  144 145 In the fifth test case, you can choose $r = 2$ and $c = 3$. 146 147  148 149 In the sixth test case, you can choose $r = 3$ and $c = 2$.