Solve in Python:
Zonal Computing Olympiad 2013, 10 Nov 2012

Little Red Riding Hood is carrying a basket with berries through the forest to her grandmother's house.  The forest is arranged in the form of a square N × N grid of cells.  The top left corner cell, where Little Red Riding Hood starts her journey, is numbered (1,1) and the bottom right corner cell, where her grandmother lives, is numbered (N,N).  In each step, she can move either one position right or one position down.

The forest is full of dangerous wolves and she is looking for a safe path to reach her destination.  Little Red Riding Hood's fairy godmother has placed some special anti-wolf magical charms in some of the cells in the grid.  Each charm has a strength.  If the charm in cell (i,j) has strength k then its zone of influence is all the cells within k steps of (i,j); that is, all cells (i',j') such that |i - i'| + |j - j'| ≤ k.  A cell within the zone of influence of a charm is safe from wolves.  A safe path from (1,1) to (N,N) is one in which every cell along the path is safe.

Little Red Riding Hood is carrying a basket with berries. In each cell, she drops some berries while pushing her way through the thick forest.  However, sometimes she is also able to pick up fresh berries.  Each cell is labelled with an integer that indicates the net change in the number of berries in her basket on passing through the cell; that is, the number of berries she picks up in that cell minus the number of berries she drops.  You can assume that there are enough berries in her basket to start with so that the basket never becomes empty.

Little Red Riding Hood knows the positions and strengths of all the magic charms and is looking for a safe path along which the number of berries she has in the basket when she reaches her grandmother's house is maximized.

As an example consider the following grid:

3  3  2  4  3 
2  1 -1 -2  2  
-1  2  4  3 -3  
-2  2  3  2  1  
3 -1  2 -1  2  

Suppose there are 3 magic charms, at position (1,2) with strength 2, at position (4,5)...
def main():
	from sys import stdin, stdout
	rl = stdin.readline

	n, m = (int(x) for x in rl().split())
	grid = [[int(x) for x in rl().split()] for _ in range(n)]
	charms = [[int(x) for x in rl().split()] for _ in range(m)]

	n_inf = -9999
	dp = [[n_inf] * n for _ in range(n)]

	for c in charms:
		c[0] -= 1
		c[1] -= 1

		x = max(0, c[0] - c[2])
		while x < n and x <= c[0] + c[2]:
			off = abs(x - c[0])
			y = max(0, c[1] - c[2] + off)
			while y < n and y <= c[1] + c[2] - off:
				dp[x][y] = grid[x][y]
				y += 1
			x += 1

	for x in range(1, n):
		if dp[x - 1][0] == n_inf:
			for x1 in range(x, n):
				dp[x1][0] = n_inf
			break
		dp[x][0] += dp[x - 1][0]

	for y in range(1, n):
		if dp[0][y - 1] == n_inf:
			for y1 in range(y, n):
				dp[0][y1] = n_inf
			break
		dp[0][y] += dp[0][y - 1]

	for x in range(1, n):
		for y in range(1, n):
			m = max(dp[x - 1][y], dp[x][y - 1])
			dp[x][y] = m + dp[x][y] if m != n_inf else n_inf

	if dp[-1][-1] != n_inf:
		stdout.write('YES\n')
		stdout.write(str(dp[-1][-1]))
	else:
		stdout.write('NO')


main()