Submission #925952

#	Time	Username	Problem	Language	Result	Execution time	Memory
925952		Karoot	Jump (BOI06_jump)	Pypy 3	100 / 100	73 ms	24732 KiB

jump

import math

n = int(input())
mem = []
arr = []


for i in range(n):
	mem.append([])
	arr.append([])
	li = input().split(" ")
	for j in range(n):
		mem[i].append(-1)
		arr[i].append(int(li[j]))
	
	

def dp(x, y):
	if x == n-1 and y == n-1:
		return 1 
	if mem[x][y] != -1:
		return mem[x][y]
	val = arr[x][y]
	if val == 0:
		mem[x][y] = 0
		return 0
	ret = 0
	if x+val < n:
		ret += dp(x+val, y)
	if y+val < n:
		ret += dp(x, y+val)
	mem[x][y] = ret
	return ret


print(dp(0, 0))

• Subtask 1: 100 / 100