Problem p03171 (python)

Fixed submission:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(N: int, a: "List[int]"):
    N1 = N + 1
    dpmin = [-1] * N1 ** 2
    dpmax = [-1] * N1 ** 2
    for i in range(N1):
        dpmin[0 * N1 + i] = dpmax[0 * N1 + i] = 0
    for i in range(N):
        dpmin[1 * N1 + i] = -a[i]
        dpmax[1 * N1 + i] = a[i]
    for k in range(2, N1):
        for i in range(N - k + 1):
            dpmin[k * N1 + i] = min(
                -a[i] + dpmax[(k - 1) * N1 + i + 1],
                -a[i + k - 1] + dpmax[(k - 1) * N1 + i],
            )
            r = -1
            dpmax[k * N1 + i] = max(
                a[i] + dpmin[(k - 1) * N1 + i + 1],
                a[i + k - 1] + dpmin[(k - 1) * N1 + i],
            )
    return dpmax[N * N1]


def main():
    N = int(readline())  # type: int
    a = [int(x) for x in readline().split()]  # type: "List[int]"
    print(solve(N, a))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]"):
    dpmin = [[None] * (N + 1) for _ in range(N + 1)]
    dpmax = [[None] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        dpmin[i][i] = dpmax[i][i] = 0
        dpmin[i][i + 1] = -a[i]
        dpmax[i][i + 1] = a[i]
    dpmin[N][N] = dpmax[N][N] = 0

    def minimize(a, begin, end):
        x = dpmin[begin][end]
        if x is not None:
            return x
        pt1 = -a[begin] + maximize(a, begin + 1, end)
        pt2 = -a[end - 1] + maximize(a, begin, end - 1)
        r = min(pt1, pt2)
        dpmin[begin][end] = r
        return r

    def maximize(a, begin, end):
        x = dpmax[begin][end]
        if x is not None:
            return x
        pt1 = a[begin] + minimize(a, begin + 1, end)
        pt2 = a[end - 1] + minimize(a, begin, end - 1)
        r = max(pt1, pt2)
        dpmax[begin][end] = r
        return r

    return maximize(a, 0, N)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, a))


if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]"):
    dpmin = [[None] * (N + 1) for _ in range(N + 1)]
    dpmax = [[None] * (N + 1) for _ in range(N + 1)]
    for i in range(N):
        dpmin[i][i] = dpmax[i][i] = 0
        dpmin[i][i + 1] = -a[i]
        dpmax[i][i + 1] = a[i]

    def minimize(a, begin, end):
        x = dpmin[begin][end]
        if x is not None:
            return x
        pt1 = -a[begin] + maximize(a, begin + 1, end)
        pt2 = -a[end - 1] + maximize(a, begin, end - 1)
        r = min(pt1, pt2)
        dpmin[begin][end] = r
        return r

    def maximize(a, begin, end):
        x = dpmax[begin][end]
        if x is not None:
            return x
        pt1 = a[begin] + minimize(a, begin + 1, end)
        pt2 = a[end - 1] + minimize(a, begin, end - 1)
        r = max(pt1, pt2)
        dpmax[begin][end] = r
        return r

    return maximize(a, 0, N)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, a))


if __name__ == "__main__":
    main()