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

Solution code:
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)
input = sys.stdin.readline

def dfs(i,j,p,z,w,a,n):
    if p == 0:
        if i == n:
            if j == 0:
                return abs(w - a[-1])
            return abs(a[j -1] - a[-1])
        ans = 0
        for k in range(i,n):
            ans = max(ans,dfs(k + 1,k,1,z,w,a,n))
        if i == 1:
            ans = max(ans,abs(a[-1] - w))
        else:
            ans = max(ans,abs(a[-1]- a[i - 1]))
        return ans
    elif p == 1:
        if i == n:
            if j == 0:
                return abs(z - a[-1])
            return abs(a[j - 1] - a[-1])
        ans = INF
        for k in range(i,n):
            ans = min(ans,dfs(k + 1,k,0,z,w,a,n))
        if i == 1:
            ans = min(ans,abs(a[-1] - z))
        else:
            ans = min(ans,abs(a[-1] - a[i - 1]))
        return ans

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

    ans = dfs(1,0,0,z,w,a,n)
    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

dp=[[[0 for i in range(0,2)] for j in range(0,N+2)] for k in range(0,N+1)]

for i in range(0,N+2):
    dp[N-1][i][0]=abs(A[N-1]-A[i])
    dp[N-1][i][1]=abs(A[N-1]-A[i])


for i in range(1,N):
    for j in range(0,N+2):
        I=N-1-i
        dp[I][j][0]=max(dp[I+1][I][1],dp[I+1][j][0],abs(A[N-1]-A[j]))
        dp[I][j][1]=min(dp[I+1][I][0],dp[I+1][j][1],abs(A[N-1]-A[j]))

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

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, Z, W = MAP()
A = [W] + LIST()

memo = list3d(N+1, N+1, 2, -1)
def rec(cur, prev, turn):
    if cur == N:
        return abs(A[cur] - A[prev])
    if memo[cur][prev][turn] != -1:
        return memo[cur][prev][turn]
    
    if turn == 0:
        res = 0
        for nxt in range(cur+1, N+1):
            res = max(res, rec(nxt, cur, 1 - turn))
    else:
        res = INF
        for nxt in range(cur+1, N+1):
            res = min(res, rec(nxt, cur, 1 - turn))
    memo[cur][prev][turn] = res
    return res
print(rec(0, -1, 0))

Submission status: Time Limit Exceeded

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

N, Z, W = list(map(int, input().split()))
A = [W] + list(map(int, input().split()))

S = set(A)
GX = {s:[None]*N + [abs(A[N]-s)] for s in S}
GY = {s:[None]*N + [abs(A[N]-s)] for s in S}
minGX = {s:10**10 for s in S}
maxGY = {s:0      for s in S}

for k in range(N-1, -1, -1):
    ak = A[k]
    gx = max(GY[ak][k+1], maxGY[ak])
    gy = min(GX[ak][k+1], minGX[ak])
    for s in S:
        GX[s][k] = gx
        GY[s][k] = gy

    for s in S:
        maxGY[s] = max(GY[s][k+1], maxGY[s])
        minGX[s] = min(GX[s][k+1], minGX[s])

print(GX[W][0])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)

def maxValue(z:int, w:int, a:"List[int]", player:str) -> int:
    if not a:
        return abs(z-w)

    if player == "X": ## playerXが操作する。価値がmaxになるように
        value = 0
        for i in range(len(a)):
            value = max(maxValue(a[i],w,a[i+1:],"Y"),value)
    else: ## yが操作,価値がminになるように
        value = 10**9
        for i in range(len(a)):
            value = min(maxValue(z,a[i],a[i+1:],"X"),value)
    return value        

def solve(N: int, Z: int, W: int, a: "List[int]"):
    print(maxValue(Z,W,a,"X"))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Z = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, Z, W, a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, Z, W = list(map(int, input().split()))
A = [W] + list(map(int, input().split()))

S = set(A)
GX = {s:[None]*N + [abs(A[N]-s)] for s in S}
GY = {s:[None]*N + [abs(A[N]-s)] for s in S}
minGX = {s:10**10 for s in S}
maxGY = {s:0      for s in S}

#for s in S:
#    GX[s][N-1] = GY[A[N-1]][N]
#    GY[s][N-1] = GX[A[N-1]][N]

for k in range(N-1, -1, -1):
    ak = A[k]
    gx = max(GY[ak][k+1], maxGY[ak])
    gy = min(GX[ak][k+1], minGX[ak])
    for s in S:
        GX[s][k] = gx
        GY[s][k] = gy

    for s in S:
        maxGY[s] = max(GY[s][k+1], maxGY[s])
        minGX[s] = min(GX[s][k+1], minGX[s])

print(GX[W][0])

Submission status: Time Limit Exceeded

Solution code:
N, Z, W = list(map(int, input().split()))
A = [W] + list(map(int, input().split()))

S = set(A)
GX = {s:[None]*N + [abs(A[N]-s)] for s in S}
GY = {s:[None]*N + [abs(A[N]-s)] for s in S}
minGX = {s:10**10 for s in S}
maxGY = {s:0      for s in S}

#for s in S:
#    GX[s][N-1] = GY[A[N-1]][N]
#    GY[s][N-1] = GX[A[N-1]][N]

for k in range(N-1, -1, -1):
    ak = A[k]
    for s in S:
        GX[s][k] = max(GY[ak][k+1], maxGY[ak])
        GY[s][k] = min(GX[ak][k+1], minGX[ak])

    for s in S:
        maxGY[s] = max(GY[s][k+1], maxGY[s])
        minGX[s] = min(GX[s][k+1], minGX[s])

print(GX[W][0])

Submission status: Time Limit Exceeded

Solution code:
N, Z, W = list(map(int, input().split()))
A = [W] + list(map(int, input().split()))

S = set(A)
GX = {s:[None]*N + [abs(A[N]-s)] for s in S}
GY = {s:[None]*N + [abs(A[N]-s)] for s in S}
minGX = {s:10**10 for s in S}
maxGY = {s:0      for s in S}

for k in range(N-1, -1, -1):
    for s in S:
        GX[s][k] = max(GY[A[k]][k+1], maxGY[A[k]])
        GY[s][k] = min(GX[A[k]][k+1], minGX[A[k]])

    for s in S:
        maxGY[s] = max(GY[s][k+1], maxGY[s])
        minGX[s] = min(GX[s][k+1], minGX[s])

print(GX[W][0])

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

N, Z, W = map(int, input().split())
A = [int(a) for a in input().split()]

@lru_cache(maxsize=None)
def X(i, y):
    return max([Y(j+1, A[j]) for j in range(i, N-1)] + [abs(A[N-1] - y)])

@lru_cache(maxsize=None)
def Y(i, x):
    return min([X(j+1, A[j]) for j in range(i, N-1)] + [abs(A[N-1] - x)])

print(X(0, W))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000000)

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

memo={}
def func(n,last,turn):  #n:カードの残り枚数、last:前の手番が最後に引いたスコア、turn: 0先手の番 1後手の番
    #print "func(",n,",",last,",",turn,")"
    if (n,last,turn) in memo:
        return memo[(n,turn)]
    if n==1:
        ret=abs(last-A[N-n])
    elif turn==0:
        ret=max( func(n-1,last,0) , func(n-1,A[N-n],1) ) #手番がXのまま  手番がYに移動
    elif turn==1:
        ret=min( func(n-1,last,1) , func(n-1,A[N-n],0) ) #手番がYのまま  手番がXに移動
    memo[(n,turn)]=ret
    return ret


print func(N,Y,0)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000000)

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

memo={}
def func(n,last,turn):  #n:カードの残り枚数、last:前の手番が最後に引いたスコア、turn: 0先手の番 1後手の番
    #print "func(",n,",",last,",",turn,")"
    if (n,last,turn) in memo:
        return memo[(n,last,turn)]
    if n==1:
        ret=abs(last-A[N-n])
    elif turn==0:
        ret=max( func(n-1,last,0) , func(n-1,A[N-n],1) ) #手番がXのまま  手番がYに移動
    elif turn==1:
        ret=min( func(n-1,last,1) , func(n-1,A[N-n],0) ) #手番がYのまま  手番がXに移動
    memo[(n,last,turn)]=ret
    return ret


print func(N,Y,0)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000000)

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

memo={}
def func(n,last,turn):  #n:カードの残り枚数、last:前の手番が最後に引いたスコア、turn: 0先手の番 1後手の番
    #print "func(",n,",",last,",",turn,")"
    if (n,last,turn) in memo:
        return memo[(n,last,turn)]
    if n==1:
        ret=abs(last-A[N-n])
    elif turn==0:
        ret=max( func(n-1,last,0) , func(n-1,A[N-n],1) ) #手番がXのまま  手番がYに移動
    elif turn==1:
        ret=min ( func(n-1,last,1) , func(n-1,A[N-n],0) ) #手番がYのまま  手番がXに移動
    memo[(n,last,turn)]=ret
    return ret


print func(N,Y,0)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000000)

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

def func(n,last,turn):  #n:カードの残り枚数、last:前の手番が最後に引いたスコア、turn: 0先手の番 1後手の番
    #print "func(",n,",",last,",",turn,")"
    if n==1:
        return abs(last-A[N-n])
    elif turn==0:
        return max( func(n-1,last,0) , func(n-1,A[N-n],1) ) #手番がXのまま  手番がYに移動
    elif turn==1:
        return min ( func(n-1,last,1) , func(n-1,A[N-n],0) ) #手番がYのまま  手番がXに移動


print func(N,Y,0)

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, _, W = MAP()
A = [W] + LIST()

# memo[i][j] := 先手が最後にi枚目、後手が最後にj枚目を取った状態
memo = list2d(N+1, N+1, None)
def rec(a, b):
    if memo[a][b] is not None:
        return memo[a][b]
    # 終了条件(どちらかが最後まで札を取った)
    if a == N or b == N:
        res = abs(A[a]-A[b])
        memo[a][b] = res
        return res
    nxt = max(a, b)
    turn = 0 if a < b else 1
    if turn % 2 == 0:
        res = -INF
        for i in range(nxt+1, N+1):
            res = max(res, rec(i, b))
    else:
        res = INF
        for i in range(nxt+1, N+1):
            res = min(res, rec(a, i))
    memo[a][b] = res
    return res

ans = rec(-1, 0)
print(ans)

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, _, W = MAP()
A = [W] + LIST()

# memo[i][j] := 先手が最後にi枚目、後手が最後にj枚目を取った状態
memo = list2d(N+1, N+1, -INF)
def rec(a, b):
    if memo[a][b] != -INF:
        return memo[a][b]
    # 終了条件(どちらかが最後まで札を取った)
    if a == N or b == N:
        res = abs(A[a]-A[b])
        memo[a][b] = res
        return res
    nxt = max(a, b)
    turn = 0 if a < b else 1
    if turn % 2 == 0:
        res = -INF
        for i in range(nxt+1, N+1):
            res = max(res, rec(i, b))
    else:
        res = INF
        for i in range(nxt+1, N+1):
            res = min(res, rec(a, i))
    memo[a][b] = res
    return res

ans = rec(-1, 0)
print(ans)

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, _, W = MAP()
A = [W] + LIST()

# memo[i][j][k] := iのターンで先手が最後にj枚目、後手が最後にk枚目を取った状態
memo = list3d(2, N+1, N+1, -INF)
def rec(turn, a, b):
    if memo[turn][a][b] != -INF:
        return memo[turn][a][b]
    # 終了条件(どちらかが最後まで札を取った)
    if a == N or b == N:
        res = abs(A[a]-A[b])
        memo[turn][a][b] = res
        return res
    nxt = max(a, b)
    if turn % 2 == 0:
        res = -INF
        for i in range(nxt+1, N+1):
            res = max(res, rec(1-turn, i, b))
    else:
        res = INF
        for i in range(nxt+1, N+1):
            res = min(res, rec(1-turn, a, i))
    memo[turn][a][b] = res
    return res

ans = rec(0, 0, 0)
print(ans)

Submission status: Time Limit Exceeded

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,z,w = LI()
a = LI()
que = deque(a)
tmp1 = que.popleft()
tmp2 = w
turn = 0
cnt = 0
while que:
    if turn == 0:
        if tmp1 <= que[0]:
            tmp1 = que.popleft()
        else:
            turn = 1
    else:
        if tmp2 >= que[0]:
            tmp2 = que.popleft()
        else:
            turn = 0
    cnt += 1
    if cnt > n:
        print(abs(tmp1 - tmp2))
print(abs(tmp1-tmp2))

Submission status: Time Limit Exceeded

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,z,w = LI()
a = LI()
que = deque(a)
tmp1 = que.popleft()
tmp2 = w
turn = 0
while que:
    if turn == 0:
        if tmp1 <= que[0]:
            tmp1 = que.popleft()
        else:
            turn = 1
    else:
        if tmp2 >= que[0]:
            tmp2 = que.popleft()
        else:
            turn = 0
print(abs(tmp1-tmp2))

Submission status: Time Limit Exceeded

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

N, Z, W = map(int, input().split())
a = list(map(int, input().split()))
a.reverse()
a += [W] #最後にYさんの手札を加えておく
dp_T = [-1] * (N + 1) #Xの手番
dp_F = [-1] * (N + 1) #Yの手番

def calc(n, flag): #n: 残りの山の枚数　flag: ターンの管理
    #既に計算済みの場合その値を返す
    # if flag == True and dp_T[n] != -1:
    #     return dp_T[n]
    # if flag == False and dp_F[n] != -1:
    #     return dp_F[n]

    if n == 1: #山の残り枚数が1枚の時 -->引くしかなく得点が決定
        return abs(a[0] - a[n])
    if flag == True: #Xのターン-->大きくしたい
        tmp = 0
        for i in range(1, n + 1): #自分が引く枚数 = 1 ~ n枚
            if i == n: #残り枚数0で相手に渡す = 自分が最後の1枚を引く -->相手の手札が決まっているから得点が決定
                tmp = max(tmp, abs(a[0]-a[n]))
            else: #残り枚数が1枚以上ある時、手番は相手に変える
                tmp = max(tmp, calc(n-i, not flag))
        dp_T[n] = tmp
        return tmp
    if flag == False: #Yのターン-->小さくしたい
        tmp = 10 ** 10 #最大値
        for i in range(1, n + 1): #自分が引く枚数 = 1 ~ n枚
            if i == n - 1: #残り0枚で相手に渡す
                tmp = min(tmp, abs(a[0] - a[n]))
            else:
                tmp = min(tmp, calc(n-i, not flag))
        dp_F[n] = tmp
        return tmp

print (calc(N, True))

Submission status: Time Limit Exceeded

Solution code:
import functools
import os
import sys
from functools import lru_cache


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        ret = fn(*args, **kwargs)
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        print(ret)
        return ret

    return wrapper


sys.setrecursionlimit(10000)
INF = float('inf')

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


# def xy(x, y, pos, x_turn):
#     if x_turn:
#         return A[pos], y
#     else:
#         return x, A[pos]
#
#
# @debug
# def solve(x, y, pos, x_turn):
#     if pos >= N:
#         return abs(x - y)
#
#     if x_turn:
#         ans = -INF
#         for i in range(pos, N):
#             x, y = xy(x, y, i, x_turn)
#             ans = max(ans, solve(x, y, i + 1, not x_turn))
#     else:
#         ans = INF
#         for i in range(pos, N):
#             x, y = xy(x, y, i, x_turn)
#             ans = min(ans, solve(x, y, i + 1, not x_turn))
#     return ans
#
# print(solve(Z, W, 0, True))


@lru_cache(maxsize=None)
def dpx(i):
    """
    i 番目から x が最善を尽くしたときのスコア
    :param i: 
    :return: 
    """
    if i == 0:
        y = W
    else:
        y = A[i - 1]

    ret = abs(A[-1] - y)
    for i in range(i + 1, N):
        ret = max(ret, dpy(i))
    return ret


@lru_cache(maxsize=None)
def dpy(i):
    """
    i 番目から y が最善を尽くしたときのスコア
    :param i: 
    :return: 
    """
    if i == 0:
        x = Z
    else:
        x = A[i - 1]

    ret = abs(A[-1] - x)
    for i in range(i + 1, N):
        ret = min(ret, dpx(i))
    return ret


print(dpx(0))

Submission status: Time Limit Exceeded

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

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

cache = {}

def f(idx, turn, x, y):
    if idx == n:
        return abs(x - y)
    
    key = (idx, turn)
    if key in cache:
        return cache[key]

    if turn == 0:
        ans = -float('inf')
        for i in range(idx, n):
            ans = max(ans, f(i + 1, 1 - turn, a[i], y))
    else:
        ans = float('inf')
        for i in range(idx, n):
            ans = min(ans, f(i + 1, 1 - turn, x, a[i]))

    cache[key] = ans
    return cache[key]

print(f(0, 0, z, w))

Submission status: Time Limit Exceeded

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

"""
参考：https://kimiyuki.net/writeup/algo/atcoder/arc-085-d/
・ミニマックス法
・メモ化再帰
・先手と後手にそれぞれのメモを作る
"""

import sys
from collections import defaultdict

# 再帰呼び出しの回数制限(デフォルト1000)
sys.setrecursionlimit(10 ** 9)
 
N, Z, W = map(int, input().split())
aN = list(map(int, input().split()))

# 先手番用メモ[残り山札数][相手のスコア] = このルートでのmax
# 後手番用メモ[残り山札数][相手のスコア] = このルートでのmin
memo1 = [defaultdict(int) for _ in range(N+1)]
memo2 = [defaultdict(int) for _ in range(N+1)]

def dfs(turn, rest, x, y):
    if rest == 0:
        return abs(x - y)
    # 先手番
    if turn % 2 == 0:
        # 既に見た局面ならメモの内容を返す
        if memo1[rest][y]: 
            return memo1[rest][y]
        mx = -1
        for i in range(N-rest, N):
            x = aN[i]
            idx = i+1
            mx = max(dfs(turn+1, N-idx, x, y), mx)
        # ここより深い所を探し終わったので結果をメモする
        memo1[rest][y] = mx
        return mx
    # 後手番
    else:
        if memo2[rest][x]: 
            return memo2[rest][x]
        mn = float('inf')
        for i in range(N-rest, N):
            y = aN[i]
            idx = i+1
            mn = min(dfs(turn+1, N-idx, x, y), mn)
        memo2[rest][x] = mn
        return mn

print(dfs(0, N, Z, W))

Submission status: Time Limit Exceeded

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

import sys

# 再帰呼び出しの回数制限(デフォルト1000)
sys.setrecursionlimit(10 ** 9)
 
N, Z, W = map(int, input().split())
aN = list(map(int, input().split()))

def dfs(turn, rest, x, y):
    if rest == 0:
        return abs(x - y)
    if turn % 2 == 0:
        mx = -1
        for i in range(N-rest, N):
            x = aN[i]
            idx = i+1
            mx = max(dfs(turn+1, N-idx, x, y), mx)
        return mx
    else:
        mn = float('inf')
        for i in range(N-rest, N):
            y = aN[i]
            idx = i+1
            mn = min(dfs(turn+1, N-idx, x, y), mn)
        return mn

print(dfs(0, N, Z, W))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(114514)

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

memo = {}
def act(xlast, ylast, turn):
    x = z if xlast == -1 else aa[xlast]
    y = w if ylast == -1 else aa[ylast]

    if xlast == n - 1 or ylast == n - 1:
        return abs(x - y)
    
    if (xlast, ylast, turn) in memo:
        return memo[(xlast, ylast, turn)]
    
    if turn == 0:
        # x turn
        ans = 0
        for i in range(ylast + 1, n):
            ans = max(ans, act(i, ylast, 1))
    else:
        # y turn
        ans = 1 << 30
        for i in range(xlast + 1, n):
            ans = min(ans, act(xlast, i, 0))
    
    memo[(xlast, ylast, turn)] = ans
    return ans

print(act(-1, -1, 0))

Submission status: Time Limit Exceeded

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

a = []
memo = []


def dfs(no, i):
    global memo, a
    if memo[no][i]:
        return memo[no][i]

    ans = abs(a[-1] - a[i])
    for j in range(i + 1, len(a) - 1):
        nex = dfs(1 - no, j + 1)
        # X
        if no == 0:
            ans = max(ans, nex)
        # Y
        else:
            ans = min(ans, nex)

    memo[no][i] = ans
    return ans


def solve2(N, Z, W):
    global a, memo
    a = [Z, W] + a
    memo = [[None] * len(a) for _ in range(2)]
    return dfs(0, 1)


def solve(N, Z, W):
    global a
    ans = abs(a[-1] - W)
    if len(a) > 1:
        ans = max(ans, abs(a[-2] - a[-1]))
    return ans


def main():
    global a
    N, Z, W = map(int, input().split())
    a = list(map(int, input().split()))
    print(solve2(N, Z, W))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

a = []
@lru_cache(None)
def dfs(no, i, Z, W):
    global a
    if i >= len(a):
        return abs(Z - W)

    # X
    if no % 2 == 0:
        ans = 0
        for j in range(i, len(a)):
            ans = max(ans, dfs(1 - no, j + 1, a[j], W))
        return ans
    # Y
    else:
        ans = INF
        for j in range(i, len(a)):
            ans = min(ans, dfs(1 - no, j + 1, Z, a[j]))
        return ans


def solve2(N, Z, W):
    return dfs(0, 0, Z, W)


def solve(N, Z, W):
    global a
    ans = abs(a[-1] - W)
    if len(a) > 1:
        ans = max(ans, abs(a[-2] - a[-1]))
    return ans


def main():
    global a
    N, Z, W = map(int, input().split())
    a = list(map(int, input().split()))
    print(solve2(N, Z, W))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ma = max( abs(a[n-2]-a[n-1]) , abs(a[n-1]-w) )
print(ma)

Submission status: Accepted

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

if N == 1:
  print(abs(A[-1] - W))
else:
  print(max(abs(A[-1] - W), abs(A[-2] - A[-1])))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, Z, W = in_nn()
    A = in_nl()

    if N == 1:
        ans = abs(W - A[0])
    else:
        ans = max(abs(A[-1] - A[-2]), abs(A[-1] - W))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

print(max(abs(A[N-1] - W), abs(A[N-2] - A[N-1])))

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,Z,W = LI()
    a = LI()

    s = abs(W - a[-1])
    if N == 1:
        print(s)
        return

    u = [0] * N
    d = [0] * N

    u[-2] = d[-2] = min_u = max_d = abs(a[-1] - a[-2])
    for i in range(N-3,-1,-1):
        u[i] = max(max_d,abs(a[i]-a[-1]))
        d[i] = min(min_u,abs(a[i]-a[-1]))
        min_u = min(min_u,u[i])
        max_d = max(max_d,d[i])

    print(max(s,max_d))
if __name__ == '__main__':
    main()

Submission status: Accepted

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

# 初手で全部引く abs(a_N - W) or 1枚残す abs(a_N-1 - a_N) が最適
# 2枚以上残した場合、Yが1枚残すことで abs(a_N-1 - a_N)　とすることが可能で、
# abs(a_N-1 - a_N) より良くすることは出来ない

# 1枚しかない時に注意

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

ans = max(
  abs(A[-2] - A[-1]) if len(A) > 1 else 0,
  abs(A[-1] - w)
)

print(ans)

Submission status: Accepted

Solution code:
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[-1]-w),abs(a[-1]-a[-2])))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, z, w = map(int, input().split())
    A = list(map(int, input().split()))

    res = abs(w - A[-1])
    if n > 1:
        res = max(res, abs(A[-2] - A[-1]))
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import numpy as np

def solve(N, Z, W, A):
    # dp_x[n] := y さんが n 枚目を引いて x さんに手番が回ったときの最大値
    dp_x = np.full(N+1, 1<<61, dtype=np.int64)
    dp_y = np.zeros(N+1, dtype=np.int64)
    for i in range(N-1, 0, -1):
        dp_x[i] = max(dp_y[i+1:].max(), abs(A[-1]-A[i-1]))
        dp_y[i] = min(dp_x[i+1:].min(), abs(A[-1]-A[i-1]))
    ans = max(abs(A[-1]-W), dp_y[1:].max())
    return ans

N, Z, W = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
ans = solve(N, Z, W, A)
print(ans)

Submission status: Accepted

Solution code:
N, Z, W = (int(x) for x in input().split())
A = [int(x) for x in input().split()]

ans = max(abs(A[N-2]-A[N-1]), abs(A[N-1]-W))
print(ans)

Submission status: Accepted

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

N, Z, W = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0]*(2) for _ in range(N)]

for i in range(N-1, -1, -1):
    if i==0:
        dp[i][0] = abs(a[N-1]-W)
    else:
        dp[i][0] = abs(a[N-1]-a[i-1])
    
    for j in range(i+1, N):
        dp[i][0] = max(dp[i][0], dp[j][1])
    
    if i==0:
        dp[i][1] = abs(a[N-1]-Z)
    else:
        dp[i][1] = abs(a[N-1]-a[i-1])
    
    for j in range(i+1, N):
        dp[i][1] = min(dp[i][1], dp[j][0])

print(dp[0][0])

Submission status: Accepted

Solution code:
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[-1]-a[-2]),abs(a[-1]-w)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

max_score = abs(As[-1] - W)
if N >= 2 and max_score < abs(As[-2] - As[-1]):
    max_score = abs(As[-2] - As[-1])

print(max_score)