Buggy python submission (verdict: Time Limit Exceeded):
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]

    for i in range(R):
        for j in range(C):
            v = max(dp[i][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[i+1][j+1][0] = max(dp[i+1][j+1][0], v)
            dp[i+1][j+1][1] = max(dp[i+1][j+1][1], dp[i+1][j][1], dp[i+1][j][0] + u,  v + u)
            dp[i+1][j+1][2] = max(dp[i+1][j+1][2], dp[i+1][j][2], dp[i+1][j][1] + u )
            dp[i+1][j+1][3] = max(dp[i+1][j+1][3], dp[i+1][j][3], dp[i+1][j][2] + u )

    return max(dp[R][C])

if __name__ == '__main__':
    print(main())


Fixed submission:
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(2)]

    for i in range(R):
        for j in range(C):
            v = max(dp[0][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[1][j+1][0] = max(dp[1][j+1][0], v)
            dp[1][j+1][1] = max(dp[1][j+1][1], dp[1][j][1], dp[1][j][0] + u,  v + u)
            dp[1][j+1][2] = max(dp[1][j+1][2], dp[1][j][2], dp[1][j][1] + u )
            dp[1][j+1][3] = max(dp[1][j+1][3], dp[1][j][3], dp[1][j][2] + u )
        dp[1], dp[0] = dp[0], dp[1]

    return max(dp[0][C])

if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    cur = [[0]*4 for _ in range(C+1)]
    prev = [[0]*4 for _ in range(C+1)]

    for i in range(R):
        cur, prev = prev, cur
        for j in range(C):
            for k in range(4): cur[j+1][k] = cur[j][k]
            v = max(prev[j+1])
            cur[j+1][0] = max(cur[j+1][0], v)
            if (i, j) in a:
                u = a[(i, j)]
                cur[j+1][1] = max(cur[j+1][1], cur[j][0] + u,  v + u)
                cur[j+1][2] = max(cur[j+1][2], cur[j][1] + u )
                cur[j+1][3] = max(cur[j+1][3], cur[j][2] + u )
        # print(cur)

    return max(cur[C])

if __name__ == '__main__':
    print(main())


Fixed submission:
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(2)]

    for i in range(R):
        for j in range(C):
            v = max(dp[0][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[1][j+1][0] = max(dp[1][j+1][0], v)
            dp[1][j+1][1] = max(dp[1][j+1][1], dp[1][j][1], dp[1][j][0] + u,  v + u)
            dp[1][j+1][2] = max(dp[1][j+1][2], dp[1][j][2], dp[1][j][1] + u )
            dp[1][j+1][3] = max(dp[1][j+1][3], dp[1][j][3], dp[1][j][2] + u )
        dp[1], dp[0] = dp[0], dp[1]

    return max(dp[0][C])

if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]

    for i in range(R):
        for j in range(C):
            dp[i+1][j+1][0] = dp[i+1][j][0]
            dp[i+1][j+1][1] = dp[i+1][j][1]
            dp[i+1][j+1][2] = dp[i+1][j][2]
            dp[i+1][j+1][3] = dp[i+1][j][3]
            v = max(dp[i][j+1])
            dp[i+1][j+1][0] = max(dp[i+1][j+1][0], v)
            if (i, j) in a:
                u = a[(i, j)]
                dp[i+1][j+1][1] = max(dp[i+1][j+1][1],  dp[i+1][j][0] + u,  v + u)
                dp[i+1][j+1][2] = max(dp[i+1][j+1][2], dp[i+1][j][1] + u )
                dp[i+1][j+1][3] = max(dp[i+1][j+1][3], dp[i+1][j][2] + u )

    return max(dp[R][C])

if __name__ == '__main__':
    print(main())

Fixed submission:
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(2)]

    for i in range(R):
        for j in range(C):
            v = max(dp[0][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[1][j+1][0] = max(dp[1][j+1][0], v)
            dp[1][j+1][1] = max(dp[1][j+1][1], dp[1][j][1], dp[1][j][0] + u,  v + u)
            dp[1][j+1][2] = max(dp[1][j+1][2], dp[1][j][2], dp[1][j][1] + u )
            dp[1][j+1][3] = max(dp[1][j+1][3], dp[1][j][3], dp[1][j][2] + u )
        dp[1], dp[0] = dp[0], dp[1]

    return max(dp[0][C])

if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]

    for i in range(R):
        for j in range(C):
            dp[i+1][j+1][0] = dp[i+1][j][0]
            dp[i+1][j+1][1] = dp[i+1][j][1]
            dp[i+1][j+1][2] = dp[i+1][j][2]
            dp[i+1][j+1][3] = dp[i+1][j][3]
            v = max(dp[i][j+1])
            dp[i+1][j+1][0] = max(dp[i+1][j+1][0], v)
            if (i, j) in a:
                u = a[(i, j)]
                dp[i+1][j+1][1] = max([dp[i+1][j+1][1],  dp[i+1][j][0] + u,  v + u])
                dp[i+1][j+1][2] = max([dp[i+1][j+1][2], dp[i+1][j][1] + u ])
                dp[i+1][j+1][3] = max([dp[i+1][j+1][3], dp[i+1][j][2] + u ])

    return max(dp[R][C])

if __name__ == '__main__':
    print(main())

Fixed submission:
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(2)]

    for i in range(R):
        for j in range(C):
            v = max(dp[0][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[1][j+1][0] = max(dp[1][j+1][0], v)
            dp[1][j+1][1] = max(dp[1][j+1][1], dp[1][j][1], dp[1][j][0] + u,  v + u)
            dp[1][j+1][2] = max(dp[1][j+1][2], dp[1][j][2], dp[1][j][1] + u )
            dp[1][j+1][3] = max(dp[1][j+1][3], dp[1][j][3], dp[1][j][2] + u )
        dp[1], dp[0] = dp[0], dp[1]

    return max(dp[0][C])

if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]

    for i in range(R):
        for j in range(C):
            for k in range(4): dp[i+1][j+1][k] = dp[i+1][j][k]
            v = max(dp[i][j+1])
            dp[i+1][j+1][0] = max(dp[i+1][j+1][0], v)
            if (i, j) in a:
                u = a[(i, j)]
                dp[i+1][j+1][1] = max([dp[i+1][j+1][1],  dp[i+1][j][0] + u,  v + u])
                dp[i+1][j+1][2] = max([dp[i+1][j+1][2], dp[i+1][j][1] + u ])
                dp[i+1][j+1][3] = max([dp[i+1][j+1][3], dp[i+1][j][2] + u ])

    return max(dp[R][C])

if __name__ == '__main__':
    print(main())


Fixed submission:
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(2)]

    for i in range(R):
        for j in range(C):
            v = max(dp[0][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[1][j+1][0] = max(dp[1][j+1][0], v)
            dp[1][j+1][1] = max(dp[1][j+1][1], dp[1][j][1], dp[1][j][0] + u,  v + u)
            dp[1][j+1][2] = max(dp[1][j+1][2], dp[1][j][2], dp[1][j][1] + u )
            dp[1][j+1][3] = max(dp[1][j+1][3], dp[1][j][3], dp[1][j][2] + u )
        dp[1], dp[0] = dp[0], dp[1]

    return max(dp[0][C])

if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]

    for i in range(R):
        for j in range(C):
            v = max(dp[i][j+1])
            for k in range(4):
                dp[i+1][j+1][k] = dp[i+1][j][k]
            dp[i+1][j+1][0] = max(dp[i+1][j+1][0], v)
            if (i, j) in a:
                dp[i+1][j+1][1] = max([dp[i+1][j+1][1],  dp[i+1][j][0] + a[(i, j)],  v + a[(i, j)]])
                dp[i+1][j+1][2] = max([dp[i+1][j+1][2], dp[i+1][j][1] + a[(i, j)] ])
                dp[i+1][j+1][3] = max([dp[i+1][j+1][3], dp[i+1][j][2] + a[(i, j)] ])

    return max(dp[R][C])


if __name__ == '__main__':
    print(main())


Fixed submission:
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(2)]

    for i in range(R):
        for j in range(C):
            v = max(dp[0][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[1][j+1][0] = max(dp[1][j+1][0], v)
            dp[1][j+1][1] = max(dp[1][j+1][1], dp[1][j][1], dp[1][j][0] + u,  v + u)
            dp[1][j+1][2] = max(dp[1][j+1][2], dp[1][j][2], dp[1][j][1] + u )
            dp[1][j+1][3] = max(dp[1][j+1][3], dp[1][j][3], dp[1][j][2] + u )
        dp[1], dp[0] = dp[0], dp[1]

    return max(dp[0][C])

if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(R+1)]

    for i in range(R):
        for j in range(C):
            v = max(dp[i][j+1])
            for k in range(4):
                dp[i+1][j+1][k] = dp[i+1][j][k]
            dp[i+1][j+1][0] = max(dp[i+1][j+1][0], v)
            if (i, j) in a:
                dp[i+1][j+1][1] = max([dp[i+1][j+1][1],  dp[i+1][j][0] + a[(i, j)],  v + a[(i, j)]])
                dp[i+1][j+1][2] = max([dp[i+1][j+1][2], dp[i+1][j][1] + a[(i, j)] ])
                dp[i+1][j+1][3] = max([dp[i+1][j+1][3], dp[i+1][j][2] + a[(i, j)] ])

    return max(dp[R][C])


if __name__ == '__main__':
    print(main())

Fixed submission:
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(2)]

    for i in range(R):
        for j in range(C):
            v = max(dp[0][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[1][j+1][0] = max(dp[1][j+1][0], v)
            dp[1][j+1][1] = max(dp[1][j+1][1], dp[1][j][1], dp[1][j][0] + u,  v + u)
            dp[1][j+1][2] = max(dp[1][j+1][2], dp[1][j][2], dp[1][j][1] + u )
            dp[1][j+1][3] = max(dp[1][j+1][3], dp[1][j][3], dp[1][j][2] + u )
        dp[1], dp[0] = dp[0], dp[1]

    return max(dp[0][C])

if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0, 0, 0, 0] for _ in range(C+1)] for _ in range(R+1)]

    for i in range(R):
        for j in range(C):
            for k in range(4):
                dp[i+1][j+1][k] = dp[i+1][j][k]
                dp[i+1][j+1][0] = max(dp[i+1][j+1][0], max(dp[i][j+1]))
            if (i, j) in a:
                dp[i+1][j+1][1] = max([dp[i+1][j+1][1],  dp[i+1][j][0] + a[(i, j)],  max(dp[i][j+1]) + a[(i, j)]])
                dp[i+1][j+1][2] = max([dp[i+1][j+1][2], dp[i+1][j][1] + a[(i, j)] ])
                dp[i+1][j+1][3] = max([dp[i+1][j+1][3], dp[i+1][j][2] + a[(i, j)] ])

    return max(dp[R][C])


if __name__ == '__main__':
    print(main())


Fixed submission:
def main():

    R, C, K = map(int, input().split())
    a = dict()
    for _ in range(K):
        r, c, v = map(int, input().split())
        a[(r-1, c-1)] = v

    dp = [[[0]*4 for _ in range(C+1)] for _ in range(2)]

    for i in range(R):
        for j in range(C):
            v = max(dp[0][j+1])
            u = 0
            if (i, j) in a: u = a[(i, j)]
            dp[1][j+1][0] = max(dp[1][j+1][0], v)
            dp[1][j+1][1] = max(dp[1][j+1][1], dp[1][j][1], dp[1][j][0] + u,  v + u)
            dp[1][j+1][2] = max(dp[1][j+1][2], dp[1][j][2], dp[1][j][1] + u )
            dp[1][j+1][3] = max(dp[1][j+1][3], dp[1][j][3], dp[1][j][2] + u )
        dp[1], dp[0] = dp[0], dp[1]

    return max(dp[0][C])

if __name__ == '__main__':
    print(main())