2059C.md (3274B)
1 Source: https://codeforces.com/problemset/problem/2059/C 2 3 C. Customer Service 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 Nikyr has started working as a queue manager at the company "Black Contour." He needs to choose the order of servicing customers. There are a total of $n$ queues, each initially containing $0$ people. In each of the next $n$ moments of time, there are two sequential events: 22 23 1. New customers arrive in all queues. More formally, at the $j$-th moment of time, the number of people in the $i$-th queue increases by a positive integer $a_{i,j}$. 24 2. Nikyr chooses exactly one of the $n$ queues to be served at that moment in time. The number of customers in this queue becomes $0$. 25 26 Let the number of people in the $i$-th queue after all events be $x_i$. Nikyr wants MEX$^{\dagger}$ of the collection $x_1, x_2, \ldots, x_n$ to be as large as possible. Help him determine the maximum value he can achieve with an optimal order of servicing the queues. 27 28 $^{\dagger}$The minimum excluded (MEX) of a collection of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $y$ which does not occur in the collection $c$. 29 30 For example: 31 32 * $\operatorname{MEX}([2,2,1])= 0$, since $0$ does not belong to the array. 33 * $\operatorname{MEX}([3,1,0,1]) = 2$, since $0$ and $1$ belong to the array, but $2$ does not. 34 * $\operatorname{MEX}([0,3,1,2]) = 4$, since $0$, $1$, $2$, and $3$ belong to the array, but $4$ does not. 35 36 Input 37 38 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. The description of the test cases follows. 39 40 The first line of each test case contains a single integer $n$ ($1 \le n \le 300$) — the number of queues and moments of time. 41 42 The $i$-th of the next $n$ lines contains $n$ integers $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$ ($1 \le a_{i,j} \le 10^9$) — the number of new customers in the $i$-th queue at each moment of time. 43 44 It is guaranteed that the sum of $n^2$ over all test cases does not exceed $2 \cdot 10^5$. 45 46 Output 47 48 For each test case, output a single integer — the maximum value of $\operatorname{MEX}([x_1, x_2, \ldots, x_n])$ that can be achieved. 49 50 Example 51 52 Input 53 54 ``` 55 4 56 57 2 58 59 1 2 60 61 2 1 62 63 2 64 65 10 10 66 67 10 10 68 69 3 70 71 2 3 3 72 73 4 4 1 74 75 2 1 1 76 77 4 78 79 4 2 2 17 80 81 1 9 3 1 82 83 5 5 5 11 84 85 1 2 1 1 86 ``` 87 88 Output 89 90 ``` 91 2 92 1 93 3 94 3 95 ``` 96 97 Note 98 99 In the first test case, the second queue can be served at time $1$, and the first queue at time $2$. There will be $x_1 = 0$ people left in the first queue and $x_2 = 1$ person left in the second queue. Therefore, the answer is $\operatorname{MEX}([0, 1]) = 2$. 100 101 In the second test case, the first queue can be served both times. There will be $x_1 = 0$ people left in the first queue and $x_2 = 20$ people left in the second queue. Therefore, the answer is $\operatorname{MEX}([0, 20]) = 1$. 102 103 In the third test case, the third queue can be served at time $1$, the second queue at time $2$, and the first queue at time $3$. There will be $x_1 = 0$ people left in the first queue, $x_2 = 1$ person left in the second queue, and $x_3 = 2$ people left in the third queue. Therefore, the answer is $\operatorname{MEX}([0, 1, 2]) = 3$.