В этой задаче прямоугольная матрица $$$a$$$ размером $$$n \times m$$$ называется возрастающей, если для каждой строки $$$i$$$ при просмотре слева направо значения строго возрастают (то есть $$$a_{i,1}<a_{i,2}<\dots<a_{i,m}$$$) и для каждого столбца $$$j$$$ при просмотре сверху вниз значения строго возрастают (то есть $$$a_{1,j}<a_{2,j}<\dots<a_{n,j}$$$).
В заданной матрице неотрицательных целых чисел надо заменить каждое значение $$$0$$$ на некоторое положительное целое число так, чтобы получившаяся матрица была возрастающей и сумма её элементов — максимальной, или определить, что так сделать нельзя.
Гарантируется, что в заданной матрице значения все значения $$$0$$$ содержатся только во внутренних ячейках (то есть не в первой или последней строке и не в первом или последнем столбце).
В первой строке записаны целые числа $$$n$$$ и $$$m$$$ ($$$3 \le n, m \le 500$$$) — количество строк и столбцов в заданной матрице $$$a$$$.
В следующих строках содержится по $$$m$$$ целых неотрицательных чисел — значения в соответствующей строке заданной матрицы $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$0 \le a_{i,j} \le 8000$$$).
Гарантируется, что для всех $$$a_{i,j}=0$$$ выполняется $$$1 < i < n$$$ и $$$1 < j < m$$$.
Если возможно заменить все нули на положительные числа, чтобы матрица была возрастающей, выведите максимальную возможную сумму элементов матрицы. Иначе, выведите -1.
4 5 1 3 5 6 7 3 0 7 0 9 5 0 0 0 10 8 9 10 11 12
144
3 3 1 2 3 2 0 4 4 5 6
30
3 3 1 2 3 3 0 4 4 5 6
-1
3 3 1 2 3 2 3 4 3 4 2
-1
В первом примере результирующая матрица выглядит следующим образом:
1 3 5 6 7
3 6 7 8 9
5 7 8 9 10
8 9 10 11 12
Во втором примере в среднюю ячейку обязательно надо поставить значение $$$3$$$.
В третьем примере искомой результирующей матрицы не существует.
Название |
---|