Submission #76467188

---

Source Code Expand

h, w, k = map(int, input().split())

grid = []
for _ in range(h):
    grid.append(input())

s = [[0] * (w + 1) for _ in range(h + 1)]
for i in range(h):
    for j in range(w):
        val = int(grid[i][j])
        s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + val

ans = 0
max_sum = h * w
count = [0] * (max_sum + 1)

for r1 in range(1, h + 1):
    for r2 in range(r1, h + 1):
        count[0] = 1 
        
        for c in range(1, w + 1):
            current_sum = s[r2][c] - s[r1 - 1][c]
            
            if current_sum >= k:
                ans += count[current_sum - k]
            
            count[current_sum] += 1
        
        count[0] = 0
        for c in range(1, w + 1):
            current_sum = s[r2][c] - s[r1 - 1][c]
            count[current_sum] = 0

print(ans)

Submission Info

Judge Result