Problem:


Score : 100 points

Problem Statement

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

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

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 3000

1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

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

Sample Input 1

4
10 80 90 30

Sample Output 1

10

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

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

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

Taro: (10, 80) → (10)

Jiro: (10) → ()

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

Sample Input 2

3
10 100 10

Sample Output 2

-80

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

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

Jiro: (100, 10) → (10)

Taro: (10) → ()

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

Sample Input 3

1
10

Sample Output 3

10

Sample Input 4

10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1

Sample Output 4

4999999995

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

Sample Input 5

6
4 2 9 7 1 5

Sample Output 5

2

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

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

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

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

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

Taro: (2, 9) → (2)

Jiro: (2) → ()

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



Sample input:
4
10 80 90 30


Sample output:
10

Submission status: Time Limit Exceeded

Solution code:
#!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():
    def dfs(d,m):
        if dp[m] != None:
            return dp[m]
        l = [0,0]
        for i in range(n+1):
            if p[i]&m:
                l[0] = i
                l[1] = i+n-1-d
                break
        if not d%2:
            res = -float("inf")
            for i in l:
                res = max(res,a[i]+dfs(d+1,m^p[i]))
            dp[m] = res
            return dp[m]
        else:
            res = float("inf")
            for i in l:
                res = min(res,-a[i]+dfs(d+1,m^p[i]))
            dp[m] = res
            return dp[m]
    n = I()
    a = LI()
    b = deque()
    p = [1 for i in range(n+1)]
    for i in range(n):
        p[i+1] = p[i]*2
    for i in range(1,n+1):
        b += [(p[i]-1) << j for j in range(n+1-i)]
    dp = [None for i in range(b[-1]+1)]
    dp[0] = 0
    print(dfs(0,b[-1]))
    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: Time Limit Exceeded

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():
    def dfs(d,m):
        if dp[m] != None:
            return dp[m]
        l = []
        for i in range(n+1):
            if p[i]&m:
                l.append(i)
                for j in range(i,n+1):
                    if not p[j]&m:
                        l.append(j-1)
                        break
                else:
                    l.append(n)
                break
        if not d%2:
            res = -float("inf")
            for i in l:
                res = max(res,a[i]+dfs(d+1,m^p[i]))
            dp[m] = res
            return dp[m]
        else:
            res = float("inf")
            for i in l:
                res = min(res,-a[i]+dfs(d+1,m^p[i]))
            dp[m] = res
            return dp[m]
    n = I()
    a = LI()
    b = deque()
    p = [1 for i in range(n+1)]
    for i in range(n):
        p[i+1] = p[i]*2
    for i in range(1,n+1):
        b += [(p[i]-1) << j for j in range(n+1-i)]
    dp = [None for i in range(b[-1]+1)]
    dp[0] = 0
    print(dfs(0,b[-1]))
    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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
N = int(input())
a = list(map(int,input().split(" ")))

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


def dfs(l,r,turn):
    if l == r:
        return 0

    if memo[l][r-1] != -1:
        return memo[l][r-1]

    if turn % 2 == 0:
        ret = max(a[l] + dfs(l+1,r,(turn+1)%2),a[r-1] + dfs(l,r-1,(turn+1)%2))
    else:
        ret = min(-a[l] + dfs(l+1,r,(turn+1)%2),-a[r-1] + dfs(l,r-1,(turn+1)%2))

    memo[l][r-1] = ret
    return memo[l][r-1]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


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

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

def func(x,y,cnt):
	if dp[x][y]>0: return dp[x][y]
	ret=0
	if x==y:
		if cnt%2==0:
			ret=A[x]
			dp[x][y]=ret
			return ret
		else:
			ret=-1*A[x]
			dp[x][y]=ret
			return ret
	if cnt%2==0:
		cnt+=1
		ret=max( func(x,y-1,cnt)+A[y] , func(x+1,y,cnt)+A[x]  )
	else:
		cnt+=1
		ret=min( func(x,y-1,cnt)-A[y] ,func(x+1,y ,cnt)-A[x] )

	dp[x][y]=ret
	return ret

func(0,N-1,0)

print dp[0][N-1]

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10000000)


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

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

def func(x,y,cnt):
	if dp[x][y]>0: return dp[x][y]
	ret=0
	if x==y:
		if cnt%2==0:
			ret=A[x]
			dp[x][y]=ret
			return ret
		else:
			ret=-1*A[x]
			dp[x][y]=ret
			return ret
	if cnt%2==0:
		cnt+=1
		ret=max( func(x,y-1,cnt)+A[y] , func(x+1,y,cnt)+A[x]  )
	else:
		cnt+=1
		ret=min( func(x,y-1,cnt)-A[y] ,func(x+1,y ,cnt)-A[x] )

	dp[x][y]=ret
	return ret

func(0,N-1,0)

print dp[0][N-1]

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10000000)


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

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

def func(x,y,cnt):
	ret=0
	if x==y:
		if cnt%2==0:
			ret=A[x]
			dp[x][y]=ret
			return ret
		else:
			ret=-1*A[x]
			dp[x][y]=ret
			return ret
	if cnt%2==0:
		cnt+=1
		ret=max( func(x,y-1,cnt)+A[y] , func(x+1,y,cnt)+A[x]  )
	else:
		cnt+=1
		ret=min( func(x,y-1,cnt)-A[y] ,func(x+1,y ,cnt)-A[x] )

	dp[x][y]=ret
	return ret

func(0,N-1,0)

print dp[0][N-1]

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10000000)


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

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

def func(x,y,cnt):
	ret=0
	if x==y:
		if cnt%2==0:
			ret=A[x]
			dp[x][y]=ret
			return ret
		else:
			ret=-1*A[x]
			dp[x][y]=ret
			return ret
	if cnt%2==0:
		cnt+=1
		ret+=max( func(x,y-1,cnt)+A[y] , func(x+1,y,cnt)+A[x]  )
	else:
		cnt+=1
		ret+=min( func(x,y-1,cnt)-A[y] ,func(x+1,y ,cnt)-A[x] )

	dp[x][y]=ret
	return ret

func(0,N-1,0)

print dp[0][N-1]

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10000000)


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

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

def func(x,y,cnt):
	if dp[x][y]!=0: return dp[x][y]

	ret=0
	if x==y:
		if cnt%2==0:
			ret=A[x]
			dp[x][y]=ret
			return ret
		else:
			ret=-1*A[x]
			dp[x][y]=ret
			return ret
	if cnt%2==0:
		cnt+=1
		ret+=max( func(x,y-1,cnt)+A[y] , func(x+1,y,cnt)+A[x]  )
	else:
		cnt+=1
		ret+=min( func(x,y-1,cnt)-A[y] ,func(x+1,y ,cnt)-A[x] )

	dp[x][y]=ret
	return ret

func(0,N-1,0)


print dp[0][N-1]

Submission status: Time Limit Exceeded

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
dp = [[0]*N for _ in range(N)]
flag = [[0]*N for _ in range(N)]
turn = True


def dfs(l, r, turn):
    if flag[l][r]:
        return dp[l][r]
    else:
        flag[l][r] = 1
        if l == r:
            if turn:
                dp[l][r] = A[l]
            else:
                dp[l][r] = -A[l]
            return dp[l][r]
        else:
            nt = not turn
            if turn:
                dp[l][r] = max(A[l]+dfs(l+1, r, nt), A[r]+dfs(l, r-1, nt))
            else:
                dp[l][r] = min(-A[l]+dfs(l+1, r, nt), -A[r]+dfs(l, r-1, nt))
            return dp[l][r]


print(dfs(0, N-1, True))

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 l in range(1, n+1):
    for i in range(n - l + 1):
        j = i + l
        if (n - l) % 2 == 0:
            dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j-1])
        else:
            dp[i][j] = min(dp[i+1][j] - a[i], dp[i][j-1] - a[j-1])

print(dp[0][n])

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())

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

for length in range(1,n+1):
    for stidx in range(n-length+1):
        # 次郎の手番
        if(n-length)%2:
            dp[stidx][stidx+length] = min(dp[stidx+1][stidx+length] - a[stidx],
                                          dp[stidx][stidx+length-1] - a[stidx+length-1])
        # 太郎の手番
        else:
            dp[stidx][stidx+length] = max(dp[stidx+1][stidx+length] + a[stidx],
                                          dp[stidx][stidx+length-1] + a[stidx+length-1])
            
print(dp[0][n])

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)

n = int(input())
a = list(map(int, input().split()))
INIT = 10**18
d = [[INIT for i in range(n+1)] for j in range(n+1)]

def p(l, r):
    if d[l][r] == INIT:
        if l == r-1: d[l][r] = (1-((n*3-r-l)%2)*2)*a[l]
        elif (n*3-l-r)%2 == 0: d[l][r]=max(p(l+1, r)+a[l], p(l, r-1)+a[r-1])
        else: d[l][r]=min(p(l+1, r)-a[l], p(l, r-1)-a[r-1])
    return d[l][r]

ans = p(0, n)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(200000)

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

INF = -(10**13)

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


def play(start: 'int',
         end: 'int') -> 'int':  # return the maximum X for range[start,end)
    # if start + 1 == end:
    #     return start
    if dp[start][end] != INF:
        return dp[start][end]
    length = end - start
    if (N - length) & 1 == 0:  # taro plays
        if length == 1:
            dp[start][end] = a[start]
            return a[start]
        else:
            dp[start][end] = max(a[start] + play(start + 1, end),
                                 a[end - 1] + play(start, end - 1))
            return dp[start][end]
    else:  # jiro plays
        if length == 1:
            dp[start][end] = 0
            return 0
        else:
            dp[start][end] = min(play(start + 1, end), play(start, end - 1))
            return dp[start][end]


print(2 * play(0, N) - sum(a))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
aN = LIST()

# メモ[左端位置][右端位置] = この局面からの結果
memo = [[None] * (N+1) for i in range(N+1)]

def dfs(turn, l, r):
    # 既に見た局面ならメモの内容を返す
    if memo[l][r] != None:
        return memo[l][r]
    # 全部取り切ったので終了
    if l > r:
        return 0
    # 先手番
    if turn == 0:
        mx = -INF
        mx = max(mx, dfs(turn+1, l+1, r) + aN[l])
        mx = max(mx, dfs(turn+1, l, r-1) + aN[r])
        # ここより深い所を探し終わったので結果をメモする
        memo[l][r]= mx
        return mx
    # 後手番
    else:
        mn = INF
        mn = min(mn, dfs(turn-1, l+1, r) - aN[l])
        mn = min(mn, dfs(turn-1, l, r-1) - aN[r])
        memo[l][r] = mn
        return mn

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
aN = LIST()

# メモ[左端位置][右端位置][現在のスコア] = この局面からの結果
memo = [[defaultdict(lambda: None) for j in range(N+1)] for i in range(N+1)]

def dfs(turn, l, r, x, y):
    # 既に見た局面ならメモの内容を返す
    if memo[l][r][x-y] != None:
        return memo[l][r][x-y]
    # 全部取り切ったので終了
    if l > r:
        return x - y
    # 先手番
    if turn == 0:
        mx = -INF
        mx = max(mx, dfs(turn+1, l+1, r, x+aN[l], y))
        mx = max(mx, dfs(turn+1, l, r-1, x+aN[r], y))
        # ここより深い所を探し終わったので結果をメモする
        memo[l][r][x-y] = mx
        return mx
    # 後手番
    else:
        mn = INF
        mn = min(mn, dfs(turn-1, l+1, r, x, y+aN[l]))
        mn = min(mn, dfs(turn-1, l, r-1, x, y+aN[r]))
        memo[l][r][x-y] = mn
        return mn

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
aN = LIST()

# メモ[手番][左端位置][右端位置] = この局面からの結果
memo = [[[None] * (N+1) for j in range(N+1)] for i in range(2)]

def dfs(turn, l, r, x, y):
    # 既に見た局面ならメモの内容を返す
    # if memo[turn][l][r] != None:
    #     return memo[turn][l][r]
    # 全部取り切ったので終了
    if l > r:
        return x - y
    # 先手番
    if turn == 0:
        mx = -INF
        mx = max(mx, dfs(turn+1, l+1, r, x+aN[l], y))
        mx = max(mx, dfs(turn+1, l, r-1, x+aN[r], y))
        # ここより深い所を探し終わったので結果をメモする
        memo[turn][l][r] = mx
        return mx
    # 後手番
    else:
        mn = INF
        mn = min(mn, dfs(turn-1, l+1, r, x, y+aN[l]))
        mn = min(mn, dfs(turn-1, l, r-1, x, y+aN[r]))
        memo[turn][l][r] = mn
        return mn

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

Submission status: Time Limit Exceeded

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

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

SCORE=dict()

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番
    #print(i,j,k,l)
    
    if SCORE.get((i,j))!=None:
        return SCORE.get((i,j))+k
    if i==j:
        SCORE[(i,j)]=0
        return k

        

    if l==1:
        SCORE[(i,j)]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[(i,j)]+k
    if l==-1:
        SCORE[(i,j)]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[(i,j)]+k



hand=N%2
for i in range(N+1):
    for j in range(N-i+1):
        score(j,j+i,0,(-1)**(j+j+i+hand))

print(SCORE[(0,N)])

Submission status: Time Limit Exceeded

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

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

SCORE=dict()

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番
    #print(i,j,k,l)
    
    if SCORE.get((i,j))!=None:
        return SCORE.get((i,j))+k
    if i==j:
        SCORE[(i,j)]=0
        return k

        

    if l==1:
        SCORE[(i,j)]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[(i,j)]+k
    if l==-1:
        SCORE[(i,j)]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[(i,j)]+k



hand=N%2
for i in range(N+1):
    for j in range(N-i):
        for k in range(j,N+1):
            score(j,k,0,(-1)**(j+k+hand))

print(SCORE[(0,N)])

Submission status: Time Limit Exceeded

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

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

SCORE=[[None for i in range(N+1)] for j in range(N+1)]

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番
    #print(i,j,k,l)
    
    if SCORE[i][j]!=None:
        return SCORE[i][j]+k
    if i==j:
        SCORE[i][j]=0
        return k

        

    if l==1:
        SCORE[i][j]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[i][j]+k
    if l==-1:
        SCORE[i][j]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[i][j]+k



hand=N%2
for i in range(N+1):
    for j in range(N-i):
        for k in range(j,N+1):
            score(j,k,0,(-1)**(j+k+hand))

print(SCORE[0][N])

Submission status: Time Limit Exceeded

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

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

SCORE=[[None for i in range(N+1)] for j in range(N+1)]

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番

    if i==j:
        return k
    if SCORE[i][j]!=None:
        return SCORE[i][j]+k
        

    if l==1:
        SCORE[i][j]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[i][j]+k
    if l==-1:
        SCORE[i][j]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[i][j]+k


print(score(0,N,0,1))

Submission status: Time Limit Exceeded

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

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

SCORE=dict()

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番

    if i==j:
        return k
    if SCORE.get((i,j))!=None:
        return SCORE.get((i,j))+k
        

    if l==1:
        SCORE[(i,j)]=max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))-k
        return SCORE[(i,j)]+k
    if l==-1:
        SCORE[(i,j)]=min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))-k
        return SCORE[(i,j)]+k


print(score(0,N,0,1))

Submission status: Time Limit Exceeded

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

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

def score(i,j,k,l):#A[i:j)が残っているときのscore,1:Xの手番,-1:Yの手番

    if i==j:
        return k

    if l==1:
        return max(score(i+1,j,k+A[i],-l),score(i,j-1,k+A[j-1],-l))
    if l==-1:
        return min(score(i+1,j,k-A[i],-l),score(i,j-1,k-A[j-1],-l))


print(score(0,N,0,1))

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()

    t = [[0]*n for _ in range(n)]
    for i in range(n):
        t[i][i] = a[i]

    for s in range(1,n):
        for i in range(n-s):
            j = i + s
            r = a[j] - t[i][j-1]
            u = a[i] - t[i+1][j]
            if r < u:
                r = u
            t[i][j] = r

    return t[0][-1]


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()

    m = {}
    def f(l,r):
        k = (l,r)
        if k in m:
            return m[k]
        if l == r:
            m[k] = a[l]
            return a[l]

        b = a[l] - f(l+1,r)
        t = a[r] - f(l,r-1)
        if b < t:
            b = t
        m[k] = b
        return m[k]

    r = f(0,n-1)

    return r


print(main())

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
*A, = map(int, input().split())
dp = [[-1]*(N+1-i) for i in range(N+1)]
for i in range(N+1):
    dp[0][i] = 0
t = (N & 1)
for l in range(1, N+1):
    S = dp[l-1]; T = dp[l]
    t ^= 1
    T[:] = (min(S[i+1] - A[i], S[i] - A[i+l-1]) for i in range(N-l+1)) if t else  (max(S[i+1] + A[i], S[i] + A[i+l-1]) for i in range(N-l+1))
print(T[0])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int,input().split()))
X,Y = 0,0
dp = [[0] * (N+1) for i in range(N+1)]
# dp[i][j] ans = dp[1][N]
for i in range(1,N+1):
    if N % 2 == 1:
        dp[i][i] = a[i-1]
    else:
        dp[i][i] = -a[i-1]
for i in range(N-1,0,-1):
    for j in range(1,N+1):
        if i >= j: continue
        if (j - i) % 2 != N % 2:
            dp[i][j] = max(a[i-1] + dp[i+1][j],a[j-1] + dp[i][j-1])
        else:
            dp[i][j] = min(-a[i-1] + dp[i+1][j],-a[j-1] + dp[i][j-1])
print(dp[1][N])

Submission status: Time Limit Exceeded

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

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
#dp[l][r]: 左l個右r個取ったところからの前-後max
for i in range(n):
	dp[i][n-1-i] = a[i]
for x in range(n-2, -1, -1):
	for y in range(x+1):
		l, r = y, x-y
		dp[l][r] = max(-dp[l+1][r] + a[l], -dp[l][r+1] + a[-(r+1)])

print(dp[0][0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
aaa = list(map(int, input().split()))
dp = [[[0, 0] for _ in range(n + 1)] for _ in range(n + 1)]
for w in range(1, n + 1):
    for l in range(n - w + 1):
        r = l + w
        # take left
        dpl = dp[l + 1][r]
        tl_x = aaa[l] + dpl[1]
        tl_y = dpl[0]
        tl_score = tl_x - tl_y
        # take_right
        dpr = dp[l][r - 1]
        tr_x = aaa[r - 1] + dpr[1]
        tr_y = dpr[0]
        tr_score = tr_x - tr_y
        dpc = dp[l][r]
        if tl_score > tr_score:
            dpc[0] = tl_x
            dpc[1] = tl_y
        else:
            dpc[0] = tr_x
            dpc[1] = tr_y
print(dp[0][n][0] - dp[0][n][1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
aaa = list(map(int, input().split()))
dp = [[0] * (n + 1) for _ in range(n)]
for i, a in enumerate(aaa):
    dp[i][i + 1] = (a, 0)
for w in range(2, n + 1):
    for l in range(n - w + 1):
        r = l + w
        # take left
        dpl, dpr = dp[l + 1][r]
        tl_x = aaa[l] + dpr
        tl_y = dpl
        tl_score = tl_x - tl_y
        # take_right
        dpl, dpr = dp[l][r - 1]
        tr_x = aaa[r - 1] + dpr
        tr_y = dpl
        tr_score = tr_x - tr_y
        if tl_score > tr_score:
            dp[l][r] = (tl_x, tl_y)
        else:
            dp[l][r] = (tr_x, tr_y)
print(dp[0][n][0] - dp[0][n][1])

Submission status: Time Limit Exceeded

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

N = int(input())
*A, = map(int, input().split())
memo = [[-1]*(N+1) for i in range(N+1)]
for i in range(N+1):
    memo[i][i] = 0
def dfs(p, q, t):
    if memo[p][q] != -1:
        return memo[p][q]
    if t:
        r = min(dfs(p+1, q, 0) - A[p], dfs(p, q-1, 0) - A[q-1])
    else:
        r = max(dfs(p+1, q, 1) + A[p], dfs(p, q-1, 1) + A[q-1])
    memo[p][q] = r
    return r

print(dfs(0, N, 0))

Submission status: Accepted

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 = [[0] * (N + 1) for _ in range(N + 1)]


for w in range(1, N + 1):
    for l in range(N - w + 1):
        r = w + l
        dp[l][r] = A[l] - dp[l + 1][r]
        if r > 0:
            dp[l][r] = max(dp[l][r], A[r - 1] - dp[l][r - 1])

print(dp[0][N])

Submission status: Accepted

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: Accepted

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

for num in range(1, N + 1):
    for start in range(N):
        end = start + num
        if end > N:
            break
        if num == 1:
            DP[start][end] = A[start]
        else:
            DP[start][end] = max(A[start] - DP[start+1][end], A[end - 1] - DP[start][end - 1])
print(DP[0][N])

Submission status: Accepted

Solution code:
def coun(a,i,j):
    if dp[i][j]!=-1:
        return dp[i][j]

    if i==j:
        return a[i]
    elif abs(i-j)==1:

        return max(a[i],a[j])
    dp[i][j]= max(min(coun(a,i+2,j),coun(a,i+1,j-1))+a[i],min(coun(a,i+1,j-1),coun(a,i,j-2))+a[j])

    return dp[i][j]

n= int(input())
a =[int(X ) for  X in input().split()]
dp = [[-1 for i in range(n)]for j in range(n)]
print(2*coun(a,0,n-1)-sum(a))