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:
#!/usr/bin/env python3

#import
#import math
#import numpy as np
N = int(input())
A = list(map(int, input().split()))

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

# 半開区間A[r,l)における最大スコア
def calc(r, l):
    if dp[r][l] != -1:
        return dp[r][l]

    if l - r == 1:
        return A[r]

    elif l - r == 2:
        return max(A[r], A[r + 1]) - min(A[r], A[r + 1])

    res = max(A[r] - calc(r + 1, l), A[l - 1] - calc(r, l - 1))
    dp[r][l] = res
    return res

ans = calc(0, N)

print(ans)

Submission status: Runtime Error

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 i in range(1,N+1):
    dp[i][i]=a[i-1]
for j in range(1,N+1):
    for i in reversed(range(1,N+1)):
        if i>j:
            continue
        if i==j:
            dp[i][j]=a[i-1]
        if i<j:
            dp[i][j]=max(a[i-1]-dp[i+1][j],a[j-1]-dp[i][j-1])
print(dp[1][N]

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]




l = 0
@lru_cache(None)
def dp(i, j):
    if i == j:
        return l[i]
    
    return max(l[i] - dp(i + 1, j), l[j] - dp(i, j - 1))

n = val()
l = li()
print(dp(0, n - 1))

Submission status: Runtime Error

Solution code:
dp = {}

def getAns(arr, L, H):
    # print(arr)
    if (L, H) in dp:
        return dp[(L, H)]
    if L == H:
        return arr[L]
    else:
        res =  max(
            arr[L]-getAns(arr, L+1, H), 
            arr[H]-getAns(arr, L, H-1)
            )
        
        dp[(L, H)] = res
        
        return res

n = int(input())
arr = list(map(int, input().strip().split()))
print(getAns(arr, 0, n-1))

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(int(x) for x in input().split())
memo = [[0] * n for _ in range(n)]
flag = [[False] * n for _ in range(n)]

def dfs(l, r):
    if flag[l][r]:
        return memo[l][r]
    if l == r:
        return A[l]
    flag[l][r] = True
    memo[l][r] = max(A[l] - dfs(l + 1, r), A[r] - dfs(l, r - 1))
    return memo[l][r]

print(dfs(0, n - 1))

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(int(x) for x in input().split())
memo = [[0] * n for _ in range(n)]
flag = [[False] * n for _ in range(n)]

def dfs(l, r):
    if flag[l][r]:
        return memo[l][r]
    flag[l][r] = True
    if l == r:
        return A[l]
    memo[l][r] = max(A[l] - dfs(l + 1, r), A[r] - dfs(l, r - 1))
    return memo[l][r]

print(dfs(0, n - 1))

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(int(x) for x in input().split())
memo = [[0] * n for _ in range(n)]

def dfs(l, r):
    if memo[l][r] != 0:
        return memo[l][r]
    if l == r:
        return A[l]
    return max(A[l] - dfs(l + 1, r), A[r] - dfs(l, r - 1))

print(dfs(0, n - 1))

Submission status: Runtime Error

Solution code:
n = int(input())
arr = []
temparr = input()
temparr = temparr.split()
for i in temparr:
    arr.append(int(i))

dicts = {}
def dfs(arr):
    global dicts
    temparr = []
    for i in arr:
        temparr.append(str(i))
    strs = ",".join(temparr)
    if strs in dicts:
        return dicts[strs]
    if len(arr) == 2:
        return max(arr) - min(arr)
    if len(arr) == 1:
        return arr[0]
    if len(arr) == 0 :
        return 0
    ans =  max( arr[0] - dfs(arr[1:]), arr[-1] - dfs(arr[:-1]) )
    #print(dicts)
    dicts[strs] = ans
    return ans 

ans = dfs(arr)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
n=int(input())
a=list(map(int,input().split()))
dp=[[0 for j in range(n)] for i in range(n)]
v=[[0 for j in range(n)] for i in range(n)]
def solve(l,r):
    if v[l][r]==1:
        return dp[l][r]
    v[l][r]=1
    if l==r:
        dp[l][r]=ret
        return a[l]
    ret=max(a[l]-solve(l+1,r),a[r]-solve(l,r-1))
    dp[l][r]=ret
    return ret
print(solve(0,n-1))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[[0 for j in range(n)] for i in range(n)]
v=[[0 for j in range(n)] for i in range(n)]
def solve(l,r):
    if v[l][r]==1:
        return dp[l][r]
    v[l][r]=1
    if l==r:
        return a[l]
    ret=max(a[l]-solve(l+1,r),a[r]-solve(l,r-1))
    return ret
print(solve(0,n-1))

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_l

'''
dp[i,j] ... dequeに[i,j]が残っているときに行動するプレイヤーのスコアの最大
dp[i,j] = max(a[i-1]-dp[i-1,j], a[j+1]-dp[i,j+1]) #これじゃgreedyと同じじゃん

dp[i,j] ... dequeに[i,j)が残っているときにその状態からスタートするプレイヤーが達成できるスコアの最大 (区間を伸ばしていく感じ)

初期値 dp[i,i]==0

dp[i,j]=max(a[i]-dp[i+1,j], a[j-1]-dp[i,j-1])
'''
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)


def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

N = a_int()
A = ints()


from numba import njit


@njit('(i8,i8[:])', cache=True)
def solve(N, A, dp):
    dp = np.zeros((N + 1, N + 1), dtype=np.int64)
    for i in range(N - 1, -1, -1):
        for j in range(i + 1, N + 1):
            dp[i, j] = max(A[i] - dp[i + 1, j], A[j - 1] - dp[i, j - 1])
    print(dp[0, N])
    # print(*dp, sep='\n')


solve(N, A)

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit
N=int(input())
a=np.array([int(i) for i in input().split()],dtype=np.int64)
a.dtype
dp=np.full((N,N),-1,dtype=np.int64)
dp.dtype
for i in range(N):
    dp[i][i]=a[i]

@njit('i8(i8,i8,i8[:,:],i8[:])', cache=True)
def calc(i,j,dp,a):
    if dp[i][j]!=-1:
        return dp[i][j]
    dp[i][j]=max(a[i]-calc(i+1,j,dp,a),a[j]-calc(i,j-1,dp,a))
    return dp[i][j]

calc(0,N-1,dp,a)
print(dp[0][N-1])

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit

N = int(input())
scores = np.array([int(i) for i in input().split()], dtype='int64')
dpt = np.full((N, N), -10**18, dtype='int64')

#@njit('i8(i8[:],i8[:,:],i8,i8)', cache=True)
def get_max_score(scores, dpt, i, j):
    if i == j:
        dpt[i][j] = scores[i]
        return scores[i]
    else:
        if dpt[i][j] != -10**18:
            return dpt[i][j]
        result = max(scores[i] - get_max_score(scores, dpt, i+1, j), scores[j] - get_max_score(scores, dpt, i, j-1))
        dpt[i][j] = result
        return result

print(get_max_score(scores, dpt, 0, len(scores)-1))

Submission status: Runtime Error

Solution code:
def calc(N,i,j):
  if dp[i][j]<float('inf'):
    return dp[i][j]
  if (N-(j-i+1))%2==0:
    if i==j:
      dp[i][j] = A[i]
    else:
      dp[i][j] = max(calc(N,i,j-1)+A[j],calc(N,i+1,j)+A[i])
  else:
    if i==j:
      dp[i][j] = -A[i]
    else:
      dp[i][j] = min(calc(N,i,j-1)-A[j],calc(N,i+1,j)-A[i])
  return dp[i][j]

N = int(input())
A = list(map(int, input().split()))
dp = [[float('inf')]*N for _ in range(N)]
ans = calc(N,0,N-1)
print(ans)

Submission status: Runtime Error

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

D = [None] * (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):
    # print(l,r)
    if (r-l+1)%2 == n%2:
        if D[l*n + r] == None:
            D[l*n + r] = max(point(l, r-1) + A[r], point(l+1, r) + A[l])
        return D[l*n + r]
    else:
        if D[l*n + r] == None:
            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: Runtime Error

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)
p1=0
p2=n-1
first=f(a,n,0,p1,p2,2)
print(first-(s-first))

Submission status: Runtime Error

Solution code:
def f(a,n,ans1,p1,p2,flag):
    if p1>p2:
        return ans1
    if flag&1==0:
        return max(f(a,n,ans1+a[p1],p1+1,p2,flag+1),
                   f(a,n,ans1+a[p2],p1,p2-1,flag+1))
    return min(f(a,n,ans1,p1+1,p2,flag+1),f(a,n,ans1,p1,p2-1,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: Runtime Error

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

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

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

def rec(i, j):
    if dp[i][j] != '':
        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: Runtime Error

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

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])
return dp[0][n-1]

Submission status: Runtime Error

Solution code:
def resultingValue(arr,st,en,n,dp):
    if(st>en):
        return 0
    if(dp[st][en]!="#"):
        return dp[st][en]
    moves = n-(en-st)
    if(moves%2==1):
        dp[st][en]=max(arr[st]+resultingValue(arr,st+1,en,n,dp),arr[en]+resultingValue(arr,st,en-1,n,dp))
    else:
        dp[st][en]= min(resultingValue(arr,st+1,en,n,dp)-arr[st], resultingValue(arr,st,en-1,n,dp)-arr[en])
    return dp[st][en]

n = int(input())
arr= list(map(int,input().split()))
dp=[]
for i in range(n):
    dp.append(['#']*n)
print(resultingValue(arr,0,n-1,n,dp))

Submission status: Runtime Error

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

#半開区間で考える⇒[i,j)での最適解
for w in range(1,N+1):#区間の残り数
    for l in range(N):# 左端
        r = l + w#右端
        if r > N:
            continue
        elif (N-k) % 2 == 0:#太郎
            #print(i,x)
            dp[l][x] = max(dp[l+1][x] + A[l], dp[l][r-1] + A[r-1])
        elif (N-k) % 2 == 1:#次郎
            #print(i,x)
            dp[l][x] = min(dp[l+1][x] - A[l], dp[l][r-1] - A[r-1])
            
print(dp)

Submission status: Runtime Error

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):
        #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+i][i+k] - q.popleft()
            dp[i][i+k] = min(r, l)

print(dp[0][n])

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(map(int, input().split()))
dp = [[0 for j in range(10)] for i in range(10)]
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: Runtime Error

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

Solution code:



def solve(i, j, turn, dp, arr):

    if i > j:
        return 0

    if (i, j, turn) in dp:
        return dp[(i, j, turn)]

    if turn == 1:
        dp[(i, j, turn)] = max(arr[i] + solve(i + 1, j, 0, dp, arr), arr[j] + solve(i, j - 1, 0, dp, arr))
        return dp[(i, j, turn)]

    else:
        dp[(i, j, turn)] = min(solve(i + 1, j, 1, dp, arr), solve(i, j - 1, 1, dp, arr))
        return dp[(i, j, turn)]


n = int(input())

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

dp = {}
sum_ = sum(a)
print(2 * solve(0, n - 1, 1, dp, a) - sum_)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

def f(l,beg,end):
    if beg==end:
        dp[beg][end]=l[beg]
        return l[beg]
    # if beg+1==end:
    #     return max(l[beg],l[end])
    if dp[beg][end]!=-1:
        return dp[beg][end]
    ans1=l[beg]+min(f(l,beg+2,end),f(l,beg+1,end-1))
    ans2=l[end]+min(f(l,beg,end-2),f(l,beg+1,end-1))
    dp[beg][end]=max(ans1,ans2)
    return max(ans1,ans2)

n = int(input())
l = list(map(int, input().split()))
tl = sum(l)
dp=[]
for _ in range(n):
    dp.append([-1]*n)
a = f(l,0,n-1)
b = tl-a
print(a-b)
print(dp)

Submission status: Runtime Error

Solution code:
n=int(sys.stdin.readline())
a=list(map(int,sys.stdin.readline().split()))
dp=[[0 for i in range(n)] for j in range(n)]
for i in range(n):
    dp[i][i]=a[i]
for i in range(2,n+1):
    for j in range(n-i+1):
        k=j+i-1 
        dp[j][k]=max(a[k]-dp[j][k-1],a[j]-dp[j+1][k])
print(dp[0][len(a)-1])

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout



def solve():
    n = int(input())
    A = [int(i) for i in stdin.readline().split()]
    dp = [[i,0] for i in A]
    t = [[0,0] for _ in range(len(A))]
    for i in range(1, len(A)):
        for j in range(i, len(A)):
            l = A[j-i] + dp[j][1]
            r = A[j] + dp[j-1][1]
            if l > r:
                t[j][0] = l
                t[j][1] = dp[j][0]
            else:
                t[j][0] = r
                t[j][1] = dp[j-1][0]
        dp = t.copy()
        t = [[0,0] for _ in range(len(A))]
    return dp[-1][0] - dp[-1][1]


print(solve())

Submission status: Runtime Error

Solution code:
import random

List_A = []
List_save = []

def GetInput():
    N = int(input())
    txt = input().split(" ")
    for i in range(N):
        List_A.append(int(txt[i]))
        List_save.append([])
        for j in range(N):
            List_save[i].append(-1)

def GetMax(Arr):
    if len(Arr) == 1:
        return [Arr[0], 0]
    if List_save[0][len(Arr)-2] == -1:
        List_save[0][len(Arr)-2] = Arr[len(Arr)-1] - GetMax(Arr[0:len(Arr)-1])[0]
    va1 = List_save[0][len(Arr)-2]
    if List_save[1][len(Arr)-1] == -1:
        List_save[1][len(Arr)-1] = Arr[0] - GetMax(Arr[1:len(Arr)])[0]
    va2 = List_save[1][len(Arr)-1]
    if va1 > va2:
        #print(Arr, Arr[-1])
        return [va1, -1]
    else:
        #print(Arr, Arr[0])
        return [va2, 0]

GetInput()
print(GetMax(List_A)[0])

Submission status: Runtime Error

Solution code:
import random

List_A = []
List_save = []
def CreateTest(N):
    for i in range(N):
        List_A.append(random.randrange(0,100))
        List_save.append([])
        for j in range(N):
            List_save[i].append(-1)
    #print(List_save)

def GetInput():
    N = int(input())
    txt = input().split(" ")
    for i in range(N):
        List_A.append(int(txt[i]))
        List_save.append([])
        for j in range(N):
            List_save[i].append(-1)

def GetMax(Arr):
    if len(Arr) == 1:
        return [Arr[0], 0]
    if List_save[0][len(Arr)-2] == -1:
        List_save[0][len(Arr)-2] = Arr[len(Arr)-1] - GetMax(Arr[0:len(Arr)-1])[0]
    va1 = List_save[0][len(Arr)-2]
    if List_save[1][len(Arr)-1] == -1:
        List_save[1][len(Arr)-1] = Arr[0] - GetMax(Arr[1:len(Arr)])[0]
    va2 = List_save[1][len(Arr)-1]
    if va1 > va2:
        #print(Arr, Arr[-1])
        return [va1, -1]
    else:
        #print(Arr, Arr[0])
        return [va2, 0]

GetInput()
print(GetMax(List_A)[0])

Submission status: Runtime Error

Solution code:
import random

List_A = []
List_save = []
def CreateTest(N):
    for i in range(N):
        List_A.append(random.randrange(0,100))
        List_save.append([])
        for j in range(N):
            List_save[i].append(-1)
    #print(List_save)

def GetInput():
    N = int(input())
    for i in range(N):
        List_A.append(int(input()))
        List_save.append([])
        for j in range(N):
            List_save[i].append(-1)

def GetMax(Arr):
    if len(Arr) == 1:
        return [Arr[0], 0]
    if List_save[0][len(Arr)-2] == -1:
        List_save[0][len(Arr)-2] = Arr[len(Arr)-1] - GetMax(Arr[0:len(Arr)-1])[0]
    va1 = List_save[0][len(Arr)-2]
    if List_save[1][len(Arr)-1] == -1:
        List_save[1][len(Arr)-1] = Arr[0] - GetMax(Arr[1:len(Arr)])[0]
    va2 = List_save[1][len(Arr)-1]
    if va1 > va2:
        #print(Arr, Arr[-1])
        return [va1, -1]
    else:
        #print(Arr, Arr[0])
        return [va2, 0]

GetInput()
print(GetMax(List_A)[0])

Submission status: Runtime Error

Solution code:
List_A = []
List_save = []
def GetInput():
    N = int(input())
    for i in range(N):
        List_A.append(int(input()))
        List_save.append([])
        for j in range(N):
            List_save[i].append(-1)

def GetMax(Arr):
    if len(Arr) == 1:
        return [Arr[0], 0]
    if List_save[0][len(Arr)-2] == -1:
        List_save[0][len(Arr)-2] = Arr[len(Arr)-1] - GetMax(Arr[0:len(Arr)-1])[0]
    va1 = List_save[0][len(Arr)-2]
    if List_save[1][len(Arr)-1] == -1:
        List_save[1][len(Arr)-1] = Arr[0] - GetMax(Arr[1:len(Arr)])[0]
    va2 = List_save[1][len(Arr)-1]
    if va1 > va2:
        #print(Arr, Arr[-1])
        return [va1, -1]
    else:
        #print(Arr, Arr[0])
        return [va2, 0]

GetInput()
print(GetMax(List_A))

Submission status: Runtime Error

Solution code:
import random

N = input()
List_A = []
def CreateTest(N):
    for i in range(N):
        List_A.append(input())
        List_save.append([])
        for j in range(N):
            List_save[i].append([-1, 0])
    #print(List_save)

def GetExist(Arr, s, e):
    #if List_save[s][e-1][0] == -1:
        va = GetMax(Arr[0:len(Arr)-1])
        List_save[s][e-1] = va
        return va
    #else:
    #    return List_save[s][e-1]


def GetMax(Arr):
    #print(Arr)
    if len(Arr) == 1:
        return [Arr[0], 0]
    va1 = Arr[len(Arr)-1] - GetExist(Arr, 0, len(Arr)-1)[0]
    va2 = Arr[0] - GetExist(Arr, 1, len(Arr))[0]
    if va1 > va2:
        #print(Arr, Arr[-1])
        return [va1, -1]
    else:
        #print(Arr, Arr[0])
        return [va2, 0]

CreateTest(N)
print(GetMax(List_A))

Submission status: Runtime Error

Solution code:
import random

N = input()
List_A = []
def CreateTest(N):
    for i in range(N):
        List_A.append(input())
        List_save.append([])
        for j in range(N):
            List_save[i].append([-1, 0])
    #print(List_save)

def GetExist(Arr, s, e):
    if List_save[s][e-1][0] == -1:
        va = GetMax(Arr[0:len(Arr)-1])
        List_save[s][e-1] = va
        return va
    else:
        return List_save[s][e-1]


def GetMax(Arr):
    #print(Arr)
    if len(Arr) == 1:
        return [Arr[0], 0]
    va1 = Arr[len(Arr)-1] - GetExist(Arr, 0, len(Arr)-1)[0]
    va2 = Arr[0] - GetExist(Arr, 1, len(Arr))[0]
    if va1 > va2:
        #print(Arr, Arr[-1])
        return [va1, -1]
    else:
        #print(Arr, Arr[0])
        return [va2, 0]

CreateTest(N)
print(GetMax(List_A))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000)
n = int(input())
a = list(map(int,input().split()))
dp = [[0 for _ in range(n)]*n]
flag =  [[False for _ in range(n)]*n]
def f(i,j):
  if flag[i][j]:
    return dp[i][j]
  flag[i][j] = True
  if i == j:
    dp[i][j] = a[i]
    return dp[i][j]
  else:
    dp[i][j] = max(a[i]- f(i+1,j),a[j]-f(i,j-1))
    return dp[i][j]
print(f(0,n-1))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)
n = int(input())
a = list(map(int,input().split()))
dp = [[0 for _ in range(n)]*n]
flag =  [[False for _ in range(n)]*n]
def f(i,j):
  if flag[i][j]:
    return dp[i][j]
  flag[i][j] = True
  if i == j:
    dp[i][j] = a[i]
    return dp[i][j]
  else:
    dp[i][j] = max(a[i]- f(i+1,j),a[j]-f(i,j-1))
    return dp[i][j]
print(f(0,n-1))

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
a=np.zeros((N+10))
memory=np.zeros((N+10,N+10))
kt=memory
s=0
for i in range(1,N+1):
    a[i]=int(input())
    s+=a[i]
def dp(left,right):
    if kt[left][right]!=0.0:
        return memory[left][right]
    if left>right: return 0.0
    if left==right: return a[left]
    x1=a[left]+min(dp(left+2,right),dp(left+1,right-1))
    x2=a[right]+min(dp(left+1,right-1),dp(left,right-2))
    kt[left][right]=1.0
    memory[left][right]=max(x1,x2)
    return memory[left][right]
    #return max(x1,x2)
print(int(2*dp(1,N)-s))

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
a=np.zeros((N+10))
s=0
for i in range(1,N+1):
    a[i]=int(input())
    s+=a[i]
def dp(left,right):
    if left>right: return 0.0
    if left==right: return a[left]
    x1=a[left]+min(dp(left+2,right),dp(left+1,right-1))
    x2=a[right]+min(dp(left+1,right-1),dp(left,right-2))
    return max(x1,x2)
print(int(2*dp(1,N)-s))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#!/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()

Submission status: Runtime Error

Solution code:
#!/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()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
d={}
def k(a):
      return ','.join(map(str,a))
def dp(a):
      ka=k(a)
      if ka in d:
            return [d[ka][0],d[ka][1]]
      if len(a)==1:
            d[ka]=[a[0],[]]
            return a[0],[]
      elif len(a)==2:
            d[ka]=[max(a),[min(a)]]
            return max(a),[min(a)]
      else:
            if a[0]-dp(a[1:])[0]>a[-1]-dp(a[:-1])[0]:
                  d[ka]=[a[0],a[1:]]
                  return a[0],a[1:]
            else:
                  d[ka]=[a[-1],a[:-1]]
                  return a[-1],a[:-1]
x,y=0,0
while a!=[]:
      x_,a=dp(a)
      x+=x_
      if a==[]:
            break
      y_,a=dp(a)
      y+=y_
print(x-y)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;

 
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

 
int N;
vector<long long> a;
vector< vector<long long> > dp;

//dp[l][r]:[l, r)の範囲における二人が最適な行動をした時のX-Yの値
//dp[l][r] = max(dp[l][r-1]+a[r-1], dp[l+1][r]+a[l]) (大郎)
//dp[l][r] = min(dp[l][r-1]-a[r-1], dp[l+1][r]-a[l]) (次郎)

long long rec(int l, int r) {
    if (r-l == 0) return 0; //数字が残っていない時
    else {
        if ((r-l) % 2 == N % 2) { //大郎のturn
            dp[l][r] = max(rec(l+1, r)+a[l], rec(l, r-1)+a[r-1]);
        }
        else { //次郎のturn
            dp[l][r] = min(rec(l+1, r)-a[l], rec(l, r-1)-a[r-1]);
        }
    }
    return dp[l][r];
}

int main() {
    cin >> N;
    a.resize(N);
    dp.resize(N+2, vector<long long> (N+2, 0));
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    
    long long ret = rec(0, N);
    cout << ret << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
def dp(i, j):
    if i == j:
        return A[i]
    return max(A[i]-dp(i+1, j), A[j]-dp(i, j-1))


n = int(input())
*A, = map(int, input().split())
print(dp(0, n-1))

Submission status: Runtime Error

Solution code:
from collections import deque
N = int(input())
A = list(map(int, input().split()))
d = deque(A)
X, Y = 0, 0
i = 0
while deque:
  if i % 2 == 0:
    if deque[0] >= deque[-1]:
      X += d.popleft()
    else:
      X += d.pop()
  else:
    if deque[0] >= deque[-1]:
      Y += d.popleft()
    else:
      Y += d.pop()
print(X - Y)