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:
n = int(input())
a = list(map(int, input().split()))

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

def rec(i=0, j=n):
    if i == j:
        return 0
    if dp[i][j] != -1:
        return dp[i][j]
    # 太郎
    if (n - (j-i))%2==0:
        dp[i][j] = max(a[i] + rec(i+1,j), a[j-1] +rec(i,j-1))
    else:
        dp[i][j] = min(-a[i] + rec(i+1,j), -a[j-1] +rec(i,j-1))
    return dp[i][j]
print(rec())

Submission status: Runtime Error

Solution code:
# coding: utf-8
from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

@lru_cache(maxsize = None)
def f2(i, j, a):
    if i == j:
        return(a[i])
    return(max(a[i] - f2(i + 1, j, a), a[j] - f2(i, j - 1, a)))

n = int(input()) # 1 <= n <= 3000
a = list(map(int, input().split()))
print(f2(0, n - 1, a))

Submission status: Runtime Error

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


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

memo = makelist(N+1, N+1)

def solve(bg, ed, turn): # int * int * bool
    if memo[bg][ed] > 0:
        return memo[bg][ed]
    else:
        if bg == ed:
            memo[bg][ed] = a[bg] * (1 if turn else -1)
            return memo[bg][ed]
        else:
            left = solve(bg+1, ed, not turn)
            right = solve(bg, ed-1, not turn)
            if turn: # 先攻
                memo[bg][ed] = max(left + a[bg], right + a[ed])
            else:
                memo[bg][ed] = min(left - a[bg], right - a[ed])
            return memo[bg][ed]
                
solve(N//2, N, (N-N//2)%2 == (N-1)%2)
print(solve(1, N, True))

Submission status: Runtime Error

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


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

memo = makelist(N+1, N+1)

def solve(bg, ed, turn): # int * int * bool
    if memo[bg][ed] > 0:
        return memo[bg][ed]
    else:
        if bg == ed:
            memo[bg][ed] = a[bg] * (1 if turn else -1)
            return memo[bg][ed]
        else:
            left = solve(bg+1, ed, not turn)
            right = solve(bg, ed-1, not turn)
            if turn: # 先攻
                memo[bg][ed] = max(left + a[bg], right + a[ed])
            else:
                memo[bg][ed] = min(left - a[bg], right - a[ed])
            return memo[bg][ed]
                

print(solve(1, N, True))

Submission status: Runtime Error

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

Solution code:
import sys
from collections import deque

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

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

n, m = map(int, input().split())
g = [[] for _ in range(n)]

if n > 2000 or m > 2000:
    exit()

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

q = int(input())
if q > 2000:
    exit()

query = [list(map(int, input().split())) for _ in range(q)]

color = [0] * n

def dfs(node, dist, dist_max, col, pre_node):
    if dist > dist_max:
        return
    if color[node] == 0:
        color[node] = col
    if dist == dist_max:
        return
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist+1, dist_max, col, node)

for v, d, c in query[::-1]:
    v -= 1
    dfs(v, 0, d, c, -1)

for co in color:
    print(co)

Submission status: Runtime Error

Solution code:
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)