Buggy python submission (verdict: Time Limit Exceeded):
def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()


Fixed submission:
def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    r, c, k = map(int, input().split())
    d = dict()
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[(t1-1, t2-1)] = t3
    dp = [[0]*4 for _ in [0]*c]
    if (0, 0) in d:
        dp[0][1] = d[(0, 0)]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        if (x, y+1) in d:
                            dp[y+1][z+1] = max(dp[y+1]
                                               [z+1], dp[y][z]+d[(x, y+1)])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                if (x+1, y) in d:
                    dp2[y][1] = max(dp2[y][1],
                                    max(dp[y])+d[(x+1, y)])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()


Fixed submission:
def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()

Buggy python submission (verdict: Runtime Error):
def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r-1):
        d2 = d[x]
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c-1):
            d3 = d2[y+1]
            for z in range(3):
                dp[y+1][z+1] = max(dp[y+1][z+1], dp[y][z]+d3)
            for z in range(4):
                dp[y+1][z] = max(dp[y+1][z], dp[y][z])
        d2 = d[x+1]
        for y in range(c):
            dp2[y][1] = max(dp2[y][1], max(dp[y])+d2[y])
            dp2[y][0] = max(dp2[y][0], max(dp[y]))
        dp = dp2
    for y in range(c-1):
        d3 = d2[y+1]
        for z in range(3):
            dp[y+1][z+1] = max(dp[y+1][z+1], dp[y][z]+d3)
        for z in range(4):
            dp[y+1][z] = max(dp[y+1][z], dp[y][z])
    print(max(dp[c-1]))


main()


Fixed submission:
def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()

Buggy python submission (verdict: Runtime Error):
def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r-1):
        d2 = d[x]
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c-1):
            d3 = d2[y+1]
            dp3 = dp[y+1]
            dp4 = dp[y]
            for z in range(3):
                dp3[z+1] = max(dp3[z+1], dp4[z]+d3)
            for z in range(4):
                dp3[z] = max(dp3[z], dp4[z])
        d2 = d[x+1]
        for y in range(c):
            dp3 = dp2[y]
            M = max(dp[y])
            dp3[1] = max(dp3[1], M+d2[y])
            dp3[0] = max(dp3[0], M)
        dp = dp2
    for y in range(c-1):
        d3 = d2[y+1]
        dp2 = dp[y+1]
        dp3 = dp[y]
        for z in range(3):
            dp2[z+1] = max(dp2[z+1], dp3[z]+d3)
        for z in range(4):
            dp2[z] = max(dp2[z], dp3[z])
    print(max(dp[c-1]))


main()


Fixed submission:
def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[[0]*4 for _ in [0]*c] for _ in [0]*r]
    dp[0][0][1] = d[0][0]
    for x in range(r):
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[x][y+1][z+1] = max(dp[x][y+1]
                                              [z+1], dp[x][y][z]+d[x][y+1])
                    dp[x][y+1][z] = max(dp[x][y+1][z], dp[x][y][z])
            if x != r-1:
                dp[x+1][y][1] = max(dp[x+1][y][1], max(dp[x][y])+d[x+1][y])
                dp[x+1][y][0] = max(dp[x+1][y][0], max(dp[x][y]))
    print(max(dp[r-1][c-1]))


main()


Fixed submission:
def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    r, c, k = map(int, input().split())
    d = dict()
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[(t1-1, t2-1)] = t3
    dp = [[[0]*4 for _ in [0]*c] for _ in [0]*r]
    if (0, 0) in d:
        dp[0][0][1] = d[(0, 0)]
    for x in range(r):
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        if (x, y+1) in d:
                            dp[x][y+1][z+1] = max(dp[x][y+1]
                                                  [z+1], dp[x][y][z]+d[(x, y+1)])
                    dp[x][y+1][z] = max(dp[x][y+1][z], dp[x][y][z])
            if x != r-1:
                if (x+1, y) in d:
                    dp[x+1][y][1] = max(dp[x+1][y][1],
                                        max(dp[x][y])+d[(x+1, y)])
                dp[x+1][y][0] = max(dp[x+1][y][0], max(dp[x][y]))
    print(max(dp[r-1][c-1]))


main()

Fixed submission:
def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    r, c, k = map(int, input().split())
    d = dict()
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[(t1-1, t2-1)] = t3
    dp = [[[0]*4 for _ in [0]*c] for _ in [0]*r]
    if (0, 0) in d:
        dp[0][0][1] = d[(0, 0)]
    for x in range(r):
        for y in range(c):
            for z in range(4):
                if x != r-1:
                    if (x+1, y) in d:
                        dp[x+1][y][1] = max(dp[x+1][y][1],
                                            dp[x][y][z]+d[(x+1, y)])
                    dp[x+1][y][0] = max(dp[x+1][y][0], dp[x][y][z])
                if y != c-1:
                    if z != 3:
                        if (x, y+1) in d:
                            dp[x][y+1][z+1] = max(dp[x][y+1]
                                                  [z+1], dp[x][y][z]+d[(x, y+1)])
                    dp[x][y+1][z] = max(dp[x][y+1][z], dp[x][y][z])
    print(max(dp[r-1][c-1]))


main()


Fixed submission:
def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()