Problem:


Score : 100 points

Problem Statement

Taro and Jiro will play the following game against each other.

Initially, they are given a sequence a = (a_1, a_2, \ldots, a_N).
Until a becomes empty, the two players perform the following operation alternately, starting from Taro:

Remove the element at the beginning or the end of a. The player earns x points, where x is the removed element.

Let X and Y be Taro's and Jiro's total score at the end of the game, respectively.
Taro tries to maximize X - Y, while Jiro tries to minimize X - Y.

Assuming that the two players play optimally, find the resulting value of X - Y.

Constraints

All values in input are integers.

1 \leq N \leq 3000

1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

Print the resulting value of X - Y, assuming that the two players play optimally.

Sample Input 1

4
10 80 90 30

Sample Output 1

10

The game proceeds as follows when the two players play optimally (the element being removed is written bold):

Taro: (10, 80, 90, 30) → (10, 80, 90)

Jiro: (10, 80, 90) → (10, 80)

Taro: (10, 80) → (10)

Jiro: (10) → ()

Here, X = 30 + 80 = 110 and Y = 90 + 10 = 100.

Sample Input 2

3
10 100 10

Sample Output 2

-80

The game proceeds, for example, as follows when the two players play optimally:

Taro: (10, 100, 10) → (100, 10)

Jiro: (100, 10) → (10)

Taro: (10) → ()

Here, X = 10 + 10 = 20 and Y = 100.

Sample Input 3

1
10

Sample Output 3

10

Sample Input 4

10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1

Sample Output 4

4999999995

The answer may not fit into a 32-bit integer type.

Sample Input 5

6
4 2 9 7 1 5

Sample Output 5

2

The game proceeds, for example, as follows when the two players play optimally:

Taro: (4, 2, 9, 7, 1, 5) → (4, 2, 9, 7, 1)

Jiro: (4, 2, 9, 7, 1) → (2, 9, 7, 1)

Taro: (2, 9, 7, 1) → (2, 9, 7)

Jiro: (2, 9, 7) → (2, 9)

Taro: (2, 9) → (2)

Jiro: (2) → ()

Here, X = 5 + 1 + 9 = 15 and Y = 4 + 7 + 2 = 13.



Sample input:
4
10 80 90 30


Sample output:
10

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[[0 for i in range(n+1)] for j in range(n+1)]

for len in range(1,n+1):
  for i in range(n+1):
    if i+len>n:
      break
    j=i+len
    if (n - len) % 2 == 0:
      dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
      #print(len,dp)
    else:
      dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])
      #print(len,dp)
print(dp[0][n])

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n = ni()
    a = na()

    dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    for d in range(1, n + 1):
        for l in range(n - d + 1):
            r = l + d

            # second
            if (n - d) % 2:
                dp[l][r] = min(dp[l + 1][r] - a[l], dp[l][r - 1] - a[r - 1])

            # first
            else:
                dp[l][r] = max(dp[l + 1][r] + a[l], dp[l][r - 1] + a[r - 1])

    print(dp[0][n])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))

# from random import randint
# n = 3000
# A = [randint(1, 10**9) for i in range(n)]

sys.setrecursionlimit(10**7)

mm = 10**14

D = [mm] * (n**2)
f = 1 if n%2==1 else -1
for i in range(n):
    D[i*n + i] = f * A[i]

# print(D)

def point(l, r):
    if D[l*n + r] != mm:
        return D[l*n + r]
    else:
        if (r-l+1)%2 == n%2:
            D[l*n + r] = max(point(l, r-1) + A[r], point(l+1, r) + A[l])
        else:
            D[l*n + r] = min(point(l, r-1) - A[r], point(l+1, r) - A[l])
    return D[l*n + r]

print(point(0, n-1))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))

    su = [0 for _ in range(n + 1)]    
    for i in range(n):
        su[i + 1] = su[i] + a[i]

    INF = 1e18
    dp = [[-INF for _ in range(n + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][i] = 0

    for length in range(1, n + 1):
        i = 0
        while i + length <= n:
            j = i + length
            dp[i][j] = max(a[i] + (su[j] - su[i + 1]) - dp[i + 1][j], a[j - 1] + (su[j - 1] - su[i]) - dp[i][j - 1])
            i += 1
    
    print(dp[0][n] - (su[n] - dp[0][n]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def resolve():
    N = int(input())
    A = list(map(int, input().split()))

    dp = [[0] * (N+1) for _ in range(N+1)]
    # 左側をとる: 区間 [i+1,j)[i+1,j) に遷移
    # 右側をとる: 区間 [i,j−1)[i,j−1) に遷移
    for L in range(1, N + 1):
        i = 0
        while i + L <= N:
            j = i + L
            # 先手番
            if (N - L) % 2 == 0:
                dp[i][j] = max(dp[i + 1][j] + A[i], dp[i][j - 1] + A[j - 1])
            # 後手番
            else:
                dp[i][j] = min(dp[i + 1][j] - A[i], dp[i][j - 1] - A[j - 1])
            i += 1

    print(dp[0][N])


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def f(a,p1,p2):
    if p1>p2:
        return 0
   
    return max(a[p1]+min(f(a,p1+2,p2),f(a,p1+1,p2-1))
                      ,a[p2]+min(f(a,p1+1,p2-1),f(a,p1,p2-2)))
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
first=f(a,0,n-1)
print(first-(s-first))

Submission status: Time Limit Exceeded

Solution code:
def f(a,n,ans1,p1,p2,flag):
    if p1>p2:
        return 0
   
    return max(a[p1]+min(f(a,n,ans1,p1+2,p2,flag+1),f(a,n,ans1,p1+1,p2-1,flag+1))
                      ,a[p2]+min(f(a,n,ans1,p1+1,p2-1,flag+1),f(a,n,ans1,p1,p2-2,flag+1)))
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
p1=0
p2=n-1
first=f(a,n,0,p1,p2,2)
print(first-(s-first))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a_list = list(map(int, input().split()))

dp = [[0]*(N+10) for _ in range(N+10)]
dp[0][0] = 0
for width in range(1, N+1):
    for l in range(1, N+1):
        r = l + width
        if r >= N+2:
            break
        if width % 2 == N % 2:
            dp[l][r] = max(dp[l][r-1]+a_list[r-2], dp[l+1][r]+a_list[l-1])
        else:
            dp[l][r] = min(dp[l][r-1]-a_list[r-2], dp[l+1][r]-a_list[l-1])

print(dp[1][N+1])

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int,readline().split()))

# dp[i][j] = 元の数列の中の連続する区間i～jに対して、最終局面に行った時のX-Yの最大値

dp = [[0] * (N + 1) for i in range(N + 1)]
  
for length in range(1, N + 1):
  for i in range(N - length + 1):
    j = i + length
    
    if (N - length) % 2 == 0: # 先手番
      dp[i][j] = max(dp[i + 1][j] + A[i], dp[i][j - 1] + A[j - 1])
      
    else: # 後手番
      dp[i][j] = min(dp[i + 1][j] - A[i], dp[i][j - 1] - A[j - 1])

print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)


@lru_cache(maxsize=None)
def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    dp = [[-1]*(N+1) for _ in range(N+1)]

    for i in range(N+1):
        dp[i][i] = 0

    for l in range(1,N+1):
        for i in range(N-l+1):
            j = i + l
            if (N-l)%2==0:
                dp[i][j] = max(dp[i+1][j]+A[i], dp[i][j-1]+A[j-1])
            else:
                dp[i][j] = min(dp[i+1][j]-A[i], dp[i][j-1]-A[j-1])

    print(dp[0][N])



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
from functools import lru_cache

@lru_cache(maxsize=None)
def f(N, *A):
    dp = [[INF] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        dp[i][i] = 0
    for l in range(1, N + 1):
        for i in range(N - l + 1):
            j = i + l
            if (N - l) % 2 == 0:
                dp[i][j] = max(dp[i + 1][j] + A[i], dp[i][j - 1] + A[j - 1])
            else:
                dp[i][j] = min(dp[i + 1][j] - A[i], dp[i][j - 1] - A[j - 1])
    print(dp[0][N])

def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    f(N,*A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    dp = [[INF]*(N+1) for _ in range(N+1)]

    for i in range(N+1):
        dp[i][i] = 0

    # 右は開区間[i,j)
    for length in range(1,N+1):
        for i in range(N-length+1):
            j = i + length
            if (N-length)%2==0:
                dp[i][j] = max(dp[i+1][j]+A[i], dp[i][j-1]+A[j-1])
            else:
                dp[i][j] = min(dp[i+1][j]-A[i], dp[i][j-1]-A[j-1])

    print(dp[0][N])



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

#from collections import defaultdict
#from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, XS):
    memo = {}

    def first(L, R):
        # debug(": L, R", L, R)
        if L == R:
            return XS[L]

        right = memo.get((L + 1, R))
        if right == None:
            right = first(L + 1, R)
        left = memo.get((L, R - 1))
        if left == None:
            left = first(L, R - 1)

        return max(
            XS[L] - right,
            XS[R] - left
        )

    return first(0, N - 1)


def main():
    # parse input
    N = int(input())
    XS = list(map(int, input().split()))
    print(solve(N, XS))


# tests
T1 = """
4
10 80 90 30
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    10
    """


T2 = """
3
10 100 10
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    -80
    """


T3 = """
1
10
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    10
    """


T4 = """
10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    4999999995
    """


T5 = """
6
4 2 9 7 1 5
"""


def test_T5():
    """
    >>> as_input(T5)
    >>> main()
    2
    """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

#from collections import defaultdict
#from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, XS):
    def first(L, R):
        # debug(": L, R", L, R)
        if L == R:
            return XS[L]
        return max(
            XS[L] - first(L + 1, R),
            XS[R] - first(L, R - 1)
        )

    return first(0, N - 1)


def main():
    # parse input
    N = int(input())
    XS = list(map(int, input().split()))
    print(solve(N, XS))


# tests
T1 = """
4
10 80 90 30
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    10
    """


T2 = """
3
10 100 10
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    -80
    """


T3 = """
1
10
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    10
    """


T4 = """
10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    4999999995
    """


T5 = """
6
4 2 9 7 1 5
"""


def test_T5():
    """
    >>> as_input(T5)
    >>> main()
    2
    """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = tuple(map(int, input().split()))

dp = [[0]*(n+1) for i in range(n+1)]

for l in range(1, n+1):
  for i in range(n-l+1):
    j = i+l
    if (n-l)&1: #second
      dp[i][j] = min(dp[i+1][j]-a[i], dp[i][j-1]-a[j-1])
  
    else: #first
      dp[i][j] = max(dp[i+1][j]+a[i], dp[i][j-1]+a[j-1])

print(dp[0][n])

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(100000) 

N = int(input())
*a, = map(int, input().split())

dp = [[-1] *  N for _ in range(N)]
for i in range(N): dp[i][i] = a[i]

def rec(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
    ans = max(a[i] - rec(i+1, j), a[j] - rec(i, j-1))
    dp[i][j] = ans
    return ans

print(rec(0, N-1))

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(100000) 

N = int(input())
*a, = map(int, input().split())

dp = [[-1] *  N for _ in range(N)]

def rec(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
    if i == j: 
        dp[i][j] = a[i]
        return a[i]
    ans = max(a[i] - rec(i+1, j), a[j] - rec(i, j-1))
    dp[i][j] = ans
    return ans

print(rec(0, N-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5000)

readline = sys.stdin.readline

N = int(readline())
A = list(map(int,readline().split()))

# dp[i][j] = 左端がi、右端がjの状態でのX - Yの最高得点
# dp[0][-1] = 0
# 奇数回目の処理では、
# dp[i][j] = max(dp[i-1][j] + A[i],dp[i][j - 1] + A[j])
# 偶数回目の処理では、
# dp[i][j] = min(dp[i - 1][j]) + A[i],dp[i][j - 1] + A[j])

from functools import lru_cache

@lru_cache(maxsize=3000)
def f(i,j):
  # 左端がi,右端がjのとき、これから取ることが出来る最大値 右端は含まない[i:j)
  if j - i == 1:
    if (N - (j - i)) % 2 == 0:
      return A[i]
    else:
      return -A[i]
  if (N - (j - i)) % 2 == 0:
    # 先手の場合
    return max(f(i + 1,j) + A[i],f(i,j - 1) + A[j - 1])
  else:
    return min(f(i + 1,j) - A[i],f(i,j - 1) - A[j - 1])
  
print(f(0,N))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5000)

readline = sys.stdin.readline

N = int(readline())
A = list(map(int,readline().split()))

# dp[i][j] = 左端がi、右端がjの状態でのX - Yの最高得点
# dp[0][-1] = 0
# 奇数回目の処理では、
# dp[i][j] = max(dp[i-1][j] + A[i],dp[i][j - 1] + A[j])
# 偶数回目の処理では、
# dp[i][j] = min(dp[i - 1][j]) + A[i],dp[i][j - 1] + A[j])

dp = [[-1] * (N + 1) for i in range(N + 1)]
def f(i,j):
  # 左端がi,右端がjのとき、これから取ることが出来る最大値 右端は含まない[i:j)
  if dp[i][j] != -1:
    return dp[i][j]
  if j - i == 1:
    if (N - (j - i)) % 2 == 0:
      return A[i]
    else:
      return -A[i]
  if (N - (j - i)) % 2 == 0:
    # 先手の場合
    dp[i][j] = max(f(i + 1,j) + A[i],f(i,j - 1) + A[j - 1])
    return dp[i][j]
  else:
    dp[i][j] = min(f(i + 1,j) - A[i],f(i,j - 1) - A[j - 1])
    return dp[i][j]
  
print(f(0,N))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5000)

readline = sys.stdin.readline

N = int(readline())
A = list(map(int,readline().split()))

# dp[i][j] = 左端がi、右端がjの状態でのX - Yの最高得点
# dp[0][-1] = 0
# 奇数回目の処理では、
# dp[i][j] = max(dp[i-1][j] + A[i],dp[i][j - 1] + A[j])
# 偶数回目の処理では、
# dp[i][j] = min(dp[i - 1][j]) + A[i],dp[i][j - 1] + A[j])

def f(i,j):
  # 左端がi,右端がjのとき、これから取ることが出来る最大値 右端は含まない[i:j)
  if j - i == 1:
    if (N - (j - i)) % 2 == 0:
      return A[i]
    else:
      return -A[i]
  if (N - (j - i)) % 2 == 0:
    # 先手の場合
    return max(f(i + 1,j) + A[i],f(i,j - 1) + A[j - 1])
  else:
    return min(f(i + 1,j) - A[i],f(i,j - 1) - A[j - 1])
  
print(f(0,N))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
dp = [0 for i in range(N)]
for i in range(N-1, -1, -1):
    dp[i] = a[i]
    prev = dp[i]
    for j in range(i+1, N):
        right = a[i] - dp[j]
        left = a[j] - prev
        if right > left:
            dp[j] = right
            prev = right
        else:
            dp[j] = left
            prev = left
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
dp = [0 for i in range(N)]
for i in range(N-1, -1, -1):
    dp[i] = a[i]
    prev = dp[i]
    for j in range(i+1, N):
        right = a[i] - dp[j]
        left = a[j] - prev
        if right > left:
            dp[j] = right
            prev = right
        else:
            dp[j] = left
            prev = left
print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
piles = [int(x) for x in input().split()]
dp = [[0] * n for _ in range(n)]
for l in range(n-1,-1,-1):
    for r in range(l, n):
        if l == r:
            dp[l][r] = piles[l]
        else:
            dp[l][r] = max(piles[l] - dp[l+1][r], piles[r] - dp[l][r-1])
print(dp[0][n-1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
a = tuple(map(int, input().split()))

#dp[i][j] := ai, ..., a(j-1)までの状態で最善を尽くしたときのX-Yの値
#dp[0][0]からdp[0][n],dp[n-1][n]まである
dp = [[0] * (n + 1) for _ in range(n)]

#j-iが残っている個数だから，n-(j-i)がとった個数なので，
#n-j+i%2=0なら次は先手番(Xが増える)(X-Yは増える)
#n-j+i%2=1なら次は後手番(Yが増える)(X-Yは減る)
#i=jならもう変化がないので0
#j-iが1,2,...と決まっていく
#差が1のときは決まる
for i in range(n):
    dp[i][i+1] = a[i] if n % 2 == 1 else -a[i]


#差が2以上の時その差をkとする
for k in range(2, n+1):
    for i in range(n-1):
        #dp[i][i+k]を決める
        #まずdp[i][i+k]が存在することが条件
        if i + k > n:
            continue
        
        #存在するなら，
        # 残っている数のqueue
        q = deque(a[i:]) if i+k == n else deque(a[i: i+k])
        # 次が先手番か後手番かで場合わけ
        #先手番の時
        if (n - k) % 2 == 0:
            #点数を最大化したい
            #右端をとった時と左端をとった時
            r = dp[i][i+k-1] + q.pop()
            l = dp[i+1][i+k] + q.popleft()
            dp[i][i+k] = max(r, l)

        #後手番の時
        else:
            r = dp[i][i+k-1] - q.pop()
            l = dp[i+1][i+k] - q.popleft()
            dp[i][i+k] = min(r, l)

print(dp[0][n])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def func():
    N = int(input())
    A = [int(i) for i in input().split()]

    dp = [[0] * (N+1) for i in range(N+1)]
    if (N - 1) % 2 == 0:
        fl = 1
    else:
        fl = -1
    for i in range(N):
        dp[i][i+1] = fl * A[i]

    for s in range(2, N+1):
        for l in range(N-s+1):
            r = l + s
            if (N - s) % 2 == 0:
                dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
                continue
            dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
                
    return dp[0][N]

print(func())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def func():
    N = int(input())
    A = [int(i) for i in input().split()]

    dp = [[0] * (N+1) for i in range(N+1)]
    if (N - 1) % 2 == 0:
        fl = 1
    else:
        fl = -1
    for i in range(N):
        dp[i][i+1] = fl * A[i]

    for s in range(2, N+1):
        for l in range(N-s+1):
            r = l + s
            if (N - s) % 2 == 0:
                dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
            else:
                dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
                
    return dp[0][N]

print(func())

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = [int(i) for i in input().split()]

dp = [[0] * (N+1) for i in range(N+1)]
if (N - 1) % 2 == 0:
    fl = 1
else:
    fl = -1
for i in range(N):
    dp[i][i+1] = fl * A[i]


def func():
    for s in range(2, N+1):
        for l in range(N-s+1):
            r = l + s
            if (N - s) % 2 == 0:
                dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
            else:
                dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
    
func()
print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
A = [int(i) for i in input().split()]

dp = [[0] * (N+1) for i in range(N+1)]

def func():
    for s in range(1, N+1):
        for l in range(N-s+1):
            r = l + s
            if (N - s) % 2 == 0:
                dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
            else:
                dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
    
func()
print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

dp = [[0] * (N+1) for i in range(N+1)]
for s in range(1, N+1):
    for l in range(N-s+1):
        r = l + s
        if (N - s) % 2 == 0:
            dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
        else:
            dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
    
print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
def solve():
    def max2(x, y): return x if x >= y else y
    def min2(x, y): return x if x <= y else y

    N = int(input())
    As = list(map(int, input().split()))

    dp = [[0]*(N) for _ in range(N)]

    if N%2 == 1:
        for i, A in enumerate(As):
            dp[i][i] = A
    else:
        for i, A in enumerate(As):
            dp[i][i] = -A

    for W in range(2, N+1):
        if (N-W)%2 == 0:
            for L in range(N-W+1):
                R = L+W-1
                dp[L][R] = max2(As[L]+dp[L+1][R], As[R]+dp[L][R-1])
        else:
            for L in range(N-W+1):
                R = L+W-1
                dp[L][R] = min2(-As[L]+dp[L+1][R], -As[R]+dp[L][R-1])

    print(dp[0][N-1])


solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
dp = [[0 for j in range(3010)] for i in range(3010)]
for len in range(1,N+1):
    for i in range(N-len+1):
        j = len + i

        if (N - len) % 2 == 0:
            dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j-1])
        else:
            dp[i][j] = min(dp[i+1][j] - a[i], dp[i][j-1] - a[j-1])

print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))

# dp[i][j] = a[i:j] を考えたときの X-Y の最大値
dp = [[0]*(N+1) for _ in range(N+1)]
for l in range(1, N+1):
    for i in range(N-l+1):
        j = i+l
        if (N-l)%2 == 0:
            dp[i][j] = max(dp[i+1][j]+a[i], dp[i][j-1]+a[j-1])
        else:
            dp[i][j] = min(dp[i+1][j]-a[i], dp[i][j-1]-a[j-1])
        
print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    dp = [[0 for _ in range(N)] for _ in range(N)]
    for length in range(1, N + 1):
        for left in range(N - length + 1):
            right = left + length - 1
            val = 0
            if left == right:
                val = A[left]
            else:
                val = max([
                    A[left] - dp[left + 1][right],
                    A[right] - dp[left][right - 1]
                ])
            dp[left][right] = val
    print(dp[0][N - 1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    dp = [[None for _ in range(N)] for _ in range(N)]

    def rec(sign, left, right):
        ret = dp[left][right]
        if ret is not None:
            return ret
        if left == right:
            val = sign * A[left]
            dp[left][right] = val
            return val
        score_left = sign * A[left] + rec(- sign, left + 1, right)
        score_right = sign * A[right] + rec(- sign, left, right - 1)
        score = max([score_left, score_right]) if sign == 1 else min([score_left, score_right])
        dp[left][right] = score
        return score

    print(rec(1, 0, N - 1))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# from random import randint 
# mod=10**9+7

def score(n,arr):
	dp=[[0]*n for _ in range(n)]

	for i in range(n):
		dp[i][i]=arr[i]

	prefix=[0]
	for i in arr:
		prefix.append(prefix[-1]+i)

	for gap in range(1,n):
		for i in range(n):
			if i+gap<n:
				dp[i][i+gap]=prefix[i+gap+1]-prefix[i]-min(dp[i+1][i+gap],dp[i][i+gap-1])

	# print(prefix)
	# print(dp)
	return 2*dp[0][n-1]-prefix[-1]



# with open ('input.txt') as f :
n=int(input())
arr=list(map(int,input().split()))
res=score(n,arr)

# res=ways(100,10**5,[randint(0,10**5) for _ in range(100)])
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate

def main():
  n = int(input())
  A = list(map(int, input().split()))
  L = [0] + list(accumulate(A))
  dp = [[0]*(n+1) for i in range(n+1)]
  for d in range(1, n+1):
    for i in range(n+1-d):
      dp[i][i+d] = max(A[i] + L[i+d] - L[i+1] - dp[i+1][i+d], A[i+d-1] + L[i+d-1] - L[i] - dp[i][i+d-1])
  ans = 2*dp[0][n] - L[n]
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
L = [0] + list(accumulate(A))
dp = [[-1]*(n+1) for i in range(n+1)]
def dfs(i, j):
  if dp[i][j] != -1:
    return dp[i][j]
  if i == j:
    dp[i][j] = 0
    return 0
  res = max(A[i] + L[j] - L[i+1] - dfs(i+1, j), A[j-1] + L[j-1] - L[i] - dfs(i, j-1))
  dp[i][j] = res
  return res
dfs(0, n)
ans = 2*dp[0][n] - L[n]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(sys.stdin.readline())
a=list(map(int,sys.stdin.readline().split()))
d=dict()
def help(a,i,j):
    if d.get(str(i)+" "+str(j),None)!=None:
        return d[str(i)+" "+str(j)]
    if j<i:
        return 0
    if i==j:
        return a[i]
    t1=a[i]-help(a,i+1,j)
    t2=a[j]-help(a,i,j-1)
    # print(i,j)
    # print(t1,t2)
    if t1>t2:
        d[str(i)+" "+str(j)]=t1 
    else:
        d[str(i)+" "+str(j)]=t2 
    return d[str(i)+" "+str(j)]
print(help(a,0,len(a)-1))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import sys
sys.setrecursionlimit(10**6)
a=list(map(int,input().split()))
d=dict()
def help(a,i,j):
    if d.get(str(i)+" "+str(j),None)!=None:
        return d[str(i)+" "+str(j)]
    if j<i:
        return 0
    if i==j:
        return a[i]
    t1=a[i]-help(a,i+1,j)
    t2=a[j]-help(a,i,j-1)
    # print(i,j)
    # print(t1,t2)
    if t1>t2:
        d[str(i)+" "+str(j)]=t1 
    else:
        d[str(i)+" "+str(j)]=t2 
    return d[str(i)+" "+str(j)]
print(help(a,0,len(a)-1))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    dp = [[0] * (n + 1) for _ in range(n+1)]

    for len in range(1, n + 1):
        for i in range(0, n - len + 1):
            j = i + len
            if (n - len) % 2 == 0:
                dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j-1])
            else:
                dp[i][j] = min(dp[i+1][j] - a[i], dp[i][j-1] - a[j-1])
    print(dp[0][n])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[[0 for _ in range(n+1)]for _ in range(n+1)]
for L in range(n-1,-1,-1):
    for R in range(L,n):
        if L==R:
            dp[L][R]=a[L]
        else:
            dp[L][R]=max(a[L]-dp[L+1][R],a[R]-dp[L][R-1])

print(dp[0][n-1])

Submission status: Time Limit Exceeded

Solution code:
# dp[i][j]=(区間[i,j]が残っているとき次の手番の得点-そうじゃない人の得点)
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
INF=-10**14
dp=[[-1]*n for i in range(n)]
def memo(i,j):
    if dp[i][j]>=0:
        return dp[i][j]
    if i==j:
        dp[i][j]=a[i]
    else:
        dp[i][j]=max(a[i]-memo(i+1,j),a[j]-memo(i,j-1))
    return dp[i][j]
print(memo(0,n-1))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
n = N % 2

DP = [[0] * (N+1) for _ in range(N+1)]

for w in range(1, N+1):
    for i in range(N):
        j = i + w
        if j > N:
            continue
        if (w+n) % 2 == 1:
            DP[i][j] = min(DP[i+1][j] - A[i], DP[i][j-1] - A[j-1])
        else:
            DP[i][j] = max(DP[i+1][j] + A[i], DP[i][j-1] + A[j-1])

print(DP[0][N])

Submission status: Time Limit Exceeded

Solution code:

def main():
    n = int(input())
    a = list(map(int, input().split()))

    dp = [[[0 for i in range(2)]for i in range(n+2)] for i in range(n+2)]
    # dp [start][end][chance] is the diffence between X and Y 
    # such for range start to end with the current chance of player
    for start in range(n, 0, -1):
        for end in range(start, n+1):
            for chance in range(2):
                temp = -1 if chance else 1
                val1 = a[start-1]*temp + dp[start+1][end][chance ^ 1]
                val2 = a[end-1]*temp + dp[start][end-1][chance ^ 1]
                dp[start][end][chance] = min(
                    val1, val2) if chance else max(val1, val2)
    print(dp[1][n][0])


if __name__ == "__main__":
    main()