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: Runtime Error

Solution code:
#EDPC L
import sys
sys.setrecursionlimit(10**5)


def main():
    N=int(input())
    a=list(map(int,input().split()))
    #dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）
    dp=[[-1]*N for _ in range(N)]
    print(rec(0,N-1))

def rec(l,r):
    if dp[l][r]!=-1:
        return dp[l][r]
    
    if l==r:
        dp[l][r]=a[l]
        return dp[l][r]
    
    dp[l][r]=max(a[l]-rec(l+1,r),a[r]-rec(l,r-1))

    return dp[l][r]
main()

Submission status: Runtime Error

Solution code:
#EDPC L
import sys
sts.setrecursionlimit(10**8)

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

#dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）

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


#for i in range(N-1):
#    for j in range()
def rec(l,r):
    if dp[l][r]!=-1:
        return dp[l][r]
    
    if l==r:
        dp[l][r]=a[l]
        return dp[l][r]
    
    dp[l][r]=max(a[l]-rec(l+1,r),a[r]-rec(l,r-1))

    return dp[l][r]


print(rec(0,N-1))

Submission status: Runtime Error

Solution code:
#EDPC L
import sys
sts.setrecursionlimit(10**5+100)

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

#dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）

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


#for i in range(N-1):
#    for j in range()
def rec(l,r):
    if dp[l][r]!=-1:
        return dp[l][r]
    
    if l==r:
        dp[l][r]=a[l]
        return dp[l][r]
    
    dp[l][r]=max(a[l]-rec(l+1,r),a[r]-rec(l,r-1))

    return dp[l][r]


print(rec(0,N-1))

Submission status: Runtime Error

Solution code:
#EDPC L

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

#dp[l][r]:=区間[l,r]が残っている時の(直後の人の最終的な得点-そうじゃない方の最終的な得点）

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


#for i in range(N-1):
#    for j in range()
def rec(l,r):
    if dp[l][r]!=-1:
        return dp[l][r]
    
    if l==r:
        dp[l][r]=a[l]
        return dp[l][r]
    
    dp[l][r]=max(a[l]-rec(l+1,r),a[r]-rec(l,r-1))

    return dp[l][r]


print(rec(0,N-1))

Submission status: Runtime Error

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

dp = [[None] * len(a) for _ in a]


def solve(i, j):
    if dp[i][j]:
        return dp[i][j]

    if i == j:
        return a[i]

    dp[i][j] = max(a[j] - solve(i, j-1), a[i] - solve(i+1, j))
    return dp[i][j]


print(solve(0, len(a) - 1))

Submission status: Runtime Error

Solution code:
from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

#import random
#N = 400
#A = [random.randint(1, 10**9) for _ in range(N)]
INF = 1.0e+100

@lru_cache(maxsize=None)
def f(l, r, xy):
  if l > r:
    return xy
  
  n = r - l
  if (N - n) % 2 == 0:
    s = -1
  else:
    s = 1
    
  lv = f(l+1, r, xy + s*A[l])
  rv = f(l, r-1, xy + s*A[r])
  
  if s*lv > s*rv:
    return lv
  else:
    return rv
    
   
print(f(0, N-1, 0))

Submission status: Runtime Error

Solution code:
import math,sys
from collections import Counter, defaultdict, deque
from sys import stdin, stdout
input = stdin.readline
li = lambda:list(map(int,input().split()))

ans=[[-1 for i in range(3000)] for i in range(3000)]

def maxdiff(a,start,end,f):
    if(start>end):
        return 0
    if(ans[start][end]!=-1):
        return(ans[start][end])
    if(f):
        ans[start][end]=max(maxdiff(a,start+1,end,0)+a[start],maxdiff(a,start,end-1,0)+a[end])
    else:
        ans[start][end]=min(maxdiff(a,start+1,end,1)-a[start],maxdiff(a,start,end-1,1)-a[end])
    return ans[start][end]
    
    
    

def case():
    n=int(input())
    a=li()
    f=1
    k=maxdiff(a,0,len(a)-1,f)
    print(k)

for _ in range(1):
    case()

Submission status: Runtime Error

Solution code:
import math,sys
from collections import Counter, defaultdict, deque
from sys import stdin, stdout
input = stdin.readline
li = lambda:list(map(int,input().split()))

def maxdiff(a,ans,start,end,f):
    if(start>end):
        return 0
    if(ans[start][end]!=-1):
        return(ans[start][end])
    if(f):
        ans[start][end]=max(maxdiff(a,ans,start+1,end,0)+a[start],maxdiff(a,ans,start,end-1,0)+a[end])
    else:
        ans[start][end]=min(maxdiff(a,ans,start+1,end,1)-a[start],maxdiff(a,ans,start,end-1,1)-a[end])
    return ans[start][end]
    
    
    

def case():
    n=int(input())
    a=li()
    ans=[[-1 for i in range(len(a))] for i in range(len(a))]
    f=-1
    c=0
    d=0
    k=maxdiff(a,ans,0,len(a)-1,f)
    print(k)

for _ in range(1):
    case()

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 10)

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

memo = [[0] * N for _ in range(N)]
r = N % 2


def f(i, j):
    n = j - i + 1
    if i == j:
        if n % 2 == r:
            s = a[i]
            memo[i][j] = s
            return s
        else:
            s = -a[i]
            memo[i][j] = s
            return s
    if n % 2 == r:
        s = max(f(i, j - 1) + a[j], f(i + 1, j) + a[i])
    else:
        s = min(f(i, j - 1) - a[j], f(i + 1, j) - a[i])
    memo[i][j] = s
    return s


f(0, N - 1)
print(memo[0][N - 1])

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline

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

memo = [[0] * N for _ in range(N)]
r = N % 2


def f(i, j):
    n = j - i + 1
    if i == j:
        if n % 2 == r:
            s = a[i]
            memo[i][j] = s
            return s
        else:
            s = -a[i]
            memo[i][j] = s
            return s
    if n % 2 == r:
        s = max(f(i, j - 1) + a[j], f(i + 1, j) + a[i])
    else:
        s = min(f(i, j - 1) - a[j], f(i + 1, j) - a[i])
    memo[i][j] = s
    return s


f(0, N - 1)
print(memo[0][N - 1])

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
dp = [[None for m in range(N)] for j in range(N)]
def fn(i, j, c):
	if i > j:
		return 0
	if dp[i][j] != None:
		return dp[i][j]
	if c == 0:
		dp[i][j] = max(A[i] + fn(i+1, j, 1), A[j] + fn(i, j-1, 1))
	else:
		dp[i][j] = min(-A[i] + fn(i+1, j, 0), -A[j] + fn(i, j-1, 0))
	return dp[i][j]
for i in range(N):
	fn(0, N-1, 0)
print(fn(0, N-1, 0))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
dp = [[None for m in range(N)] for j in range(N)]
def fn(i, j, c):
	if i > j:
		return 0
	if dp[i][j] != None:
		return dp[i][j]
	if c == 0:
		dp[i][j] = max(A[i] + fn(i+1, j, 1), A[j] + fn(i, j-1, 1))
	else:
		dp[i][j] = min(-A[i] + fn(i+1, j, 0), -A[j] + fn(i, j-1, 0))
	return dp[i][j]
print(fn(0, N-1, 0))

Submission status: Runtime Error

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

INF = 10**18

dp0 = [[INF] * N for _ in range(N)]
dp1 = [[INF] * N for _ in range(N)]

def calc(i, j, t):
    if t == 0:
        if dp0[i][j] == INF:
            if i == j:
                dp0[i][j] = a[i]
            else:
                dp0[i][j] = max(calc(i+1, j, 1) + a[i], calc(i, j-1, 1) + a[j])
        return dp0[i][j]
    else:
        if dp1[i][j] == INF:
            if i == j:
                dp1[i][j] = -a[i]
            else:
                dp1[i][j] = min(calc(i+1, j, 0) - a[i], calc(i, j-1, 0) - a[j])
        return dp1[i][j]

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

Submission status: Runtime Error

Solution code:
from functools import lru_cache

@lru_cache()
def f(l, r):
    if l==r: return a[r]
    return max(a[l]-f(l+1, r),  a[r]-f(l, r-1))

N = int(input())
*a, = map(int, input().split())
print(f(0, N-1))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
d = [None]*(n+1)**2
def judge(l,r):
  if l >= r:
    return a[l]
  v = l + r*(n+1)
  if d[v] is not None: return d[v]
  d[v] = max(a[l] - judge(l+1,r), a[r] - judge(l,r-1))
  return d[v]

print(judge(0,n-1))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
d = [None]*(n+1)**2
def judge(l,r):
  if l >= r:
    return a[l]
  v = l + r*(n+1)
  if d[v] is not None: return d[v]
  d[v] = min(a[l] - judge(l+1,r), a[r] - judge(l,r-1))
  return d[v]

print(judge(0,n-1))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
d = [None]*3001**2
def judge(l,r):
  if l >= r:
    return a[l]
  v = l + r*3001
  if d[v] is not None: return d[v]
  res1 = a[l] - judge(l+1,r)
  res2 = a[r] - judge(l,r-1)
  if res1 < res2: res1, res2 = res2, res1
  d[v] = res1
  return res1

print(judge(0,n-1))

Submission status: Runtime Error

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

#check who plays last
currentTaro = ((N%2)==1)

#initilise best-scores list for last player with one element
bestScores = [(el if currentTaro else -el) for el in a]
bestScores = [(el,el) for el in bestScores]

for i in range(1,2):
	#alternate player
	currentTaro = not currentTaro
    
	newBestScores=[]
	for j in range(N):
		#get best score if number removed from left
		bestLeftScore=None
		if j>=i:
			leftScoresAfterRemoval=(bestScores[j-1][0],bestScores[j-i][1])
			bestLeftScore= min(leftScoresAfterRemoval)+a[j] if currentTaro else max(leftScoresAfterRemoval)-a[j]

		#get best score if number removed from right
		bestRightScore=None
		if j<=N-1-i:
			rightScoresAfterRemoval=(bestScores[j+1][1],bestScores[j+i][0])
			bestRightScore= min(rightScoresAfterRemoval)+a[j] if currentTaro else max(rightScoresAfterRemoval)-a[j]

		#add to newBestScores
		newBestScores.append((bestLeftScore,bestRightScore))

	bestScores=newBestScores

#return best score 
result = max(bestScores[0][1],bestScores[-1][0])
print(result)

Submission status: Runtime Error

Solution code:
N = input()
a = input.split()

if N<1:
	return None
#check who plays last
currentTaro = ((N%2)==1)

#initilise best-scores list for last player with one element
bestScores = [(el if currentTaro else -el) for el in a]
bestScores = [(el,el) for el in bestScores]

for i in range(1,N):
	#alternate player
    currentTaro = not currentTaro
    
    newBestScores=[]
    for j in range(N):
      #get best score if number removed from left
      bestLeftScore=None
      if j>=i:
          leftScoresAfterRemoval=(bestScores[j-1][0],bestScores[j-i][1])
          bestLeftScore= min(leftScoresAfterRemoval)+a[j] if currentTaro else max(leftScoresAfterRemoval)-a[j]

      #get best score if number removed from right
      bestRightScore=None
      if j<=N-1-i:
          rightScoresAfterRemoval=(bestScores[j+1][1],bestScores[j+i][0])
          bestRightScore= min(rightScoresAfterRemoval)+a[j] if currentTaro else max(rightScoresAfterRemoval)-a[j]

      #add to newBestScores
      newBestScores.append((bestLeftScore,bestRightScore))

	bestScores=newBestScores

#return best score 
result = max(bestScores[0][1],bestScores[-1][0])
print(result)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline

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


dp = [[float("inf") for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
	dp[i][i] = 0

def rec(i, j):
	if(dp[i][j] != float("inf")) : return dp[i][j];

	turn = N -(j-i)

	if (turn % 2 == 0):
		d = max(rec(i+1, j) + lst_a[i], rec(i, j-1) + lst_a[j-1])
	else :
		d = min(-lst_a[i] + rec(i + 1, j), -lst_a[j - 1] +rec(i, j - 1))

	dp[i][j] = d
	return dp[i][j]

rec(0,N)

print(dp[0][N])

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
s=[[0 for i in range(n)]for j in range(n)]
b=[[0 for i in range(n)]for j in range(n)]
def f(x,y):
    if b[x][y]:
        return s[x][y]
    else:
        b[x][y]=1
        if x==y:
            s[x][y]=a[x]
            return s[x][y]
        else:
            s[x][y]=max(a[x]-f(x+1,y),a[y]-f(x,y-1))
            return s[x][y]
print(f(0,n-1))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
s=[[0 for i in range(n)]for j in range(n)]
def f(x,y):
    if s[x][y]:
        return s[x][y]
    else:
        if x==y:
            s[x][y]=a[x]
            return s[x][y]
        else:
            s[x][y]=max(a[x]-f(x+1,y),a[y]-f(x,y-1))
            return s[x][y]
print(f(0,n-1))

Submission status: Runtime Error

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

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

    def rec(l, r, N, A):
        if dp[l][r] >= 0:
            return dp[l][r]
        if (N-(r-l))%2 == 1:
            dp[l][r] = min(rec(l+1,r,N,A), rec(l, r-1,N,A))
        else:
            dp[l][r] = max(rec(l+1, r,N,A)+A[l], rec(l,r-1,N,A)+A[r-1])
#        print(l, r,dp[l][r], dp)
        return dp[l][r]
    print(2*rec(0, N, N, A) - sum(A))
#    print(dp)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())

dp = [[[None]*2]*n]*n
ar = [int(x) for x in input().split()]
def recur(i, j, p):
    p=p%2
    if j<i or min(i,j)<0 or max(i,j)>n:
        return 0
    if dp[i][j][p]:
        return dp[i][j][p]
    t = max(ar[i], ar[j])
    if p == 0:
        dp[i][j][p] = max(ar[i] + recur(i+1,j,p+1),  ar[j] + recur(i,j-1,p+1))
    else:
        dp[i][j][p] = min(recur(i+1,j,p+1) - ar[i], recur(i,j-1,p+1)-ar[j])
    return dp[i][j][p]

print(int(recur(0,n-1,0)))

# print(dp)

Submission status: Runtime Error

Solution code:
n = int(input())

dp = [[[None]*2]*n]*n
ar = [int(x) for x in input().split()]
def recur(i, j, p):
    p=p%2
    if j<i or min(i,j)<0 or max(i,j)>=n:
        return 0
    if dp[i][j][p]:
        return dp[i][j][p]
    t = max(ar[i], ar[j])
    if p == 0:
        dp[i][j][p] = max(ar[i] + recur(i+1,j,p+1),  ar[j] + recur(i,j-1,p+1))
    else:
        dp[i][j][p] = min(recur(i+1,j,p+1) - ar[i], recur(i,j-1,p+1)-ar[j])
    return dp[i][j][p]

print(int(recur(0,n-1,0)))

# print(dp)

Submission status: Runtime Error

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

dpmax = [[0]*N for _ in range(N)]
dpmin = [[0]*N for _ in range(N)]
        
def f(i, j, t):
    if i > j or i < 0 or i >= N or j < 0 or j >= N:
        return 0
    
    if i == j:
        if t == 0:
            dpmin[i][j] = -A[i]
            return -A[i]
        if t == 1:
            dpmax[i][j] = A[i]
            return A[i]
        
    if t == 0 and dpmin[i][j] > 0:
        return dpmin[i][j]
    elif t == 1 and dpmax[i][j] > 0:
        return dpmax[i][j]
    
    if t == 0:
        dpmin[i][j] = min(-A[i]+f(i+1, j, 1), -A[j]+f(i, j-1, 1))
        return dpmin[i][j]
    else:
        dpmax[i][j] = max(A[i]+f(i+1, j, 0), A[j]+f(i, j-1, 0))
        return dpmax[i][j]

ans = f(0, N-1, 1)
print(ans)

Submission status: Runtime Error

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

dpmax = [[0]*N for _ in range(N)]
dpmin = [[0]*N for _ in range(N)]
        
def f(i, j, t):
    if i > j or i < 0 or j >= N:
        return 0
    
    if i == j:
        if t == 0:
            dpmin[i][j] = -A[i]
            return -A[i]
        if t == 1:
            dpmax[i][j] = A[i]
            return A[i]
        
    if t == 0 and dpmin[i][j] > 0:
        return dpmin[i][j]
    elif t == 1 and dpmax[i][j] > 0:
        return dpmax[i][j]
    
    if t == 0:
        dpmin[i][j] = min(-A[i]+f(i+1, j, 1), -A[j]+f(i, j-1, 1))
        return dpmin[i][j]
    else:
        dpmax[i][j] = max(A[i]+f(i+1, j, 0), A[j]+f(i, j-1, 0))
        return dpmax[i][j]

ans = f(0, N-1, 1)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    dp=[[None]*(n+1) for _ in range(n+1)]

    def dfs(l,r)->NoneType:
        if(dp[l][r] is not None): return
        if(l==r):
            dp[l][r]=0
            return

        # 1個先の値を確定させておく
        dfs(l+1,r)
        dfs(l,r-1)
        turn=(n-(r-l))%2
        if(turn==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])

    dfs(0,n)
    print(dp[0][n])
resolve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)
from collections import deque
N = int(input())
a = deque(map(int, input().split()))

def main():
    x, y = dfs(a, 0, 0, True)
    return x - y
def dfs(a, x, y, xturn):
    if len(a) == 1:
        if xturn:
            x += a[0]
        else:
            y += a[0]
        return x, y
    elif len(a) == 2:
        if xturn:
           x += max(a)
           y += min(a)
        else:
            y += max(a)
            x += min(a)
        return x, y
    c1a = a.copy()
    c2a = a.copy()
    c1 = c1a.pop()
    c2 = c2a.popleft()
    if xturn:
        x1, y1 = dfs(c1a, x + c1, y, not xturn)
        x2, y2 = dfs(c2a, x + c2, y, not xturn)
        if x1 > x2:
            return x1, y1
        return x2, y2
    else:
        x1, y1 = dfs(c1a, x, y + c1, not xturn)
        x2, y2 = dfs(c2a, x, y + c2, not xturn)
        if y1 > y2:
            return x1, y1
        return x2, y2
print(main())

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
a = deque(map(int, input().split()))

def main():
    x, y = dfs(a, 0, 0, True)
    return x - y
def dfs(a, x, y, xturn):
    if len(a) == 1:
        if xturn:
            x += a[0]
        else:
            y += a[0]
        return x, y
    elif len(a) == 2:
        if xturn:
           x += max(a)
           y += min(a)
        else:
            y += max(a)
            x += min(a)
        return x, y
    c1a = a.copy()
    c2a = a.copy()
    c1 = c1a.pop()
    c2 = c2a.popleft()
    if xturn:
        x1, y1 = dfs(c1a, x + c1, y, not xturn)
        x2, y2 = dfs(c2a, x + c2, y, not xturn)
        if x1 > x2:
            return x1, y1
        return x2, y2
    else:
        x1, y1 = dfs(c1a, x, y + c1, not xturn)
        x2, y2 = dfs(c2a, x, y + c2, not xturn)
        if y1 > y2:
            return x1, y1
        return x2, y2
print(main())

Submission status: Runtime Error

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

dp = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    p = (N - l) % 2
    if p == 0:
        for l in range(N + 1 - i):
            r = l + i
            t0 = dp[l + 1][r] + a[l]
            t1 = dp[l][r - 1] + a[r - 1]
            if t0 > t1:
                dp[l][r] = t0
            else:
                dp[l][r] = t1
    else:
        for l in range(N + 1 - i):
            r = l + i
            t0 = dp[l + 1][r] - a[l]
            t1 = dp[l][r - 1] - a[r - 1]
            if t0 < t1:
                dp[l][r] = t0
            else:
                dp[l][r] = t1
print(dp[0][N])

Submission status: Runtime Error

Solution code:
import subprocess as sp
import sys
code = r"""
n=int(input())
a=[int(j) for j in input().split()]
dp=[[0]*(n+1) for i in range(n+1)]

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

"""
with open("A.py","w") as f:
	f.write(code)
sp.Popen(['pypy','-std=pypy','-O2',"A.py"]).communicate()
sp.Popen(['./a.out'],stdin=sys.stdin,stdout=sys.stdout).communicate()

Submission status: Runtime Error

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
#dp=[[0]*(n+1) for i in range(n+1)]
dp=[[0]*(n+1) for i in range(n)]

for w in range(1,n+1):
#for w in range(1,3,1):
#    print(dp[1])
    for l in range(n-w+1):
        print("#",l)
        r=l+w
        dpl=-dp[l+1][r]+a[l]
        dpr=-dp[l][r-1]+a[r-1]
        dp[l][r]=max(dpl,dpr)
#print()
#for i in dp:
#    print(i)
print(dp[0][n])

Submission status: Runtime Error

Solution code:
def func(l, r, taro_turn):
    # [l,r]
    # return taro - jiro
    if l > r:
        return 0

    if taro_turn is None:
        # jiro_turn
        return min(func(l, r - 1, True) - a[r], func(l + 1, r, True) - a[l])
    else:
        # taro_turn
        return max(func(l, r - 1, None) + a[r], func(l + 1, r, None) + a[l])


n = int(input())
a = tuple(int(x) for x in input().split())

print(func(0, n - 1, True))

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=None)
def seach(left, right, turn):
    if right - left == 1:
        if turn == 0:
            return A[left]
        else:
            return -A[left]

    if turn == 0:  # 最大化
        return max(seach(left + 1, right, 1) + A[left], seach(left, right - 1, 1) + A[right - 1])
    else:
        return min(seach(left + 1, right, 0) - A[left], seach(left, right - 1, 0) - A[right - 1])

ans = seach(0, N, 0)
print(ans)

Submission status: Runtime Error

Solution code:
def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    n = len(a)
    dp = [[None for x in range(n)] for y in range(n)]
    recursive_call(dp, a, 0, n - 1)
    return dp[0][n - 1]


def recursive_call(dp, a, l, r):
    n = len(dp)
    if dp[l][r] is not None:
        return dp[l][r]
    if l == r:
        dp[l][r] = a[l]
        return dp[l][r]
    dp[l][r] = max(a[l] - recursive_call(dp, a, l + 1, r), a[r] - recursive_call(dp, a, l, r - 1))
    return dp[l][r]


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

turn = 0
scores = (0, 0)

for i in len(A):
  if A[0] >= A[-1]:
    scores[turn] += A[0]
    A = A[1:]
  else:
    scores[turn] += A[-1]
    A = A[:-1]
  scores = scores ^ 1
print(scores[0] - scores[1])

Submission status: Runtime Error

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

	for i in range(n - 2, -1, -1):
    	for j in range(i + 1, n):
        	dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
	print(dp[0][n - 1])
main()

Submission status: Runtime Error

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

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

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

Submission status: Runtime Error

Solution code:
def main():
	n = int(input())
	a = list(map(int, input().split()))
	dp = [[0] * n for _ in range(n)]
	for i in range(n):
    	dp[i][i] = a[i]
	for i in range(n - 2, -1, -1):
    	for j in range(i + 1, n):
        	dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    print(dp[0][n-1])
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def calc():
	n = int(input())
	a = list(map(int, input().split()))
	dp = [[0] * n for _ in range(n)]
	for i in range(n):
    	dp[i][i] = a[i]
	for i in range(n - 2, -1, -1):
    	for j in range(i + 1, n):
        	dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    return dp[0][n-1]
ans = calc()
print(ans)

Submission status: Runtime Error

Solution code:


def calc():
	n = int(input())
	a = list(map(int, input().split()))
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]

    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    return dp[0][n-1]

print(calc())

Submission status: Runtime Error

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

def calc():
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]

    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

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

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
def calc():
	dp=[]
	for i in range(n):
		dp.append([0]*n)
	for i in range(n):
   		dp[i][i] = a[i]
	for i in range(n - 2, -1, -1):
    	for j in range(i + 1, n):
        	dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
    return dp
print(calc()[0][n - 1])

Submission status: Runtime Error

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

dp=[]
for i in range(n):
	dp.append(0)
for i in range(n):
    dp[i][i] = a[i]

for i in range(n - 2, -1, -1):
    for j in range(i + 1, n):
        dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])

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

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
using namespace std;

// DP テーブル
long long dp[3100][3100];

int main() {
    // 入力受け取り
    int N; cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    // 初期条件
    for (int i = 0; i < N; ++i) dp[i][i] = 0;

    // DP
    for (int len = 1; len <= N; ++len) {
        for (int i = 0; i + len <= N; ++i) {
            int 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]);
        }
    }

    // 答え
    cout << dp[0][N] << endl;
}

Submission status: Runtime Error

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

# [i, j)
def rec(i, j):
    if i == j:
        return (0, 0)

    sum = 0
    for k in range(i, j):
        sum += A[k]

    # take head
    head = A[i]
    score0 = head + rec(i+1, j)[1]

    # take last
    last = A[j-1]
    score1 = last + rec(i, j-1)[1]

    score = max(score0, score1)
    return (score, sum-score)

X, Y = rec(0,N)
print(X-Y)

Submission status: Runtime Error

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

cum = [0]*(N+1)
for i in range(N):
    cum[i] = cum[i-1]+a[i]

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

def cal(i,j):
    if dp[i][j] == -1:
        dp[i][j] = cum[j]-cum[i-1]-min(cal(i+1,j),cal(i,j-1))
    return dp[i][j]

print(2*cal(0,N-1)-cum[N-1])

Submission status: Runtime Error

Solution code:
def calcdp(p, i, j):
    # すでにテーブルが埋まっていればその値を返す
    if dp[p][i][j] is not None:
        return dp[p][i][j]
    
    # リストに１個しか数字がなければ、それを取るしかない
    if i == j - 1:
        if p:
            dp[p][i][j] = A[i]
        else:
            dp[p][i][j] = -A[i]
        return dp[p][i][j]
    else:
        # 先手の場合
        if p:
            dp[p][i][j] = max(calcdp(not p, i + 1, j) + A[i], calcdp(not p, i, j-1) + A[j-1])
        #　後手の場合
        else:
            dp[p][i][j] = min(calcdp(not p, i + 1, j) - A[i], calcdp(not p, i, j-1) - A[j-1])
        return dp[p][i][j]

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

dp = [[[None] * (N+1) for _ in range(N)] for __ in range(2)]

print(calcdp(True, 0, N))

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
dp=[None]*n
for i in range(n):
    dp[i]=[None]*n
    dp[i][i]=l[i]
def find(i,j):
    if(i>j):
        return 0
    if(dp[i][j]!=None):
        return dp[i][j]
    dp[i][j]=max(l[i]-find(i+1,j),l[j]-find(i,j-1))
    return dp[i][j]
print(find(0,n-1))

Submission status: Runtime Error

Solution code:

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define eb          emplace_back
#define c(P)        cout<<P<<"\n"
#define pii         pair<ll,ll>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define F           first
#define S           second
#define mp(x,y)     make_pair(x,y) 
#define mem(a,val)  memset(a,val,sizeof(a))
#define fr(i,a,n)   for(ll i=a;i<n;i++)
#define frr(i,a,n)  for(ll i=n-1;i>=a;i--)


const ll N   =  3005;
const ll mod = 1e9 + 7;

using namespace std;

ll dp[N][N]; // for   taro
void solve()
{
   ll n;
   cin>>n;
   ll a[n];
   for (int i = 0; i < n; ++i)
   {
     /* code */
    cin>>a[i];
   }
   // dp[n-1][0] - ans when all are over
  for (int i = 0; i <n ; ++i)
  {
    for(ll j = i;j>=0;j--)
    {
      if(i==j)
      dp[i][j] = a[i];
      else dp[i][j] = max(a[i] - dp[i-1][j],a[j] - dp[i][j+1]);

    }
  }
  cout<<dp[n-1][0]<<"\n";
}

signed main(){
  
      ios_base::sync_with_stdio(false);   
      cin.tie(NULL);
      ll T=1;
      //cin>>T;
      while(T--)
      {
      solve();
      }
      return 0;
    }

Submission status: Runtime Error

Solution code:
def xy(a, x, y, i):
    if i == n - 2:
        if i % 2:
            return x - y - max(a) + min(a)
        else:
            return x - y + max(a) - min(a)
    t=tuple(a+[x,y])
    if t in memo:
        return memo[t]
    if i % 2:
        L = xy(a[1:], x, y + a[0], i + 1)
        R = xy(a[:-1], x, y + a[-1], i + 1)
        re = min(L, R)
        memo[t] = re
        return re
    else:
        L = xy(a[1:], x + a[0], y, i + 1)
        R = xy(a[:-1], x + a[-1], y, i + 1)
        re = max(L, R)
        memo[t] = re
        return re


memo = {}
n = int(input())
a = list(map(int, input().split()))
if n == 1:
    print(a[0])
    exit()
print(xy(a, 0, 0, 0))