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:
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
        print(L, H, n, i)
        mem[L][H] = max(arr[L]-mem[L+1][H], arr[H]-mem[L][H-1])

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

Submission status: Wrong Answer

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))
    return ret
print(solve(0,n-1))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=0
r=-1
m=1
x,y=0,0
a=[int(i) for i in input().split()]
while l+1-r!=n+2:
	if m%2==1:
		if a[l]>=a[r]:
			x+=a[l]
			l+=1
		else:
			x+=a[r]
			r-=1
		
	else:
		if a[l]>=a[r]:
			y+=a[l]
			l+=1
		else:
			y+=a[r]
			r-=1
		
	m+=1
print(x-y)

Submission status: Wrong Answer

Solution code:
from collections import deque

n = int(input())
a = deque(map(int, input().split()))
x, y = 0, 0

for i in range(n):
    if a[0] > a[-1]:
        d = a.popleft()
    else:
        d = a.pop()
    
    if i%2 == 0:
        x += d
    else:
        y += d

print(x-y)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * (n-t+1) for t in range(1, n+1)]
dp[0] = a
for t in range(1, n):
    for i in range(n-t):
        dp[t][i] = max(-dp[t-1][i+1] + a[i], -dp[t-1][i] + a[i+t])
print(dp)
print(dp[n-1][0])

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

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

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

    # 右は開区間[i,j)
    for length in range(1,N+1):
        for i in range(N-length+1):
            j = i + length
            if (N-length)%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])



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

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

points = [0,0]

flag = 0
while True:
  for i in range(2):
    if len(a) == 0:
      flag = 1
      break
    
    if a[0] >= a[-1]:
      points[i] += a.popleft()
    else:
      points[i] += a.pop()
   
  if flag==1:
    break

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[[float("inf")]*(n+1) for _ in range(n+1)]
z=0
for l in range(n):
    dp[l][l]=0

for k in range(1,n+1):
    for i in range(n-k+1):
        j=i+k
   
        if (n-(i+j))%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: Wrong Answer

Solution code:
import numpy as np
n=int(input())
li=list(map(int,input().split()))
dp=np.full((n,n),0)
for l in range(n-1,-1,-1):
    for r in range(l,n):
        if l==r:
            dp[l][r]=li[l]
        else:
            dp[l][r]=max(li[l]-dp[l+1][r],li[r]-dp[l][r-1])
print(dp[0][-1])

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
s=0
for i in range(n):
    if i%2==0:
        if l[0]>=l[-1]:
            s+=l[0]
            del l[0]
        else:
            s+=l[-1]
            del l[-1]
    else:
        if l[0]>=l[-1]:
            s-=l[0]
            del l[0]
        else:
            s-=l[-1]
            del l[-1]
print(s)

Submission status: Wrong Answer

Solution code:
def f(l,beg,end):
    if beg>=end:
        return 0
    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)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

l=deque(a)

k=0

ans=0
while n>0:
    if k%2==0:
        ans += max( l[0], l[len(l)-1] )
        if l[0]>=l[len(l)-1]:
            l.popleft()
        else:
            l.pop()
        k+=1
        n-=1
        
    else:
        ans-= max(l[0], l[len(l)-1])
        if l[0]>=l[len(l)-1]:
            l.popleft()
        else:
            l.pop()
        k-=1
        n-=1


print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


def solve(N,A):
    s,e = 0, N-1
    dp = [[0]*N for i in range(N)]
    for k in range(N):
        for i in range(N):
            j = i+k
            if j>=N:
                continue
            sign = (-1)**(N-1-k)
            if k==0:
                dp[i][j] = sign*A[i]
                continue
            dp[i][j] = sign*max(sign*dp[i+1][j]+A[i],sign*dp[i+1][j]+A[j])
    ans = dp[0][N-1]
    return ans
print(solve(N,A))

Submission status: Wrong Answer

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

ans = 0
for i in range(len(a)):
  if i%2==0:
    f = 1
  else:
    f = (-1)
  if a[0]>=a[-1]:
    ans = ans+a[0]*f
    a=a[1:]
  else:
    a=a[:-1]
    ans = ans+a[-1]*f
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
a=range(1,n+1)
dp=[[0]*n for _ in range(n)]
# dp[i][j]:i<=j,i番目からj番目までの数列(j-i+1個)を前にした時、ゲーム終了までに自分が取れる最大得点。i,j=0,..,n-1
sa=[0]
s=0
for ai in a:
      s+=ai
      sa.append(s)
for len in range(1,n+1):
      for l in range(n-len+1):
            r=l+len-1
            s=sa[r+1]-sa[l]
            dp[l][r]=max(s-dp[l][r-1],s-dp[l+1][r] if l+1<n else 0)
s=sum(a)
print(2*dp[0][-1]-sa[-1])

Submission status: Wrong Answer

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

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

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

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

for width in range(1, n + 1):
    for l in range(n + 1):
        r = width + l
        if r <= l or r > n:
            continue
        if (r - l) % 2 == 0:
            dp[l][r] = max(dp[l + 1][r] + a[l], dp[l][r - 1] + a[r - 1])
        else:
            dp[l][r] = min(dp[l + 1][r] - a[l], dp[l][r - 1] - a[r - 1])

print(dp[0][n])

Submission status: Wrong Answer

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

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

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

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

for width in range(1, n + 1):
    for l in range(n + 1):
        r = width + l
        if r <= l or r > n:
            continue
        if (r - l) % 2 == 1:
            dp[l][r] = max(dp[l + 1][r] + a[l], dp[l][r - 1] + a[r - 1])
        else:
            dp[l][r] = min(dp[l + 1][r] - a[l], dp[l][r - 1] - a[r - 1])

print(dp[0][n])

Submission status: Wrong Answer

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

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

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

for x in range(n + 1):
    for y in range(n + 1):
        if x + y > n or (x == 0 and y == 0):
            continue
        elif (x + y) % 2 == 1:
            if x - 1 >= 0:
                a_ = dp[x - 1][y] + a[x - 1]
            if y - 1 >= 0:
                b_ = dp[x][y - 1] + a[-y]
            if x - 1 >= 0 and y - 1 >= 0:
                dp[x][y] = max(a_, b_)
            elif x - 1 >= 0:
                dp[x][y] = a_
            else:
                dp[x][y] = b_
        else:
            if x - 1 >= 0:
                a_ = dp[x - 1][y] - a[x - 1]
            if y - 1 >= 0:
                b_ = dp[x][y - 1] - a[-y]
            if x - 1 >= 0 and y - 1 >= 0:
                dp[x][y] = min(a_, b_)
            elif x - 1 >= 0:
                dp[x][y] = a_
            else:
                dp[x][y] = b_
        if x + y == n:
            ans = max(ans, dp[x][y])

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int,input().split()))
dp=[[0]*(N+1) for i in range(N+1)]
for W in range(N):#幅
    for l in range(N-W):#左端
        r=l+W
        if((N-(W+1))%2==0):
            dp[l][r]=max(a[l]+dp[l+1][r],dp[l][r-1]+a[r])
        else:
            if(a[l]>a[r]):
                dp[l][r]=dp[l+1][r]
            else:
                dp[l][r]=dp[l][r-1]
T=dp[0][N-1]
J=sum(a)-dp[0][N-1]
print(T-J)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = []
for i in range(n):
    if a[-1] > a[0]:
        s.append(a.pop())
    else:
        s.append(a.pop(0))
print(sum(s[::2])-sum(s[1:][::2]))

Submission status: Wrong Answer

Solution code:
n=int(input())
A=list(int(i) for i in input().split())
a=[0,0]
dp=[[a for i in range(n)] for j in range(n)]
for i in range(n-1,-1,-1):
    for j in range(i,n):
      if i==j:
        dp[i][j][0]=A[i]
        dp[i][j][1]=-A[i]
      else:
        dp[i][j][0]=max(A[i]+dp[i+1][j][1],A[j]+dp[i][j-1][1])
        dp[i][j][1]=-dp[i][j][0]
#print(dp[0][-1][0])
print(dp)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    a = list(map(int, input().split()))
    a = deque(a)
    X,Y = 0,0
    res = 0
    while len(a) > 1:
        action = 0
        if a[0] < a[-2]:
            temp = a[-1] - a[-2]
            action = 1
        else:
            temp = a[-1] - a[0]
            action = 0
        if a[1] < a[-1]:
            if temp < a[0] - a[-1]:
                action = 0
                temp = a[0] - a[-1]
        else:
            if temp < a[0] - a[1]:
                action = 2
                temp = a[0] - a[1]
        res += temp
        if action == 0 or action == 3:
            a.pop()
            a.popleft()
        elif action == 1:
            a.pop()
            a.pop()
        else:
            a.popleft()
            a.popleft()
    if a:
        res += a[0]
    print(res)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

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


def solve():
    n, *a = map(int, read().split())
    a = tuple(a)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[i + 1][j]
            R = a[j] - dp[i][j - 1]
            if L > R:
                dp[i][j] = L
            else:
                dp[i][j] = R
    for i in dp:
        print(i)
    return dp[0][n - 1]


print(solve())

Submission status: Wrong Answer

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

dp=[[0]*(n) for i in range(n)]

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

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

Submission status: Wrong Answer

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

X, Y = 0, 0

head, tail = 0, N - 1
for i in range(N):
  if head == tail:
    pop = a[head]
  else:
    if a[head] - max(a[head + 1], a[tail]) > a[tail] - max(a[head], a[tail - 1]):
      pop = a[head]
      head += 1
    else:
      pop = a[tail]
      tail -= 1

  if i % 2 == 0:
    X += pop
  else:
    Y += pop

print(X - Y)

Submission status: Wrong Answer

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

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

print(judge(0,n-1))

Submission status: Wrong Answer

Solution code:
def dequeScore(N,a):
	if N<1:
		return None
	#check who plays last
	currentTaro = ((N%2)==1)

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

	for i in range(1,N):
		#alternate player, 
		currentTaro = not currentTaro

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

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


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

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

Submission status: Wrong Answer

Solution code:
def main(N,a):
  return 2

Submission status: Wrong Answer

Solution code:
def main(N, a):
  return 2

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
a = deque(list(map(int,input().split())))
#XもYも最大値を取ろうとする
Pt = 0
PM = 1
for i in range(N):
    if len(a) == 2:
        Pt += (max(a)-min(a))*PM
        break
    if len(a) == 1:
        Pt = a[0]
        break
    if a[0]-a[1] > a[-1]-a[-2]:
        t = a.popleft()
    else:
        t = a.pop()
    Pt += t*PM
    PM *= -1
print(Pt)

Submission status: Wrong Answer

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


def add(x, y, turn, val):
    if turn:
        y += val
    else:
        x += val
    return x, y


x = 0
y = 0

turn = 0
while A:
    if len(A) == 1:
        val = A.pop()
        x, y = add(x, y, turn, val)
        continue

    if A[0] - A[1] > A[-1] - A[-2]:
        val = A.popleft()
    elif A[0] - A[1] < A[-1] - A[-2]:
        val = A.pop()
    elif A[0] > A[-1]:
        val = A.popleft()
    else:
        val = A.pop()
    x, y = add(x, y, turn, val)
    turn = 1-turn

print(x-y)

Submission status: Wrong Answer

Solution code:
import sys
# input処理を高速化する
input = sys.stdin.readline
def chmax(a, b):
    if a >= b:
        return a
    return b
def chmin(a, b):
    if a <= b:
        return a
    return b
def main():
    N = int(input())
    a = list(map(int, input().split()))
    # aiからajのX−Yの最大値
    # [左端,右端)=[l,r)からの遷移    
    # 左をとる[l+1,r)、右をとる[l,r−1)の2通り
    dp = [[0] * (N+2)  for _ in range(N+2)]
    print(dp)
    for len in range(1, N + 1):
        for i in range(N + 1 - len):
            j = i + len
            if (N - len) % 2 == 0:
                dp[i][j] = chmax(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
            else:
                dp[i][j] = chmin(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])
    print(dp)
    print(dp[0][N])
main()

Submission status: Wrong Answer

Solution code:
import sys
# input処理を高速化する
input = sys.stdin.readline
def chmax(a, b):
    if a >= b:
        return a
    return b
def chmin(a, b):
    if a <= b:
        return a
    return b
def main():
    N = int(input())
    a = list(map(int, input().split()))
    # aiからajのX−Yの最大値
    # [左端,右端)=[l,r)からの遷移    
    # 左をとる[l+1,r)、右をとる[l,r−1)の2通り
    dp = [[0] * (N+1)  for _ in range(N+1)]
    print(dp)
    for len in range(1, N + 1):
        for i in range(N + 1 - len):
            j = i + len
            if (N - len) % 2 == 0:
                dp[i][j] = chmax(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
            else:
                dp[i][j] = chmin(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])
    print(dp)
    print(dp[0][N])
main()

Submission status: Wrong Answer

Solution code:
import collections
from collections import deque

n=int(input())
a=deque(map(int, input().split()))  

x=0
y=0

for i in range(n):
    if i%2==0:
        if len(a)>=2:
            if a[-1]-max(a[-2],a[0])>=a[0]-max(a[1],a[-1]):
                x+=a[-1]
                a.pop()
            else:
                x+=a[0]
                a.popleft()
                
        else:
            if a[-1]>=a[0]:
                x+=a[-1]
                a.pop()
            else:
                x+=a[0]
                a.popleft()
                
        
    else:
        if len(a)>=2:
            if a[-1]-max(a[-2],a[0])>=a[0]-max(a[1],a[-1]):
                y+=a[-1]
                a.pop()
            else:  
                y+=a[0]
                a.popleft()
        
        else:
            if a[-1]>=a[0]:
                y+=a[-1]
                a.pop()
            else:
                y+=a[0]
                a.popleft()
        
            
print(x-y)

Submission status: Wrong Answer

Solution code:
import collections
from collections import deque

n=int(input())
a=deque(map(int, input().split()))  

x=0
y=0

for i in range(n):
    if i%2==0:
        if len(a)>=2:
            if a[-1]-max(a[-2],a[0])>=a[0]-max(a[1],a[-1]):
                x+=a[-1]
                a.pop()
            else:
                x+=a[0]
                a.popleft()
                
        else:
            if a[-1]>=a[0]:
                x+=a[-1]
                a.pop()
            else:
                x+=a[0]
                a.popleft()
                
        
    else:
        if len(a)>=2:
            if a[-1]-max(a[-2],a[0])>a[0]-max(a[1],a[-1]):
                y+=a[-1]
                a.pop()
            else:  
                y+=a[0]
                a.popleft()
        
        else:
            if a[-1]>=a[0]:
                y+=a[-1]
                a.pop()
            else:
                y+=a[0]
                a.popleft()
        
            
print(x-y)

Submission status: Wrong Answer

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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    print(A)
    c = [[None] * (N + 1) for _ in range(N + 1)]
    def dp(r, l, A, c):
        if r == l:
            return A[r]
        if c[r][l] != None:
            return c[r][l]
        print(r, l)
        t = max(-dp(r + 1, l, A, c) + A[r],
                -dp(r, l - 1, A, c) + A[l])
        c[r][l] = t
        return t
    
    print(dp(0, N - 1, A, c))


main()

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
a=np.array(list(map(int,input().split())))
dp=np.zeros((N,N,2))
for i in range(N):
    dp[i,i,0]=a[i]
    dp[i,i,1]=-a[i]
for i in reversed(range(N-1)):
    dp[i,i+1:,0]=np.maximum(dp[i+1,i+1:,1]+a[i],dp[i,i:N-1,1]+a[i+1:])       
    dp[i,i+1:,1]=np.minimum(dp[i+1,i+1:,0]-a[i],dp[i,i:N-1,0]-a[i+1:])         
    
print(int(dp[0,N-1,0]))

Submission status: Wrong Answer

Solution code:
from collections import deque as dq
N = int(input())
deq = dq(list(map(int, input().split())))
dp = [0 for _ in range(N // 2 + N % 2)]
if N - 1:
  if deq[0] > deq[-1]:
    dp[0] = deq.popleft()
  else:
    dp[0] = deq.pop()
  if deq[0] > deq[-1]:
    dp[0] -= deq.popleft()
  else:
    dp[0] -= deq.pop()
for i in range(N // 2):
  if i >= N // 2 - 2:
    break
  if deq[0] - max(deq[1], deq[-1]) > deq[-1] - max(deq[0], deq[-2]):
    dp[i + 1] = dp[i] + deq.popleft()
  else:
    dp[i + 1] = dp[i] + deq.pop()
  if deq[0] - max(deq[1], deq[-1]) > deq[-1] - max(deq[0], deq[-2]):
    dp[i + 1] -= deq.popleft()
  else:
    dp[i + 1] -= deq.pop()
if len(deq) >= 2:
  if deq[0] > deq[-1]:
    dp[N // 2 - 1] = dp[N // 2 - 2] + deq.popleft()
  else:
    dp[N // 2 - 1] = dp[N // 2 - 2] + deq.pop()
  if deq[0] > deq[-1]:
    dp[N // 2 - 1] -= deq.popleft()
  else:
    dp[N // 2 - 1] -= deq.pop()
if N % 2:
  dp[N // 2] = dp[N // 2 - 1] + deq.pop()
print(dp[N // 2 + N % 2 - 1])
#print(dp)
#print(deq)

Submission status: Wrong Answer

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

from collections import deque

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

"""
・x < M > y → x+y-Mに取り替える
・V字型に帰着
・貪欲

"""

B = deque() # 修正後
for a in A:
    if len(B) > 1 and B[-2] <= B[-1] >= a:
        x = B[-2] + a - B[-1]
        B.pop()
        B[-1] = x
    else:
        B.append(a)

pts = [0,0]
player = 0
while B:
    if B[0] > B[-1]:
        pts[player] += B[0]
        B.popleft()
    else:
        pts[player] += B[-1]
        B.pop()
    player ^= 1

answer = pts[0] - pts[1]
print(answer)

Submission status: Wrong Answer

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

from collections import deque

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

"""
・x < M > y → x+y-Mに取り替える
・V字型に帰着
・貪欲

"""

B = deque() # 修正後
for a in A:
    if len(B) > 1 and B[-2] < B[-1] > a:
        x = B[-2] + a - B[-1]
        B.pop()
        B[-1] = x
    else:
        B.append(a)

B

pts = [0,0]
player = 0
while B:
    if B[0] > B[-1]:
        pts[player] += B[0]
        B.popleft()
    else:
        pts[player] += B[-1]
        B.pop()
    player ^= 1

answer = pts[0] - pts[1]
print(answer)

Submission status: Wrong Answer

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


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


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


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


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


def think(a):
    b = list(a)
    b.reverse()
    n = len(a)

    score_taro, score_jiro = 0, 0
    index_a, index_b = 0, 0
    turn_taro = True
    while index_a + index_b < n:
        if a[index_a] < b[index_b]:
            if turn_taro:
                score_taro += b[index_b]
                index_b += 1
            else:
                score_jiro += b[index_b]
                index_b += 1
        else:
            if turn_taro:
                score_taro += a[index_a]
                index_a += 1
            else:
                score_jiro += a[index_a]
                index_a += 1
        turn_taro = not turn_taro
    return score_taro - score_jiro


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
a = np.array([int(i) for i in input().split()], dtype=np.int64)

s = np.copy(a)
for i in range(1, n):
    s = np.maximum(a[:n-i]-s[1:n-i+1], a[i:]-s[:n-i])
    print(i, s)

print(s[0])

Submission status: Wrong Answer

Solution code:
import sys

N = int(sys.stdin.readline().strip())
A = [int(a) for a in sys.stdin.readline().strip().split(' ')]

turn = 0
scores = [0, 0]

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = {}
for i in range(n):
    dp[(i, i)] = a[i]

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

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

Submission status: Wrong Answer

Solution code:
def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        g0 = dp[i]
        g1 = dp[i + 1]
        for j in range(i + 1, n):
            L = a[i] - g1[j]
            R = a[j] - g0[j - 1]
            dp[i][j] = L if L > R else R
    print(*dp,sep="\n")
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))

Submission status: Wrong Answer

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

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

for length in range(1, n + 1):
    for i in range(n - length + 1):
        j = i + length

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

        print(i,j,dp[i][j])

print(dp[0][n])

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 = LI()
    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:
                if a[r+1]+dp[i] > dp[j]:
                    dp[j] = a[r+1]+dp[i]
            if l > 0:
                if a[l-1]+dp[i] > dp[j]:
                    dp[j2] = a[l-1]+dp[i]
        else:
            if r < n-1:
                if -a[r+1]+dp[i] < dp[j]:
                    dp[j] = -a[r+1]+dp[i]
            if l > 0:
                if -a[l-1]+dp[i] < dp[j]:
                    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()