Guest User

Untitled

a guest
Nov 21st, 2017
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.06 KB | None | 0 0
  1. n, m = map(int, raw_input().split())
  2. grid = []
  3. for i in range(n):
  4. grid.append(map(int, raw_input().split()))
  5.  
  6. dp = []
  7. for i in range(n):
  8. dp.append([0]*m)
  9.  
  10. for i in range(n):
  11. msl = [max(grid[i][0], 0)]*m
  12. for j in range(1, m):
  13. msl[j] = max(msl[j-1]+grid[i][j], 0)
  14.  
  15. msr = [max(grid[i][-1], 0)]*m
  16. for j in range(1, m):
  17. msr[m-1-j] = max(msr[m-j]+grid[i][m-1-j], 0)
  18.  
  19. mslit = [grid[i][0]]*m
  20. if i>0: mslit[0] += dp[i-1][0]
  21. dp[i][0] = mslit[0]+msr[1]
  22. for j in range(1, m):
  23. top = 0 if i==0 else dp[i-1][j]
  24. mslit[j] = max(mslit[j-1], top+msl[j-1])+grid[i][j]
  25.  
  26. val = 0 if j+2>m else msr[j+1]
  27. dp[i][j] = mslit[j] + val
  28.  
  29. msrit = [grid[i][m-1]]*m
  30. if i>0: msrit[m-1] += dp[i-1][m-1]
  31. dp[i][m-1] = max(dp[i][m-1], msrit[m-1]+msl[m-2])
  32. for j in range(1, m):
  33. top = 0 if i==0 else dp[i-1][m-1-j]
  34. msrit[m-1-j] = max(msrit[m-j], top+msr[m-j])+grid[i][m-1-j]
  35.  
  36. val = 0 if j+2>m else msl[m-1-j-1]
  37. dp[i][m-1-j] = max(dp[i][m-1-j], msrit[m-1-j] + val)
  38.  
  39. print max(dp[-1])
Add Comment
Please, Sign In to add comment