You are given a matrix A that consists of N rows and M columns. Every number in the matrix is either zero or one. Calculate the number of such triples (i, j, h) where for all the pairs (x, y), where both x and y belong to [1; h] if y ≥ x, A[i+x-1][j+y-1] equals to one. Of course, the square (i, j, i+h-1, j+h-1) should be inside of this matrix. In other words, we're asking you to calculate the amount of square submatrices of a given matrix which have ones on and above their main diagonal.

------ Input ------ 

The first line of the input consists of two integers - N and M.

The following N lines describe the matrix. Each line consists of M characters that are either zero or one.

------ Output ------ 

Output should consist of a single integer - the answer to the problem.

------ Example ------ 

Input:
2 3
011
111

Output:
6

------ Scoring ------ 

Subtask 1 (9 points): 1 ≤ N,M ≤ 2000, All the numbers in the matrix are equal to one.

Subtask 2 (12 points): 1 ≤ N,M ≤ 10. 

Subtask 3 (34 points): 1 ≤ N,M ≤ 30. 

Subtask 4 (17 points): 1 ≤ N,M ≤ 150. 

Subtask 5 (28 points): 1 ≤ N,M ≤ 2000.

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
(n, m) = [int(c) for c in input().split()]
matrix = []
for i in range(n):
	arr = [int(c) for c in input()]
	matrix.append(arr)
c = [0 for i in range(m)]
ans = 0
for i in range(n - 1, -1, -1):
	last = 0
	for j in range(m):
		c[j] = 0 if not matrix[i][j] else c[j] + 1
	for j in range(m):
		last = min(last + 1, c[j])
		ans += last
print(ans)


(N, M) = map(int, input().split())
A = []
for _ in range(N):
	A.append(input())
reach = [[1 for _ in range(M)] for _ in range(N)]
for i in range(N):
	for j in range(M - 1, -1, -1):
		if A[i][j] == '0':
			reach[i][j] = 0
		elif j != M - 1:
			reach[i][j] = 1 + reach[i][j + 1]
ij2h = [[0 for _ in range(M)] for _ in range(N)]
for i in range(N - 1, -1, -1):
	for j in range(M - 1, -1, -1):
		if i == N - 1 or j == M - 1:
			ij2h[i][j] = 1 if A[i][j] == '1' else 0
		else:
			ij2h[i][j] = min(reach[i][j], ij2h[i + 1][j + 1] + 1)
ans = 0
for i in range(N):
	ans += sum(ij2h[i])
print(ans)


(n, m) = map(int, input().split())
a = []
for i in range(n):
	a.append(list(map(int, list(input()))))
	for j in range(1, m):
		if a[i][j] == 1:
			a[i][j] += a[i][j - 1]
ans = 0
for j in range(m):
	prev = min(a[n - 1][j], 1)
	ans += prev
	for i in range(n - 2, -1, -1):
		temp = min(a[i][j], prev + 1)
		prev = temp
		ans += temp
print(ans)


(n, m) = map(int, input().split())
W = []
for _ in range(n):
	W.append(input())
M = [[0 for x in range(m)] for y in range(n)]
for (it, i) in enumerate(W):
	t = 0
	for (jt, j) in enumerate(i):
		t = t + 1 if j == '1' else 0
		M[it][jt] = t
ans = 0
for i in range(m - 1, -1, -1):
	t = 0
	for j in range(n - 1, -1, -1):
		t = min(t + 1, M[j][i]) if W[j][i] == '1' else 0
		ans += min(M[j][i], t)
print(ans)


(n, m) = [int(i) for i in input().split()]
arr = []
for i in range(n):
	arr.append([int(i) for i in input()])
temp = [[0 for i in range(m)] for i in range(n)]
for i in range(n):
	for j in range(m):
		if i == 0 or j == 0:
			temp[i][j] = arr[i][j]
		elif arr[i][j] == 0:
			temp[i][j] = 0
		else:
			temp[i][j] = 1 + min(temp[i - 1][j - 1], temp[i - 1][j])
print(sum([sum(temp[i]) for i in range(n)]))


from sys import stdin
(rows, columns) = map(int, stdin.readline().split())
matrix = []
for i in range(rows):
	matrix.append(list(map(int, list(stdin.readline().strip()))))
for j in range(1, columns):
	for i in range(rows - 2, -1, -1):
		if matrix[i][j]:
			matrix[i][j] = min(matrix[i + 1][j] + 1, matrix[i][j - 1] + 1)
possible_sub_matrix = 0
for i in range(rows):
	for j in range(columns):
		if matrix[i][j] != 0:
			possible_sub_matrix += matrix[i][j]
print(possible_sub_matrix)


(rows, columns) = map(int, input().split())
matrix = []
for i in range(rows):
	matrix.append(list(map(int, list(input().strip()))))
for j in range(columns):
	one_count = 0
	for i in range(rows - 1, -1, -1):
		if matrix[i][j] != 0:
			one_count += 1
			matrix[i][j] = one_count
		else:
			one_count = 0
for i in range(rows):
	matrix[i][0] = min(matrix[i][0], 1)
for i in range(rows):
	for j in range(1, columns):
		if matrix[i][j] != 0:
			matrix[i][j] = min(matrix[i][j], matrix[i][j - 1] + 1)
possible_sub_matrix = 0
for i in range(rows):
	for j in range(columns):
		if matrix[i][j] != 0:
			possible_sub_matrix += matrix[i][j]
print(possible_sub_matrix)


(n, m) = map(int, input().split())
mat = []
[mat.append(input()) for _ in range(n)]
sMats = [0] * m
ans = 0
for i in range(n - 1, -1, -1):
	tmp = 0
	for j in range(m):
		if mat[i][j] == '1':
			sMats[j] += 1
		else:
			sMats[j] = 0
		tmp = min(tmp + 1, sMats[j])
		ans += tmp
print(ans)


(N, M) = map(int, input().split())
arr = []
for i in range(1, N + 1):
	arr.append(list(input()))
col = [0] * M
ans = 0
for i in range(N - 1, -1, -1):
	prev = 0
	for j in range(M):
		if arr[i][j] == '1':
			col[j] += 1
		else:
			col[j] = 0
		prev = min(prev + 1, col[j])
		ans += prev
print(ans)


(n, m) = map(int, input().split())
dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
a = [None] * n
for i in range(n):
	a[i] = input()
varts = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(n):
	for j in range(m):
		if a[i][j] == '1':
			varts[i + 1][j + 1] = 1
			varts[i + 1][j + 1] += varts[i][j + 1]
s = 0
for i in range(n):
	for j in range(m):
		if a[i][j] == '1':
			dp[i + 1][j + 1] = 1
			dp[i + 1][j + 1] += min(dp[i][j], varts[i + 1][j + 1] - 1)
			s += dp[i + 1][j + 1]
print(s)


(n, m) = map(int, input().strip().split())
matrix = []
f = []
for i in range(0, n):
	a = list(input().strip())
	matrix.append(list(map(int, a)))
	x = [0] * m
	f.append(x)
for i in range(0, n):
	for j in range(0, m):
		if i == 0 or j == 0:
			f[i][j] = matrix[i][j]
		elif matrix[i][j] == 1:
			f[i][j] = min(f[i - 1][j], f[i - 1][j - 1]) + 1
ans = 0
for i in range(n):
	ans += sum(f[i])
print(ans)


def get_params(inp, split=True):
	if split:
		inp = inp.split()
	inp = [int(i) for i in inp]
	return inp
(n, m) = get_params(str(input()))
array = [get_params(str(input()), False) for i in range(n)]
dp = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
	for j in range(m):
		if i == 0 or j == 0:
			dp[i][j] = 1 if array[i][j] == 1 else 0
			continue
		if array[i][j] == 0:
			continue
		dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + 1
print(sum([sum(i) for i in dp]))


(n, m) = map(int, input().split())
ls = [input() for _ in range(n)]
Count = [0] * m
res = 0
for i in range(n - 1, -1, -1):
	for j in range(m):
		Count[j] = Count[j] + 1 if ls[i][j] == '1' else 0
	last = 0
	for j in range(m):
		last = min(last + 1, Count[j])
		res += last
print(res)


import sys
line = input().split()
n = int(line[0])
m = int(line[1])
a = [list() for i in range(n)]
t = [[0 for j in range(m)] for i in range(n)]
l = [[-1 for j in range(m)] for i in range(n)]
for i in range(n):
	line = list(input())
	a[i] = [int(x) for x in line]
for j in range(m):
	for i in range(n):
		if a[i][j] == 0:
			l[i][j] = i
		else:
			l[i][j] = l[i - 1][j] if i > 0 else -1
for j in range(m):
	t[0][j] = a[0][j]
for i in range(1, n):
	t[i][0] = a[i][0]
for i in range(1, n):
	for j in range(1, m):
		if a[i][j] == 1:
			t[i][j] = min(t[i - 1][j - 1] + 1, i - l[i][j])
		else:
			t[i][j] = 0
s = 0
for x in t:
	s += sum(x)
sys.stdout.write(str(s) + '\n')


(n, m) = map(int, input().strip().split())
matrix = []
for i in range(n):
	matrix.append(input().strip())
ref_matrix = [[0 for i in range(m)] for j in range(n)]
for i in range(m):
	ref_matrix[-1][i] = int(matrix[-1][i])
for i in range(n - 2, -1, -1):
	for j in range(m):
		if matrix[i][j] == '1':
			ref_matrix[i][j] = 1 + ref_matrix[i + 1][j]
		else:
			ref_matrix[i][j] = 0
ans_matrix = [[0 for i in range(m)] for j in range(n)]
ans = 0
for i in range(n):
	ans_matrix[i][0] = int(matrix[i][0])
	ans += ans_matrix[i][0]
for i in range(n):
	for j in range(1, m):
		ans_matrix[i][j] = min(ans_matrix[i][j - 1] + 1, ref_matrix[i][j])
		ans += ans_matrix[i][j]
print(ans)


(n, m) = map(int, input().strip().split())
matrix = [list(map(int, input().strip())) for i in range(n)]
g = [[0 for j in range(m)] for i in range(n)]
f = [[0 for j in range(m)] for i in range(n)]
total = 0
for j in range(m):
	ones = 0
	for i in range(n - 1, -1, -1):
		if matrix[i][j]:
			ones += 1
		else:
			ones = 0
		g[i][j] = ones
for i in range(n):
	for j in range(m):
		if j == 0:
			if matrix[i][j]:
				f[i][j] = 1
		else:
			f[i][j] = min(f[i][j - 1] + 1, g[i][j])
		total += f[i][j]
print(total)