codeforces-scrape

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

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.