def minim(a,b):
if a==0:
return b
if b==0:
return a
if a<b:
return a
else:
return b
def verify(ma,i,j):
if i!=0: if ma[i-1][j] >= ma[i][j]:
return False
if j!=0: if ma[i][j-1] >= ma[i][j]:
return False
return True
def check(l,c,ma):
som=0
for i in range(l-1,-1,-1):
for j in range(c-1,-1,-1):
if ma[i][j]!=0:
if verify(ma,i,j):
som+=ma[i][j]
else:
return -1
else:
pc=0
pl=0
if i+1<l: pl = ma[i+1][j]
if j+1<c: pc = ma[i][j+1]
ma[i][j] = minim(pl,pc) - 1
if verify(ma,i,j):
som+=ma[i][j]
else:
return -1
return som
n,m = [int(i) for i in input().split()]
matrix=[]
for i in range(n): matrix.append([int(i) for i in input().split()])
var = check(n,m,matrix)
print(var)
#include <bits/stdc++.h>
#include <string>
#include <math.h>
using namespace std;
#define int long long
#define num 998244353
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--){
int n,m;
cin >> n >> m;
bool flag = 1;
int arr[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
cin >> arr[i][j];
}
}
int xr, xc, x;
for(int i = n - 2; i > 0; i--){
for(int j = m - 2; j > 0; j--){
if(!flag){
break;
}
if(arr[i][j] != 0){
continue;
}
xr = arr[i][j+1] - 1;
xc = arr[i+1][j] - 1;
x = min(xr, xc);
if(x <= arr[i-1][j] || x <= arr[i][j-1]){
flag = 0;
break;
}
else{
arr[i][j] = x;
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(i == 0 && j == 0){
continue;
}
if(i == 0){
if(arr[i][j] <= arr[i][j-1]){
flag = 0;
break;
}
}
else if(j == 0){
if(arr[i][j] <= arr[i-1][j]){
flag = 0;
break;
}
}
else if(i > 0 && j > 0){
if(arr[i][j] <= arr[i][j-1] || arr[i][j] <= arr[i-1][j]){
flag = 0;
break;
}
}
}
}
if(!flag){
cout << -1 << endl;
return 0;
}
int sum = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
sum+=arr[i][j];
}
}
cout << sum << endl;
}
return 0;
}322. Coin Change | 307. Range Sum Query - Mutable |
287. Find the Duplicate Number | 279. Perfect Squares |
275. H-Index II | 274. H-Index |
260. Single Number III | 240. Search a 2D Matrix II |
238. Product of Array Except Self | 229. Majority Element II |
222. Count Complete Tree Nodes | 215. Kth Largest Element in an Array |
198. House Robber | 153. Find Minimum in Rotated Sorted Array |
150. Evaluate Reverse Polish Notation | 144. Binary Tree Preorder Traversal |
137. Single Number II | 130. Surrounded Regions |
129. Sum Root to Leaf Numbers | 120. Triangle |
102. Binary Tree Level Order Traversal | 96. Unique Binary Search Trees |
75. Sort Colors | 74. Search a 2D Matrix |
71. Simplify Path | 62. Unique Paths |
50. Pow(x, n) | 43. Multiply Strings |
34. Find First and Last Position of Element in Sorted Array | 33. Search in Rotated Sorted Array |