1231C.md (2079B)
1 Source: https://codeforces.com/problemset/problem/1231/C 2 3 C. Increasing Matrix 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 In this problem, a $n \times m$ rectangular matrix $a$ is called increasing if, for each row of $i$, when go from left to right, the values strictly increase (that is, $a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,m}$) and for each column $j$, when go from top to bottom, the values strictly increase (that is, $a_{1,j} \lt a_{2,j} \lt \dots \lt a_{n,j}$). 22 23 In a given matrix of non-negative integers, it is necessary to replace each value of $0$ with some positive integer so that the resulting matrix is increasing and the sum of its elements is maximum, or find that it is impossible. 24 25 It is guaranteed that in a given value matrix all values of $0$ are contained only in internal cells (that is, not in the first or last row and not in the first or last column). 26 27 Input 28 29 The first line contains integers $n$ and $m$ ($3 \le n, m \le 500$) — the number of rows and columns in the given matrix $a$. 30 31 The following lines contain $m$ each of non-negative integers — the values in the corresponding row of the given matrix: $a_{i,1}, a_{i,2}, \dots, a_{i,m}$ ($0 \le a_{i,j} \le 8000$). 32 33 It is guaranteed that for all $a_{i,j}=0$, $1 \lt i \lt n$ and $1 \lt j \lt m$ are true. 34 35 Output 36 37 If it is possible to replace all zeros with positive numbers so that the matrix is increasing, print the maximum possible sum of matrix elements. Otherwise, print -1. 38 39 Examples 40 41 Input 42 43 ``` 44 4 5 45 1 3 5 6 7 46 3 0 7 0 9 47 5 0 0 0 10 48 8 9 10 11 12 49 ``` 50 51 Output 52 53 ``` 54 144 55 ``` 56 57 Input 58 59 ``` 60 3 3 61 1 2 3 62 2 0 4 63 4 5 6 64 ``` 65 66 Output 67 68 ``` 69 30 70 ``` 71 72 Input 73 74 ``` 75 3 3 76 1 2 3 77 3 0 4 78 4 5 6 79 ``` 80 81 Output 82 83 ``` 84 -1 85 ``` 86 87 Input 88 89 ``` 90 3 3 91 1 2 3 92 2 3 4 93 3 4 2 94 ``` 95 96 Output 97 98 ``` 99 -1 100 ``` 101 102 Note 103 104 In the first example, the resulting matrix is as follows: 105 106 ``` 107 1 3 5 6 7 108 3 6 7 8 9 109 5 7 8 9 10 110 8 9 10 11 12 111 ``` 112 113 In the second example, the value $3$ must be put in the middle cell. 114 115 In the third example, the desired resultant matrix does not exist.