abc 175 E - Picking Goods (python)

３次元 dp するときに、r,c,k のうち k だけ、計算量が小さいときは、
dp = [[[0]*c for _ in range(r)] for _ in range(k)]
と書いた方が実行時間が短くなるという知見を得た。というかこう書かないと TLE するのだがなぜ？

def main():  
  import sys
  r,c,k = map(int, input().split())
  p= [[0]*c for _ in range(r)]
  for s in sys.stdin.readlines():
      x,y,z = map(int,s.split())
      p[x-1][y-1] = z

  ans = [[[0]*c for _ in range(r)] for _ in range(4)]
  if p[0][0] > 0:
    ans[1][0][0] = p[0][0]

  for R in range(r):
    for C in range(c):
      for d in range(4):
        a = ans[d][R][C]
        if R < r-1:
          ans[0][R+1][C] = max(a,ans[0][R+1][C])
          ans[1][R+1][C] = max(a+p[R+1][C],ans[1][R+1][C])
        if C < c-1:
          ans[d][R][C+1] = max(a,ans[d][R][C+1])
          if d < 3:
            ans[d+1][R][C+1] = max(a+p[R][C+1],ans[d+1][R][C+1])
            
  dp = 0
  for i in range(4):
    dp = max(ans[i][-1][-1],dp)
  print(dp)
  
if __name__ == '__main__':
    main()

※TLEするやつ↓。p の順番を変えただけ。
Submission #18495208 - AtCoder Beginner Contest 175