You are not logged in. Please login at www.codechef.com to post your questions!

×

# TLE for Sums in a Triangle with Memoization

 0 Hi, I tried this code for Sums in a Triangle: import sys T = int(sys.stdin.readline()) memo = {} def solve(i, j, m, limit): # print "i:"+str(i) if i==limit: return 0 if (i, j) in memo: # print "Reused:", i, j return memo[(i, j)] memo[(i, j)] = m[i][j] + max(solve(i+1, j, m, limit), solve(i+1, j+1, m, limit)) # print memo return memo[(i, j)] for i in xrange(T): n = int(sys.stdin.readline()) m = [] memo = {} for j in xrange(n): m.append([int(_) for _ in (sys.stdin.readline()).split()]) print solve(0, 0, m, n) I save places I've visited in the matrix in a dict, so overlapping cases are taken care of, yet CC gives me a TLE. Can someone tell me what I can do to make this work? asked 18 Apr '14, 17:28 3★svineet 36●2●4●10 accept rate: 0% @admin help, this thread is so old! (18 May '14, 23:42) svineet3★
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×528
×349
×107
×53

question asked: 18 Apr '14, 17:28

question was seen: 2,120 times

last updated: 18 May '14, 23:42