Submission #43957490

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
H,W,N = map(int, input().split())
hole_set = set()
for _ in range(N):
    a,b = map(int, input().split())
    hole_set.add((a,b))
dp = [[0 for _ in range(W+2)] for _ in range(H+2)]  # dp[i][j]:(i,j)を右下とする穴のない正方形の個数
ans = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if (i,j) not in hole_set:
            dp[i][j] = min([dp[i-1][j-1],dp[i][j-1],dp[i-1][j]]) + 1
            ans += dp[i][j]
print(ans)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

H,W,N = map(int, input().split())

hole_set = set()

for _ in range(N):
    a,b = map(int, input().split())
    hole_set.add((a,b))

dp = [[0 for _ in range(W+2)] for _ in range(H+2)]  # dp[i][j]:(i,j)を右下とする穴のない正方形の個数
ans = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if (i,j) not in hole_set:
            dp[i][j] = min([dp[i-1][j-1],dp[i][j-1],dp[i-1][j]]) + 1
            ans += dp[i][j]

print(ans)

Submission Info

Judge Result