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: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n,k = LI()
    a = LI()
    dp = [0 for i in range(k+1)]
    f = [0 for i in range(k+1)]
    for i in range(k+1):
        if not f[i]:
            for j in a:
                if i-j >= 0:
                    dp[i] = 1-dp[i-j]
                    if dp[i] == 0:
                        break
            else:
                dp[i] = 1
    print(["First","Second"][dp[k]])
#B
def B():
    n = I()
    a = [0 for i in range(n)]
    ma = n*(n+1)//2
    s = [1 for i in range(n+1)]
    for i in range(1,n):
        s[i+1] = s[i]+n-i+1
    d = [None for i in range(ma+1)]
    d[0] = 0
    k = 1
    for i in range(1,n+1):
        for j in range(n+1-i):
            d[k+j] = i
        k += n+1-i
    k = n%2
    dp = [None for i in range(ma+1)]
    dp[0] = 0
    for i in range(n+1,ma+1):
        if (d[i]+k)%2:
            dp[i] = float("inf")
        else:
            dp[i] = -float("inf")
    if k:
        for i in range(n):
            dp[i+1] = a[n-1-i]
    else:
        for i in range(n):
            dp[i+1] = -a[n-1-i]
    for i in range(1,ma):
        r = n-1-(i-s[d[i]])
        l = r+1-d[i]
        j = i+(n-d[i])
        j2 = j+1
        if (d[i]+k)%2:
            if r < n-1:
                dp[j] = max(dp[j],a[r+1]+dp[i])
            if l > 0:
                dp[j2] = max(dp[j2],a[l-1]+dp[i])
        else:
            if r < n-1:
                dp[j] = min(dp[j],-a[r+1]+dp[i])
            if l > 0:
                dp[j2] = min(dp[j2],-a[l-1]+dp[i])
    print(dp[ma])
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n,k = LI()
    a = LI()
    dp = [0 for i in range(k+1)]
    f = [0 for i in range(k+1)]
    for i in range(k+1):
        if not f[i]:
            for j in a:
                if i-j >= 0:
                    dp[i] = 1-dp[i-j]
                    if dp[i] == 0:
                        break
            else:
                dp[i] = 1
    print(["First","Second"][dp[k]])
#B
def B():
    n = I()
    a = [0 for i in range(n)]
    ma = n*(n+1)//2
    s = [1 for i in range(n+1)]
    for i in range(1,n):
        s[i+1] = s[i]+n-i+1
    d = [None for i in range(ma+1)]
    d[0] = 0
    k = 1
    for i in range(1,n+1):
        for j in range(n+1-i):
            d[k+j] = i
        k += n+1-i
    k = n%2
    dp = [None for i in range(ma+1)]
    dp[0] = 0
    for i in range(n+1,ma+1):
        if (d[i]+k)%2:
            dp[i] = float("inf")
        else:
            dp[i] = -float("inf")
    if k:
        for i in range(n):
            dp[i+1] = a[n-1-i]
    else:
        for i in range(n):
            dp[i+1] = -a[n-1-i]
    d.append(d[-1])
    for i in range(1,ma):
        r = n-1-(i-s[d[i]])
        l = r+1-d[i]
        j = i+(n-d[i])
        j2 = j+1
        if (d[i]+k)%2:
            if r < n-1:
                dp[j] = max(dp[j],a[r+1]+dp[i])
            if l > 0:
                dp[j2] = max(dp[j2],a[l-1]+dp[i])
        else:
            if r < n-1:
                dp[j] = min(dp[j],-a[r+1]+dp[i])
            if l > 0:
                dp[j2] = min(dp[j2],-a[l-1]+dp[i])
    print(dp[ma])
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    B()

Submission status: Wrong Answer

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

DP = [[0] * n for i in range(n)]
if n % 2 == 1:
    for i in range(n):
        DP[i][i] = A[i]
else:
    for i in range(n):
        DP[i][i] = -A[i]

for i in range(1, n):
    for l in range(n-i):
        if (n - i) % 2 == 1:
            DP[l][l+i] = max(DP[l+1][l+i] + A[l], DP[l][l+i-1] + A[l+i])
        else:
            DP[l][l+i] = min(DP[l+1][l+i] - A[l], DP[l][l+i-1] - A[l+i])

score = [0] * 2
l = 0
r = n - 1

for i in range(n-2):
    if A[l] + A[r - 1] > A[r] + A[l + 1]:
        score[i%2] += A[l]
        l += 1
    else:
        score[i%2] += A[r]
        r -= 1

score[n%2] += max(A[l], A[r])
score[(n+1)%2] += min(A[l], A[r])

if n % 2 == 0:
    print(score[0] - score[1])
else:
    print(DP[0][n-1])

Submission status: Wrong Answer

Solution code:
import sys

N=input()
A=map(int, sys.stdin.readline().split())

dp=[ [ 0 for i in range(N) ]  for j in range(N) ]

for i in range(N-1,-1,-1):
	dp[i][i]=A[i]*-1

	
for i in range(N):
	for j in range(i,N-1):
		t=N-(j-i)
	#	print "i,j :::: ",i,j,t

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

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

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

print dp[0][N-1]

Submission status: Wrong Answer

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

if n == 1:
    print(A[0])
    exit()

score = [0] * 2
l = 0
r = n - 1

for i in range(n-2):
    if A[l] + A[r - 1] > A[r] + A[l + 1]:
        score[i%2] += A[l]
        l += 1
    else:
        score[i%2] += A[r]
        r -= 1

score[n%2] += max(A[l], A[r])
score[(n+1)%2] += min(A[l], A[r])

print(score[0] - score[1])

Submission status: Wrong Answer

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

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

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

for i in range(N):
    dp[i][i + 1] = a[i] if N & 1 == 1 else -a[i]

for i in range(0, N - 1):
    for j in range(2, N + 1 - i):  # j is the length of the interval
        if (N - j) & 1 == 0:
            dp[i][i + j] = max(a[i + 1] + dp[i + 1][i + j],
                               a[i + j - 1] + dp[i][i + j - 1])
        else:
            dp[i][i + j] = min(dp[i + 1][i + j] - a[i + 1],
                               dp[i][i + j - 1] - a[i + j - 1])

print(dp[0][N])

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_l
n=int(input())

a=[0]+list(map(int,input().split()))+[0]

i=1
j=n
if n==1: print(n, " 0")

res=[0, 0]
turn=1
while (i<=j):
    turn=(turn+1)%2
    if (a[i]-a[i+1])>a[j]-a[j-1]:
        res[turn]=res[turn]+a[i]
        a[i]=0
        i=i+1        
    else:
        res[turn]=res[turn]+a[j]
        a[j]=0
        j=j-1
print(res[0]-res[1])

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/dp/tasks/dp_l
n=int(input())

a=[0]+list(map(int,input().split()))+[0]

i=1
j=n
if n==1: print(n, " 0")

res=[0, 0]
turn=1
while (i<=j):
    turn=(turn+1)%2
    if (a[i]-a[i+1])>a[j]-a[j-1]:
        res[turn]=res[turn]+a[i]
        a[i]=0
        i=i+1        
    else:
        res[turn]=res[turn]+a[j]
        a[j]=0
        j=j-1
print(res[0], res[1])

Submission status: Wrong Answer

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

dp = [[[-10 ** 9 if k == 0 else 10 ** 9 for i in range(N)] for j in range(N)] for k in range(2)]

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

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

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

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
q = deque()
A = list(map(int, input().split()))
for i in range(N):
    q.append(A[i])
pm = 1
sum = 0
while len(q) != 0:
    if q[0] >= q[len(q) - 1]:
        sum += pm * q.popleft()
    else:
        sum += pm * q.pop()
    pm *= -1
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def main():
    N = int(input())
    A = list(map(int, sys.stdin.readline().split()))
    INF = float('inf')
    dp = [[-INF]*N for _ in range(N)]


    def score(l, r):
        if dp[l][r] > -INF:
            return dp[l][r]
        if l == r:
            dp[l][r] = A[l]
        else:
            dp[l][r] = max(A[l]-score(l+1, r), A[r]-score(l, r-1))
        return dp[l][r]

    print(score(0, N-1))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(10**9)
#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:
        dp[r][l] = A[r]
        return dp[r][l]

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

    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: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(10**9)
#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: Time Limit Exceeded

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')]


sys.setrecursionlimit(10 ** 6)

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: Time Limit Exceeded

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

dicts = {}
def dfs(arr,st,ed):
    global dicts
    strs =str(st) + ","+str(ed)
    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
    #print(newarr)
    ans =  max( arr[0] - dfs(arr[1:], st + 1,ed), arr[-1] - dfs(arr[:-1] ,st, ed - 1) )
    #print(dicts)
    dicts[strs] = ans
    return ans 
    

ans = dfs(arr, 0,len(arr ) - 1)
print(ans)

Submission status: Time Limit Exceeded

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

dicts = {}
def dfs(arr,temparr):
    global dicts
    strs =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
    newarr = temparr.split(",")
    newstrs =  str(int(temparr[0]) + 1)+","+str(newarr[-1])
    #print(newarr)
    newstrs2 = str(int(temparr[0]))+","+ str( int(newarr[-1]) - 1) 
    ans =  max( arr[0] - dfs(arr[1:], newstrs), arr[-1] - dfs(arr[:-1] ,newstrs2) )
    #print(dicts)
    dicts[strs] = ans
    return ans 
    
temparr = []
tempstrs = "0,"+ str(len(arr ) - 1)

ans = dfs(arr, tempstrs)
print(ans)

Submission status: Time Limit Exceeded

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

dicts = {}
def dfs(arr,temparr):
    global dicts
    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:], temparr[1:]), arr[-1] - dfs(arr[:-1] ,temparr[:-1]) )
    #print(dicts)
    dicts[strs] = ans
    return ans 
    
temparr = []
for i in arr:
    temparr.append(str(i))

ans = dfs(arr, temparr)
print(ans)

Submission status: Time Limit Exceeded

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

dicts = {}
def dfs(arr):
    global dicts
    temparr = []
    temparr = [str(element) for element in arr]
    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: Time Limit Exceeded

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

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: Time Limit Exceeded

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

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

for diff in range(1, n):
    for L in range(n-diff):
        H = L+diff
        mem[L][H] = max(arr[L]-mem[L+1][H], arr[H]-mem[L][H-1])

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

Submission status: Time Limit Exceeded

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

def recursive(i,j):
  if i>j:
    return 0
  elif dp.get((i,j)):
    return dp[(i,j)]
  dp[(i,j)]=max(nums[i]-recursive(i+1,j),nums[j]-recursive(i,j-1))
  return dp[(i,j)]

dp={}
n=int(input())
nums=list(map(int,input().split()))
#print(dp)
print(recursive(0,n-1))

Submission status: Time Limit Exceeded

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]=a[l]
        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: Time Limit Exceeded

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:
        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: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
# dp[x][y][Person]:= 左端がx 番目,右端がy 番目の時の,この時動かすのがPersonの時の X - Y の値(0<=x<=Y<N)
dp = [[[0, 0] for j in range(N)] for i in range(N)]
for i in range(N):
    dp[i][i][0] = a[i]
    dp[i][i][1] = -a[i]

for i in range(1, N+1):
    # y-x = i  thus y = x+i  0<=x<N and 0<=x+i<N thus 0<=x <N-i
    for x in range(N-i):
        dp[x][x+i][0] = max(a[x]+dp[x+1][x+i][1], a[x+i]+dp[x][x+i-1][1])
        dp[x][x+i][1] = min(dp[x+1][x+i][0]-a[x], dp[x][x+i-1][0]-a[x+i])

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

Submission status: Time Limit Exceeded

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

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: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

N = int(input())
scores = np.array(list(map(int, input().split())), dtype='int32')

@njit('i8(i4[:],i4,i4)', cache=True)
def get_max_score(scores, i, j):
    if i == j:
        return scores[i]
    return max(scores[i] - get_max_score(scores, i+1, j), scores[j] - get_max_score(scores, i, j-1))

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

N = int(input())
scores = np.array(list(map(int, input().split())), dtype='int64')

@njit('i8(i8[:],i8,i8)', cache=True)
def get_max_score(scores, i, j):
    if i == j:
        return scores[i]
    return max(scores[i] - get_max_score(scores, i+1, j), scores[j] - get_max_score(scores, i, j-1))

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

Submission status: Time Limit Exceeded

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

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

def get_max_score(scores, i, j):
    if i == j:
        return scores[i]
    return max(scores[i] - get_max_score(scores, i+1, j), scores[j] - get_max_score(scores, i, j-1))

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

Submission status: Time Limit Exceeded

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

for width in range(1, N+1):
    for i in range(N-width+1):
        j = i + width

        if (N - width) % 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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
a = LIST()

lim = 3001
dp = [[0]*lim for _ in range(lim)]
cnt = 0
for i in range(1, N+1):
	for l in range(N-i+1):
		cnt += 1
		r = l+i
		if (N-i)%2: #後手
			dp[l][r] = min(dp[l+1][r]-a[l], dp[l][r-1]-a[r-1])
		else: #先手
			dp[l][r] = max(dp[l+1][r]+a[l], dp[l][r-1]+a[r-1])

print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
a = LIST()

lim = 3001
dp = [[0]*lim for _ in range(lim)]
cnt = 0
for i in range(1, N+1):
	for l in range(N-i+1):
		cnt += 1
		r = l+i
		if (N-i)%2: #後手
			dp[l][r] = min(dp[l+1][r]-a[l], dp[l][r-1]-a[r-1])
		else: #先手
			dp[l][r] = max(dp[l+1][r]+a[l], dp[l][r-1]+a[r-1])

print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N = INT()
a = LIST()

lim = 3001
dp = [[0]*lim for _ in range(lim)]
flg = [[0]*lim for _ in range(lim)]

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

	if i+1 == j:  #最後の一手
		flg[i][j] = 1
		if N%2:  #先手
			dp[i][j] = a[i]
			return dp[i][j]
		else:    #後手
			dp[i][j] = -a[i]
			return dp[i][j]
	else:
		if (N-(j-i))%2:  #後手
			dp[i][j] = min(DFS(i+1, j)-a[i], DFS(i, j-1)-a[j-1])
			flg[i][j] = 1
			return dp[i][j]
		else:  #先手
			dp[i][j] = max(DFS(i+1, j)+a[i], DFS(i, j-1)+a[j-1])
			flg[i][j] = 1
			return dp[i][j]


print(DFS(0, N))

Submission status: Time Limit Exceeded

Solution code:
n= int(input())
a = [int(i) for i in input().split(' ')] 
def solve(fst, lst): 
    global n
    global a
    # print(n,a)
    dp = [[0]*n for i in range(n)] 
    for l in range(1,n+1): 
        for i in range(n-l+1): 
            if l==1:
                dp[i][i+l-1] = a[i] 
            else:
                dp[i][i+l-1] = max( a[i+l-1] - dp[i][i+l-2] , a[i] - dp[i+1][i+l-1])
    # print(dp)
    return dp[0][n-1]

ans = solve(0,n-1) 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(int(10**7))
n= int(input())
a = [int(i) for i in input().split(' ')] 

@lru_cache(None)
def solve(fst, lst): 
    global n
    global a
    if fst>lst:
        return 0,0
    x1,y1 = solve(fst+1,lst)
    x2,y2 = solve(fst, lst-1) 
    if x1+a[fst] - y1 > x2+a[lst] - y2: 
        return y1,x1+a[fst]
    return y2,x2+a[lst] 

x,y = solve(0,n-1) 
print(y-x)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
from decimal import *
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def FI(): return float(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
A = LI()
memo = [[INF] * n for _ in range(n)]
def f(l, r):
    flg = (l + n - r) % 2
    if l > r:
        return 0
    if memo[l][r] != INF:
        return memo[l][r]
    if flg:
        memo[l][r] = max(f(l + 1, r) + A[l], f(l, r - 1) + A[r])
    else:
        memo[l][r] = min(f(l + 1, r) - A[l], f(l, r - 1) - A[r])
    return memo[l][r]

print(f(0, n - 1))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)

N = int(input())
a = [0] + list(map(int, input().split()))

# @functools.lru_cache(None)
# def dp(i,j):
#     if i == j: return 0
#     if (N % 2 == 0 and (j - i) % 2 == 0) or (N % 2 == 1 and (j - i) % 2 == 1):
#         return max(dp(i+1,j) + a[i], dp(i,j-1) + a[j-1])
#     else:
#         return min(dp(i+1,j) - a[i], dp(i,j-1) - a[j-1])
#
# print(dp(1,N+1))

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

print(f(1,N))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)

N = int(input())
a = [0] + list(map(int, input().split()))

@functools.lru_cache(None)
def dp(i,j):
    if i == j: return 0
    if (N % 2 == 0 and (j - i) % 2 == 0) or (N % 2 == 1 and (j - i) % 2 == 1):
        return max(dp(i+1,j) + a[i], dp(i,j-1) + a[j-1])
    else:
        return min(dp(i+1,j) - a[i], dp(i,j-1) - a[j-1])

print(dp(1,N+1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
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: Time Limit Exceeded

Solution code:
n=int(input())
arr=list(map(int,input().split()))
dp=[[0]*n for _ in range(n)]
for i in range(n):
  if n%2==0:
    dp[i][i]=-arr[i]
  else:
    dp[i][i]=arr[i]
for i in range(1,n):
  for j in range(n-i):
    if (n-i)%2==0:
      dp[j][j+i]=min(dp[j][j+i-1]-arr[j+i],dp[j+1][j+i]-arr[j])
    else:
      dp[j][j+i]=max(dp[j][j+i-1]+arr[j+i],dp[j+1][j+i]+arr[j])
print(dp[0][n-1])