Problem:


Score : 500 points

Problem Statement

We have a deck consisting of N cards. Each card has an integer written on it. The integer on the i-th card from the top is a_i.

Two people X and Y will play a game using this deck. Initially, X has a card with Z written on it in his hand, and Y has a card with W written on it in his hand. Then, starting from X, they will alternately perform the following action:

Draw some number of cards from the top of the deck. Then, discard the card in his hand and keep the last drawn card instead. Here, at least one card must be drawn.

The game ends when there is no more card in the deck. The score of the game is the absolute difference of the integers written on the cards in the two players' hand.

X will play the game so that the score will be maximized, and Y will play the game so that the score will be minimized. What will be the score of the game?

Constraints

All input values are integers.

1 \leq N \leq 2000

1 \leq Z, W, a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N Z W
a_1 a_2 ... a_N

Output

Print the score.

Sample Input 1

3 100 100
10 1000 100

Sample Output 1

900

If X draws two cards first, Y will draw the last card, and the score will be |1000 - 100| = 900.

Sample Input 2

3 100 1000
10 100 100

Sample Output 2

900

If X draws all the cards first, the score will be |1000 - 100| = 900.

Sample Input 3

5 1 1
1 1 1 1 1

Sample Output 3

0

Sample Input 4

1 1 1
1000000000

Sample Output 4

999999999



Sample input:
3 100 100
10 1000 100


Sample output:
900

Submission status: Wrong Answer

Solution code:
N, Z, W = map(int, input().split())
A = list(map(int, input().split()))
a0 = A[-1]
res = 0
for i in reversed(range(N-1)):
    if A[i] > a0:
        res = max(abs(A[i]-a0), res)
        a0 = A[i]
a0 = Z
for i in reversed(range(N-1)):
    if A[i] < a0:
        res = max(abs(A[i]-a0), res)
        a0 = A[i]
res = max(res, abs(A[-1]-W))
print(res)

Submission status: Wrong Answer

Solution code:
N, Z, W = map(int, input().split())
A = [Z] + list(map(int, input().split()))
a0 = A[-1]
res = 0
for i in reversed(range(N)):
    if A[i] > a0:
        res = max(abs(A[i]-a0), res)
        a0 = A[i]
a0 = Z
for i in reversed(range(N)):
    if A[i] < a0:
        res = max(abs(A[i]-a0), res)
        a0 = A[i]
res = max(res, abs(A[-1]-W))
print(res)

Submission status: Wrong Answer

Solution code:
N, Z, W = map(int, input().split())
A = [Z] + list(map(int, input().split()))
a0 = Z
res = 0
for i in reversed(range(N)):
    if A[i] > a0:
        res = max(min(abs(A[i]-a0), abs(A[i]-W)), res)
        a0 = A[i]
a0 = Z
for i in reversed(range(N)):
    if A[i] < a0:
        res = max(min(abs(A[i]-a0), abs(A[i]-W)), res)
        a0 = A[i]
res = max(res, abs(A[-1]-W))
print(res)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,z,w = map(int, readline().split())
a = [w]+[*map(int, readline().split())]
n += 1

INF = 1<<30
dp0 = [-INF]*n
dp1 = [INF]*n

dp0[-1] = dp1[-1] = abs(a[-1]-a[-2])
for i in range(n-2,0,-1):
    dp0[i] = max(abs(a[-1]-a[i-1]),-min(dp1[i+1:]))
    dp1[i] = min(-abs(a[-1]-a[i-1]),-max(dp0[i+1:]))

print(dp0[1])

#print(a)
#print(dp0)
#print(dp1)

Submission status: Wrong Answer

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

# dp[pos][turn] = turnの番で相手がposまでカードを引いている場合の最終スコア
dp = [ [0]*2 for _ in range(N+1) ]

for i in range(N, -1, -1):
  # 先攻
  x = Z if i == N else a[N-1]
  y = a[i-1] if i else W
  dp[i][0] = max( dp[i][0], abs(y - x))

  # 後攻
  x = a[i-1] if i else Z
  y = W if i == N else a[N-1]
  dp[i][1] = min( dp[i][1], abs(x - a[N-1]))

res = -10**100
for i in dp:
  res = max(res, i[0])

print(res)

Submission status: Wrong Answer

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

# dp[pos][turn] = turnの番で相手がposまでカードを引いている場合の最終スコア
dp = [ [0]*2 for _ in range(N+1) ]

for i in range(N-1, -1, -1):
  # 先攻
  x = Z if i == N-1 else a[N-1]
  y = a[i-1] if i else W
  dp[i][0] = max( dp[i][0], dp[i+1][0], abs(y - x))

  # 後攻
  x = a[i-1] if i else Z
  y = W if i == N-1 else a[N-1]
  dp[i][1] = min( dp[i][1], dp[i+1][1], abs(x - a[N-1]))

print(dp[0][0])

Submission status: Wrong Answer

Solution code:
n,z,w=[int(x) for x in input().split()]

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

if(n==1):
  print(abs(a[0]-w))
else:
  print(min(abs(a[-1]-w),abs(a[-1]-a[-2])))

Submission status: Wrong Answer

Solution code:
N,Z,W=map(int,input().split())
A=list(map(int, input().split()))
if N==1:
  print(abs(A[-1]-W))
elif N==2:
  print(abs(A[-1]-W),abs(A[0]-A[-1]))
else:
  a=abs(A[-1]-W)
  b=abs(max(A[:N-1])-A[-1])
  print(max(a,b))

Submission status: Wrong Answer

Solution code:
N,Z,W=map(int,input().split())
A=list(map(int, input().split()))
if N==1:
  print(abs(A[-1]-W))
elif N==2:
  print(abs(A[-1]-W),abs(A[0]-A[-1]))
else:
  a=abs(A[-1]-W)
  b=abs(max(A[:N-1])-A[-1])
  c=abs(min(A[1:N-1])-A[-1])
  print(max(a,b,c))

Submission status: Wrong Answer

Solution code:
N, Y, Z = map(int, input().split())
As = list(map(int, input().split()))
dpx, dpy = [0]*(N-1), [0]*(N-1)
#dpx[i] = min(dpy[i+1]...dpy[N-2], abs(As[N-1]-As[i]))
#dpy[i] = max(dpx[i+1]...dpx[N-2], abs(As[N-1]-As[i]))
for i in range(N-2, -1, -1):
    mny, mxx = 10**10, 0
    for j in range(i+1, N-1):
        mny = min(mny, dpy[j])
        mxx = max(mxx, dpx[j])
    dpx[i] = max(mny, abs(As[N-1]-As[i]))
    dpy[i] = max(mxx, abs(As[N-1]-As[i]))
dpx.append(abs(As[N-1]-Z))
print(max(dpx))

Submission status: Wrong Answer

Solution code:
N, Y, Z = map(int, input().split())
As = list(map(int, input().split()))
dpx, dpy = [0]*(N-1), [0]*(N-1)
#dpx[i] = min(dpy[i+1]...dpy[N-2], abs(As[N-1]-As[i]))
#dpy[i] = max(dpx[i+1]...dpx[N-2], abs(As[N-1]-As[i]))
for i in range(N-2, -1, -1):
    mny, mxx = 10**10, 0
    for j in range(i+1, N-1):
        mny = min(mny, dpy[j])
        mxx = max(mxx, dpx[j])
    dpx[i] = min(mny, abs(As[N-1]-As[i]))
    dpy[i] = min(mxx, abs(As[N-1]-As[i]))
dpx.append(As[N-1]-Z)
print(max(dpx))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,Z,W,*A = map(int,read().split())

A = A[::-1]

if N == 1:
    answer = abs(A[0] - W)
    print(answer)
    exit()

INF = 10 ** 18
dp1 = np.full(N,-INF,np.int64) # 自分が特定のカードで止めた場合
dp2 = np.full(N,INF,np.int64)

last = A[0]
dp1[1] = abs(A[1] - last)
dp2[1] = abs(A[1] - last)
for i,x in enumerate(A[2:],2):
    a = dp2[1:i].max()
    b = dp1[1:i].min()
    c = abs(x - last)
    dp1[i] = min(a,c)
    dp2[i] = max(b,c)

# 自分が全部とる場合
x = abs(W - last)
# 自分がどこかで止める場合
y = np.max(dp1)
answer = max(x,y)
print(answer)

Submission status: Wrong Answer

Solution code:
N,Z,W = map(int,input().split())
A = list(map(int,input().split()))
abs_last = [abs(A[i]-A[N-1])for i in range(N)]

max_abs_last = max(abs_last)
if max_abs_last >= abs(A[-1]-W):
  print(max_abs_last)
else:
  print(abs(A[-1]-W))

Submission status: Wrong Answer

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

if N == 1 :
    a = abs(X - A[0])
    b = abs(A[0] - Y)
else :
    a = abs(A[N-1] - Y)
    b = abs(A[N-2] - A[N-1])

print(max(a, b))

Submission status: Wrong Answer

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

cards = [y0] + list(map(int, input().split()))
# yの手持ちはゲームに関与するため、リストに加えてしまう

xs = [[-1] * (n+1) for i in range(n+1)]
ys = [[-1] * (n+1) for i in range(n+1)] 
#xs[i][j] = xの手番で、xがcards[i]を持ちyがcards[j]を持っているとき(i<j)の最善スコア
#ys[i][j] = yの手番で、xがcards[j]を持ちyがcards[i]を持っているとき(i<j)の最善スコア

for i in range(n+1):
	xs[i][-1] = abs(cards[-1] - cards[i])
	ys[i][-1] = abs(cards[-1] - cards[i])

for j in range(n-1, -1, -1):

	# x[i][j] = max (y[j][j+1] , y[j][j+2] , ……, y[j][n] )
	for i in range(0, j):
		xs[i][j] = max(ys[j][j+1:n+1])

	for i in range(0, j):
		ys[i][j] = min(xs[j][j+1:n+1])

# print(max(xs[0][0], abs(cards[-1] - x0)) )

print(xs)
print(ys)
print(max(ys[0][1:]))

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(2*10**5)

# 入力
N, Z, W = map(int, input().split())
a = list(map(int, input().split()))


# バックトラック法により解を求める関数。i=1のとき、Xの手番、i=-1のときYの手番
@lru_cache(maxsize=None)
def f(i, m):
    return (
        max(
            abs(W - a[-1]) if m == N else abs(a[-(m + 1)] - a[-1]),
            max(f(-i, k) for k in range(1, m))
        ) if i == 1 and m >= 2 else
        min(
            abs(Z - a[-1]) if m == N else abs(a[-(m + 1)] - a[-1]),
            min(f(-i, k) for k in range(1, m))
        ) if i == -1 and m >= 2 else
        abs(a[-1] - a[-2]) if N >= 2 else
        abs(a[-1] - Z)
    )


# 出力
ans = f(1, N)
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(2*10**5)

# 入力
N, Z, W = map(int, input().split())
a = list(map(int, input().split()))


# バックトラック法により解を求める関数。i=1のとき、Xの手番、i=-1のときYの手番
@lru_cache(maxsize=None)
def f(i, m):
    return (
        max(
            abs(W - a[-1]) if m == N else abs(a[-(m + 1)] - a[-1]),
            *[f(-i, k) for k in range(1, m)]
        ) if i == 1 and m >= 2 else
        min(
            abs(Z - a[-1]) if m == N else abs(a[-(m + 1)] - a[-1]),
            *[f(-i, k) for k in range(1, m + 1)]
        ) if i == -1 and m >= 2 else
        abs(a[-1] - a[-2]) if N >= 2 else
        abs(a[-1] - Z)
    )


# 出力
ans = f(1, N)
print(ans)

Submission status: Wrong Answer

Solution code:
N, Z, W = map(int, input().split())
a = list(map(int, input().split()))
ans = max(abs(Z-W), abs(a[N-1]-W))
if N > 1:
  ans = max(ans,abs(a[N-2]-a[N-1]))
print(ans)

Submission status: Wrong Answer

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

def main():
    n, z, w = input().split()
    n = int(n)
    z = int(z)
    w = int(w)
    a = list(map(int, input().split()))

    dpx = [0] * n
    cx = [0] * n
    dpy = [0] * n
    cy = [0] * n
    dpx[n - 1] = abs(a[n - 1] - w)
    cx[n - 1] = a[n - 1]
    dpy[n - 1] = abs(a[n - 1] - a[n - 2]) if 1 < n else abs(z - a[n - 1])
    cy[n - 1] = a[n - 1]
    for i in range(n - 2, -1, -1):
        sx = abs(a[i] - cy[i + 1])
        if dpx[i + 1] < sx:
            dpx[i] = sx
            cx[i] = a[i]
        else:
            dpx[i] = dpx[i + 1]
            cx[i] = cx[i + 1]
        sy = abs(cx[i + 1] - a[i])
        if sy < dpy[i + 1]:
            dpy[i] = sy
            cy[i] = a[i]
        else:
            dpy[i] = dpy[i + 1]
            cy[i] = cy[i + 1]

    print(dpx[0])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def main():
    n, z, w = input().split()
    n = int(n)
    z = int(z)
    w = int(w)
    a = list(map(int, input().split()))

    dpx = [0] * n
    cx = [0] * n
    dpy = [0] * n
    cy = [0] * n
    dpx[n - 1] = abs(a[n - 1] - w)
    cx[n - 1] = a[n - 1]
    dpy[n - 1] = abs(z - a[n - 1])
    cy[n - 1] = a[n - 1]
    for i in range(n - 2, -1, -1):
        sx = abs(a[i] - cy[i + 1])
        if dpx[i + 1] < sx:
            dpx[i] = sx
            cx[i] = a[i]
        else:
            dpx[i] = dpx[i + 1]
            cx[i] = cx[i + 1]
        sy = abs(cx[i + 1] - a[i])
        if sy < dpy[i + 1]:
            dpy[i] = sy
            cy[i] = a[i]
        else:
            dpy[i] = dpy[i + 1]
            cy[i] = cy[i + 1]

    print(dpx[0])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,Z,W=map(int,input().split())
a=[int(i) for i in input().split()]
if N==1:
  print(W-a[0])
else:
  print(max(abs(W-a[-1]),abs(a[-2]-a[-1])))

Submission status: Wrong Answer

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

drawcount=0 #2人が引いた枚数
score=[0]*N #XがN枚引いた時の最少スコアを格納
score[N-1]=abs(a[N-1]-W) #Xが全部引いた時のスコア

for i in range(N-1):
  Xscore=a[i] #Xがi+1番目までのカードを引いた時（最後に引いたカードがXの数値)
  score[i]=10**9 #考えられるスコアの最大値を格納
  for j in range(i+1,N):
  	score[i]=min(abs(a[i]-a[j]),score[i]) 
    #yがi+1番目以降のカードを自由に引き、Xがi番目のカードを引いた時の最小スコアをi番目に格納
print(max(score))

Submission status: Wrong Answer

Solution code:
N, Z, W = map(int, input().split())
cards = list(map(int, input().split()))

if N == 1:
    print(cards[0] - W)
else:
    x = abs(cards[-1] - cards[-2])
    y = abs(cards[-1] - W)
    print(max(x, y))

Submission status: Wrong Answer

Solution code:
N,Z,W = map(int,input().split())
src = list(map(int,input().split()))

s1 = abs(src[-1] - W)
s2 = 0 if N==1 else min(abs(src[-2]-src[-1]), abs(src[-2]-W))

print(max(s1,s2))

Submission status: Wrong Answer

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

if N == 1:
    print(a[0] - W)
else:
    x = abs(a[-2] - a[-1])
    y = abs(a[-1] - W)
    z = min(abs(max(a) - a[-1]), abs(a[-2]-a[-1]))
    w = min(abs(min(a) - a[-1]), abs(a[-2]-a[-1]))
    
    ans = max(x, y, z, w)
    print(ans)

Submission status: Wrong Answer

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

if N == 1:
    print(a[0] - W)
else:
    x = abs(a[-2] - a[-1])
    y = abs(a[-1] - W)
    ans = max(x, y)
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
N,Z,W=list(map(int,input().split()))
i=0
a=list(map(int,input().split()))
b=math.fabs(a[N-1]-W)
c=math.fabs(a[N-2]-a[N-1])
print(max(b,c))

Submission status: Wrong Answer

Solution code:
n,z,w = map(int, input().split())

x = z
y = w

a = list(map(int, input().split()))
y_flg  = False
for i in range(len(a)):
    if  y_flg is False and x < a[i]:
        x = a[i]
        y_flg = True
        continue
    if y_flg is True and y > a[i]:
        y = a[i]
        y_flg = False

print(abs(x- y))

Submission status: Wrong Answer

Solution code:
x_list = []
y_list = []

n,z,w = map(int, input().split())

x_list.append(z)
y_list.append(w)

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

y_flg  = False
for i in range(len(a)):
    if  y_flg is False and x_list[0] < a[i]:
        x_list.append(a[i])
        y_flg = True
        continue
    if y_flg is True and y_list[0] > a[i]:
        y_list.append(a[i])
        y_flg = False

x_max = max(x_list)
y_max = min(y_list)

print(abs(x_max - y_max))

Submission status: Wrong Answer

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

def main():
    N, Z, W = map(int, input().split(" "))
    a = list(map(int, input().split(" ")))
    
    if N == 1:
        print(abs(a[0] - W))
    else:
        print(max(abs(a[0] - W), abs(a[N - 2] - a[N - 1])))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,z,w = map(int,input().split())
a = list(map(int,input().split()))
if (n>1):
    print(max(abs(a[-2]-a[-1]),abs(a[-1]-w)))
else:
    print(abs(a[0])-w)

Submission status: Wrong Answer

Solution code:
w=int(input().split()[2]);n=map(lambda x:abs(int(x)-w),input().split()[-2:]);print(max(n));

Submission status: Wrong Answer

Solution code:
from itertools import chain
N,_,W = map(int,input().split())
A = list(map(int,input().split()))
B = A.pop()
M = 10**9
m = 0
for a in chain(reversed(A),(W,)):
  x = abs(B-a)
  M,m = min(M,max(x,m)),max(m,min(x,M))
print(M)

Submission status: Wrong Answer

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

if n == 1:
    print(abs(a[0] - y))
else:
    print(max(abs(a[0] - y), abs(a[-1] - a[-2])))

Submission status: Wrong Answer

Solution code:
import functools
n,x,y = map(int, input().split())
a =  list(map(int, input().split()))

if n == 1:
    print(abs(a[0] - y))
    exit()

ax = [x] + a
ay = [y] + a
vx = [abs(ax[-1] - ay[i]) for i in range(n)]
vy = [abs(ay[-1] - ax[i]) for i in range(n)]
# print(vx,vy)
min_vy = []
my = vy[-1]
for i in range(n-1, -1, -1):
    my = min(my, vy[i])
    min_vy.append(my)
min_vy.reverse()
# print(min_vy)

max_vx = []
mx = vx[-1]
for i in range(n-1, -1, -1):
    mx = max(mx, vx[i])
    max_vx.append(mx)
max_vx.reverse()
# print(max_vx)

# @functools.lru_cache()
# def solve(x_turn, idx, x, y):
#     if idx == n:
#         return abs(x-y), (x,y)
#     if x_turn:
#         score = [solve(False, i+1, a[i], y) for i in range(idx, n)]
#         return max(score)
#     else:
#         score = [solve(True, i+1, x, a[i]) for i in range(idx, n)]
#         return min(score)

# print(solve(True, 0, x, y))        
x_turn = True
ix = 0
iy = 0
while ix < n and iy < n:
    if x_turn:
        if vx[iy] >= max_vx[iy+1]:
            print(vx[iy])
            exit()
        for i in range(iy+1, n-1):
            ix = n
            if max_vx[i] > max_vx[i+1]:
                ix = i
                break
        iy = ix+1
    else:
        if vy[ix] <= min_vy[ix+1]:
            print(vy[ix])
            exit()
        for i in range(ix+1, n-1):
            iy = n
            if min_vy[i] > min_vy[i+1]:
                iy = i
                break
        ix = iy+1
    x_turn = not x_turn

if x_turn:
    print(vx[-1])
else:
    print(vy[-1])

Submission status: Wrong Answer

Solution code:
l=input().split()
n=int(l[0])
w=int(l[2])
l=input().split()
a=[]
for i in range(n):
  a.append(int(l[n-1-i]))
s=[]
m=[]
if n>=3:
  s.append(abs(a[1]-a[0]))
  s.append(max(abs(a[2]-a[0]),abs(a[1]-a[0])))
  m=[s[0],min(s[0],s[1])]
  x=min(abs(a[2]-a[0]),m[0])
  for i in range(2,n-2):
    if(max(abs(a[i]-a[0]),m[i-2])>x):
      x=max(abs(a[i]-a[0]),m[i-2])
    s.append(max(abs(a[i+1]-a[0]),x,abs(a[1]-a[0])))
    m.append(min(s[-1],m[-1]))
  s.reverse()
  if n==3:
    del(s[0])
  res=[abs(w-a[0]),abs(a[-2]-a[-1])]
  a.reverse()
  for i in range(n-2):
    res.append(min(abs(a[-2]-a[-1]),abs(a[i]-a[-1]),min(s[i:])))
  print(max(res))
if n==2:
  print(max(abs(w-a[0]),abs(a[1]-a[0])))
if n==1:
  print(abs(w-a[0]))

Submission status: Wrong Answer

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

a_l_l = abs(Z - W)

for i in range(N):
    a_l_l = max(abs(a[-1] - W), a_l_l)
    if abs(a[i] - W) > abs(Z - W):
        Z = a[i]
    elif abs(a[i] - Z) > abs(Z - W):
        W = a[i]

print(max(abs(Z - W), a_l_l))

Submission status: Wrong Answer

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

a_l_l = abs(a[-1] - W)

for i in range(N):
    if abs(a[i] - W) > abs(Z - W):
        Z = a[i]
    elif abs(a[i] - Z) > abs(Z - W):
        W = a[i]

print(max(abs(Z - W), a_l_l))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


memo = {}
def dfs(i, no, a_list):
    if (i, no % 2) in memo:
        return memo[(i, no % 2)]
    n = len(a_list)
    if no % 2 == 0:
        ans = 0
        for j in range(i, n):
            me = a_list[j]
            ans = max(ans, abs(me - dfs(j + 1, no + 1, a_list)))
        memo[(i, no % 2)] = ans
        return ans
    else:
        ans = INF
        for j in range(i, n):
            me = a_list[j]
            ans = min(ans, abs(me - dfs(j + 1, no + 1, a_list)))
        memo[(i, no % 2)] = ans
        return ans


def main():
    N, Z, W = map(int, input().split())
    a_list = list(map(int, input().split()))
    last = a_list[-1]
    if N == 1:
        print(abs(last - W))
        return
    if N == 2:
        ans = 0
        ans = max(ans, abs(last - W))
        ans = max(ans, abs(a_list[0] - last))
        print(ans)
        return

    print(dfs(0, 0, a_list))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W




def main():
    N, Z, W = map(int, input().split())
    a_list = list(map(int, input().split()))
    last = a_list[-1]
    if N == 1:
        print(abs(last - W))
        return
    if N == 2:
        ans = 0
        ans = max(ans, abs(last - W))
        ans = max(ans, abs(a_list[0] - last))
        print(ans)
        return

    ans = 0
    # Xが全部
    ans = max(ans, abs(last - W))

    for i in range(1, N - 1):
        # Xが最後
        if len(a_list[i:-1]) != 0:
            ans = max(ans, abs(last - min(a_list[i:-1])))
        # Yが最後
        ans = max(ans, abs(max(a_list[:i]) - last))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, Z, W = map(int, input().split())
aa = list(map(int, input().split()))

m = 0
index = 0
aa = [Z] + aa + [W]
for i, a in enumerate(aa[:-1]):
    c = min([abs(a - b) for b in aa[i+1:]])
    m = max([m, c])

print(m)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def main():
    N, Z, W = map(int, input().split())
    a_list = list(map(int, input().split()))
    if N == 1:
        Z = a_list[0]
        print(abs(Z - W))
        return

    ans = 0
    last = a_list[-1]

    # Xが全部
    ans = max(ans, abs(last - W))

    # Xが最後
    if N >= 3:
        ans = max(ans, abs(last - min(a_list[1:-1])))
    # Yが最後
    ans = max(ans, abs(last - max(a_list[:-1])))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF=10**18

def main():
    N,Z,W=map(int,input().split())
    a=list(map(int,input().split()))
    dic={}
    def rec(z,w,now,t):
        if dic.get((now,t),None)!=None:
            return dic[(now,t)]
        if now>=N-1:
            return abs(z-w)
        if not t:
            res=-INF
            for i in range(now+1,N):
                r=rec(a[i],w,i,1)
                res=max(res,r)
        else:
            res=INF
            for i in range(now+1,N):
                r=rec(z,a[i],i,0)
                res=min(res,r)
        dic[(now,t)]=res
        return res

    return rec(Z,W,-1,0)
    
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF=10**18
def rec(z,w,now,t):
    global N
    if dic.get((z,w,now,t),None)!=None:
        return dic[(z,w,now,t)]
    if now==N-1:
        dic[(z,w,now,t)]=abs(z-w)
        return abs(z-w)
    if t==0:
        res=-INF
        for i in range(now+1,N):
            res=max(res,rec(a[i],w,i,1))
    elif t==1:
        res=INF
        for i in range(now+1,N):
            res=min(res,rec(z,a[i],i,0))
    dic[(z,w,now,t)]=res
    return res

N,Z,W=map(int,input().split())
a=list(map(int,input().split()))
dic={}

print(rec(Z,W,-1,0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF=10**18
def rec(z,w,now,t):
    global N
    if dic.get((z,w,now,t),None)!=None:
        return dic[(z,w,now,t)]
    if now==N-1:
        return abs(z-w)
    if t==0:
        res=-INF
        for i in range(now+1,N):
            res=max(res,rec(a[i],w,i,1))
    elif t==1:
        res=INF
        for i in range(now+1,N):
            res=min(res,rec(z,a[i],i,0))
    dic[(z,w,now,t)]=res
    return res

N,Z,W=map(int,input().split())
a=list(map(int,input().split()))
dic={}

print(rec(Z,W,-1,0))

Submission status: Time Limit Exceeded

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


def dfs(x, y, memo, A, N, Z, W):
    X = Z if x == 0 else A[x - 1]
    Y = W if y == 0 else A[y - 1]

    if memo[x][y] >= 0:
        return memo[x][y]
    else:
        if x == N or y == N:
            rst = abs(X - Y)
        else:
            if x <= y:
                rst = 0
                for i in range(y + 1, N + 1):
                    rst = max(rst, dfs(i, y, memo, A, N, Z, W))
            else:
                rst = 10 ** 10
                for i in range(x + 1, N + 1):
                    rst = min(rst, dfs(x, i, memo, A, N, Z, W))
        memo[x][y] = rst
        return rst


def main():
    # import sys
    # readline = sys.stdin.readline
    # readlines = sys.stdin.readlines

    N, Z, W = map(int, input().split())
    A = list(map(int, input().split()))
    memo = [[-1] * (N + 1) for _ in range(N + 1)]
    ans = dfs(0, 0, memo, A, N, Z, W)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


def dfs(x, y):
    global N, Z, W
    X = Z if x == 0 else A[x - 1]
    Y = W if y == 0 else A[y - 1]

    if memo[x][y] >= 0:
        return memo[x][y]
    else:
        if x == N or y == N:
            rst = abs(X - Y)
        else:
            if x <= y:
                rst = 0
                for i in range(y + 1, N + 1):
                    rst = max(rst, dfs(i, y))
            else:
                rst = 10 ** 10
                for i in range(x + 1, N + 1):
                    rst = min(rst, dfs(x, i))
        memo[x][y] = rst
        return rst


N, Z, W = map(int, input().split())
A = list(map(int, input().split()))
memo = [[-1] * (N + 1) for _ in range(N + 1)]
ans = dfs(0, 0)
print(ans)

Submission status: Time Limit Exceeded

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


def dfs(x, y):
    global N, Z, W
    X = Z if x == 0 else A[x - 1]
    Y = W if y == 0 else A[y - 1]

    if memo[x][y] >= 0:
        return memo[x][y]
    else:
        if x == N or y == N:
            rst = abs(X - Y)
        else:
            if x <= y:
                rst = 0
                for i in range(y + 1, N + 1):
                    rst = max(rst, dfs(i, y))
            else:
                rst = 10 ** 10
                for i in range(x + 1, N + 1):
                    rst = min(rst, dfs(x, i))
            return rst
        memo[x][y] = rst
        return rst


N, Z, W = map(int, input().split())
A = list(map(int, input().split()))
memo = [[-1] * (N + 1) for _ in range(N + 1)]
ans = dfs(0, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
N, Z, W = [int(x) for x in input().strip().split()]
a = [int(x) for x in input().strip().split()]
d = {}
def minmax(x, y, c, f):
    # print('x={}, y={}, c={}, f={}'.format(x, y, c, f))
    if (c, f) in d:
        return d[(c, f)]
    if c == N:
        return abs(x - y)
    if f == 0:
        ret = -float('inf')
        for i in range(1, N - c + 1):
            ret = max(ret, minmax(a[c+i-1], y, c+i, f^1))
    else:
        ret = float('inf')
        for i in range(1, N - c + 1):
            ret = min(ret, minmax(x, a[c+i-1], c+i, f^1))
    d[(c, f)] = ret
    return ret

print(minmax(Z, W, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
N, Z, W = [int(x) for x in input().strip().split()]
a = [int(x) for x in input().strip().split()]
d = {}
def minmax(x, y, c, f):
    # print('x={}, y={}, c={}, f={}'.format(x, y, c, f))
    if (x, y, c, f) in d:
        return d[(x, y, c, f)]
    if c == N:
        return abs(x - y)
    if f == 0:
        ret = -float('inf')
        for i in range(1, N - c + 1):
            ret = max(ret, minmax(a[c+i-1], y, c+i, f^1))
    else:
        ret = float('inf')
        for i in range(1, N - c + 1):
            ret = min(ret, minmax(x, a[c+i-1], c+i, f^1))
    d[(x, y, c, f)] = ret
    return ret

print(minmax(Z, W, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
 
N, Z, W = map(int, input().split())
A = list(map(int, input().split()))
inf = 10 ** 9 + 7
 
sys.setrecursionlimit(inf)
 
def calc(a, b):
  return abs(a - b)
 
def alphaBeta(X, Y, turn, depth, alpha, beta):
    if depth == N:
        return calc(X, Y)
    if turn:
        for i in range(depth, N):
            alpha = max(alpha, alphaBeta(A[i], Y, False, i+1, alpha, beta))
            if alpha >= beta:
                break
        return alpha
    else:
        for i in range(depth, N):
            beta = min(beta, alphaBeta(X, A[i], True, i+1, alpha, beta))
            if alpha >= beta:
                break
        return beta
 
print(alphaBeta(Z, W, True, 0, -1, inf))

Submission status: Time Limit Exceeded

Solution code:
import sys

N, Z, W = map(int, input().split())
A = list(map(int, input().split()))
inf = 10 ** 9 + 7

sys.setrecursionlimit(inf)

def calc(a, b):
  return abs(a - b)

def alphaBeta(X, Y, turn, depth, alpha, beta):
    if depth == N:
        return calc(X, Y)
    if turn:
        for i in range(depth, N):
            alpha = max(alpha, alphaBeta(A[i], Y, False, i+1, alpha, beta))
            if alpha >= beta:
                break
        return alpha
    else:
        for i in range(depth, N):
            beta = min(beta, alphaBeta(X, A[i], True, i+1, alpha, beta))
            if alpha >= beta:
                break
        return beta

print(alphaBeta(Z, W, True, 0, -1, inf))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def score(i,x,y,turn):
        if i==n-1:
            return abs(x-y)
        if (i,x,y,turn) in memo:
            return memo[(i,x,y,turn)]
        if turn:
            res=0
            for j in range(i+1,n):
                res=max(res,score(j,aa[j],y,not turn))
        else:
            res=10**16
            for j in range(i+1,n):
                res=min(res,score(j,x,aa[j],not turn))
        memo[(i,x,y,turn)]=res
        return res

    n,z,w=map(int, input().split())
    aa=list(map(int, input().split()))
    memo={}
    print(score(-1,z,w,True))

main()

Submission status: Time Limit Exceeded

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

cards = [y0] + list(map(int, input().split()))
# yの手持ちはゲームに関与するため、リストに加えてしまう

xs = [[-1] * (n+1) for i in range(n+1)]
ys = [[-1] * (n+1) for i in range(n+1)] 
#xs[i][j] = xの手番で、xがcards[i]を持ちyがcards[j]を持っているとき(i<j)の最善スコア
#ys[i][j] = yの手番で、xがcards[j]を持ちyがcards[i]を持っているとき(i<j)の最善スコア

for i in range(n+1):
	xs[i][-1] = abs(cards[-1] - cards[i])
	ys[i][-1] = abs(cards[-1] - cards[i])

for j in range(n-1, -1, -1):

	# x[i][j] = max (y[j][j+1] , y[j][j+2] , ……, y[j][n] )
	for i in range(0, j):
		xs[i][j] = max(ys[j][j+1:n+1])

	for i in range(0, j):
		ys[i][j] = min(xs[j][j+1:n+1])

# print(max(xs[0][0], abs(cards[-1] - x0)) )

# print(xs)
# print(ys)
print(max(ys[0][1:]))