Submission #68805451

---

Source Code Expand

n, m, k = map(int,input().split())
s = [input() for i in range(n)]

# 上に何マス続いているか? 
h = [[0] * m for i in range(n)]
for j in range(m):
	for i in range(n):
		if s[i][j] == '#':
			h[i][j] = 0
		else:
			if i-1 < 0:
				h[i][j] = 1
			else:
				h[i][j] = h[i-1][j] + 1

# 縦 k 以下, 横 l 以下の長方形であって面積が K 以下のものの個数
r = [[0] * (m+1) for i in range(n+1)]
for i in range(1, n+1):
	for j in range(1, m+1):
		if i * j <= k:
			r[i][j] += 1

for i in range(n+1):
	for j in range(m):
		r[i][j+1] += r[i][j]

for i in range(n):
	for j in range(m+1):
		r[i+1][j] += r[i][j]

# r[i][j] の寄与を imos 法で求める
c = [[0] * (m+2) for i in range(n+1)]
for i in range(n):
	st = [-1] # ブロックの高さ
	ind = [m] # ブロックが始まる y 座標
	for j in range(m-1,-1,-1):
		while st[-1] >= h[i][j]:
			x = st.pop()
			c[x][ind[-1]-j] += 1 # 紫のブロック
			ind.pop()
			c[x][ind[-1]-j] -= 1 # 橙のブロック
		c[h[i][j]][0] -= 1 # 紫のブロック
		c[h[i][j]][ind[-1]-j] += 1 # 橙のブロック
		st.append(h[i][j])
		ind.append(j)
	while st[-1] >= 0:
		x = st.pop()
		c[x][ind[-1]+1] += 1 # 紫のブロック
		ind.pop()
		c[x][ind[-1]+1] -= 1 # 橙のブロック

for i in range(n+1):
	for j in range(m+1):
		c[i][j+1] += c[i][j]

ans = 0
for i in range(n+1):
	for j in range(m+1):
		ans += c[i][j] * r[i][j]

print(ans)

Submission Info

Judge Result