n = int(input())
a = []
dp = []
for _ in range(n):
a.append([int(x) for x in input().split()])
dp.append([0] * n)
dp[0][0] = 1
for i in range(n):
for j in range(n):
if i < n - 1 and i + a[i][j] < n: dp[i + a[i][j]][j] += dp[i][j]
if j < n - 1 and j + a[i][j] < n: dp[i][j + a[i][j]] += dp[i][j]
print(dp[n-1][n-1])
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
18220 KB |
Output is correct |
2 |
Correct |
33 ms |
18148 KB |
Output is correct |
3 |
Correct |
33 ms |
18228 KB |
Output is correct |
4 |
Correct |
33 ms |
18208 KB |
Output is correct |
5 |
Correct |
35 ms |
18172 KB |
Output is correct |
6 |
Correct |
34 ms |
18200 KB |
Output is correct |
7 |
Correct |
35 ms |
18196 KB |
Output is correct |
8 |
Correct |
37 ms |
18200 KB |
Output is correct |
9 |
Correct |
42 ms |
19276 KB |
Output is correct |
10 |
Correct |
37 ms |
18136 KB |
Output is correct |
11 |
Correct |
37 ms |
18244 KB |
Output is correct |
12 |
Correct |
36 ms |
18272 KB |
Output is correct |
13 |
Correct |
42 ms |
19136 KB |
Output is correct |
14 |
Correct |
43 ms |
19164 KB |
Output is correct |
15 |
Correct |
49 ms |
19716 KB |
Output is correct |
16 |
Correct |
55 ms |
20296 KB |
Output is correct |
17 |
Correct |
59 ms |
20716 KB |
Output is correct |
18 |
Correct |
57 ms |
20300 KB |
Output is correct |
19 |
Correct |
66 ms |
20912 KB |
Output is correct |
20 |
Correct |
64 ms |
20764 KB |
Output is correct |