Problem:


Score : 100 points

Problem Statement

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

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

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 3000

1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

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

Sample Input 1

4
10 80 90 30

Sample Output 1

10

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

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

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

Taro: (10, 80) → (10)

Jiro: (10) → ()

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

Sample Input 2

3
10 100 10

Sample Output 2

-80

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

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

Jiro: (100, 10) → (10)

Taro: (10) → ()

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

Sample Input 3

1
10

Sample Output 3

10

Sample Input 4

10
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1

Sample Output 4

4999999995

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

Sample Input 5

6
4 2 9 7 1 5

Sample Output 5

2

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

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

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

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

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

Taro: (2, 9) → (2)

Jiro: (2) → ()

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



Sample input:
4
10 80 90 30


Sample output:
10

Submission status: Time Limit Exceeded

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


# def print_list(lis):
#   for l in lis:
#     print(l)


# score[i][j][p] : Asのi番目を左端、j番目を右端とした時の最終スコア
#                  p = 0 が太郎君目線、p = 1 が次郎くん目線
score = [[[None for _ in range(2)] for _ in range(N)] for _ in range(N)]

for i in range(N):
  # 初期化
  # 区間長さ0であれば1通りしかない
  score[i][i][0] = As[i]
  score[i][i][1] = -As[i]

# print_list(score)

for k in range(1, N):
  # 配列の幅を広げながら計算を進める
  for i in range(N):
    # if k == 0:
    #   continue
    j = i + k
    if j >= N:
      # 幅をとりすぎたら中断
      continue
    if i == N - 1:
      score[i][j][0] = score[i][j-1][1] + As[j]
      score[i][j][1] = score[i][j-1][0] - As[j]
    else:
      # print(i,j)
      score[i][j][0] = max(score[i+1][j][1] + As[i], score[i][j-1][1] + As[j])
      score[i][j][1] = min(score[i+1][j][0] - As[i], score[i][j-1][0] - As[j])
    # print_list(score)

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

Submission status: Time Limit Exceeded

Solution code:
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 

def japonska_gierka(): 
    N = wczytaj_liste()[0]
    A = wczytaj_liste()
    X = 0
    Y = 0
    wynik = {}
    for dlugosc_kolejki in range(N+1):
        zabrano = N - dlugosc_kolejki
        for lewo in range(zabrano+1): 
            prawo = zabrano - lewo
            if dlugosc_kolejki == 0: 
                wynik[lewo,prawo] = 0 
            else:
                wynik[lewo,prawo] = max(A[lewo]-wynik[lewo+1, prawo], A[-prawo-1]-wynik[lewo,prawo+1])
    print(wynik[0,0])
    
japonska_gierka()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, a: "List[int]"):

    dp = [[0]*N for _ in range(N)]
    for sub in range(N):
        turn = sub % 2
        for i in range(N-sub):
            j = i+sub
            # i ~ jの数列に対して操作
            if i == j:
                if (N-sub+1) % 2 == 0:
                    dp[i][i] = a[i]
                else:
                    dp[i][i] = -a[i]
                continue

            if (N-sub+1) % 2 == 0:    # 先手番
                dp[i][j] = max(a[i] + dp[i+1][j], a[j]+dp[i][j-1])
            else:               # 後手番
                dp[i][j] = min(-a[i] + dp[i+1][j], -a[j]+dp[i][j-1])
    print(dp[0][N-1])
    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
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def rec(left, right, A, memo):
    if left + right == len(A):
        return 0
    if memo[left][right] is not None:
        return memo[left][right]
    if (left + right) % 2 == 0:
        ret = max(rec(left + 1, right, A, memo) + A[left],
                  rec(left, right + 1, A, memo) + A[len(A)-1-right])
    else:
        ret = min(rec(left + 1, right, A, memo) - A[left],
                  rec(left, right + 1, A, memo) - A[len(A)-1-right])
    memo[left][right] = ret
    return ret


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    memo = [[None] * N for _ in range(N)]
    print(rec(0, 0, A, memo))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def rec(left, right, A, memo):
    if left + right == len(A):
        return 0
    if memo[left][right] is not None:
        return memo[left][right]
    if (left + right) % 2 == 0:
        ret = max(rec(left + 1, right, A, memo) + A[left],
                  rec(left, right + 1, A, memo) + A[len(A)-1-right])
    else:
        ret = min(rec(left + 1, right, A, memo) - A[left],
                  rec(left, right + 1, A, memo) - A[len(A)-1-right])
    memo[left][right] = ret
    return ret


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    memo = [[None] * N for _ in range(N)]
    print(rec(0, 0, A, memo))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
n=int(input())
a=list(map(int,input().split()))
s=[[0 for i in range(n)]for j in range(n)]
b=[[0 for i in range(n)]for j in range(n)]
def f(x,y):
    if b[x][y]:
        return s[x][y]
    else:
        b[x][y]=1
        if x==y:
            s[x][y]=a[x]
            return s[x][y]
        else:
            s[x][y]=max(a[x]-f(x+1,y),a[y]-f(x,y-1))
            return s[x][y]
print(f(0,n-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
n=int(input())
a=list(map(int,input().split()))
s=[[0 for i in range(n)]for j in range(n)]
b=[[0 for i in range(n)]for j in range(n)]
def f(x,y):
    if b[x][y]:
        return s[x][y]
    else:
        b[x][y]=1
        if x==y:
            s[x][y]=a[x]
            return s[x][y]
        else:
            s[x][y]=max(a[x]-f(x+1,y),a[y]-f(x,y-1))
            return s[x][y]
print(f(0,n-1))

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**5)
def main():
    N = int( input())
    A = list( map( int, input().split()))
    dp = [[-1]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0

    def rec(l, r, N, A):
        if dp[l][r] >= 0:
            return dp[l][r]
        if (N-(r-l))%2 == 1:
            if rec(l+1,r,N,A) < rec(l, r-1,N,A):
                dp[l][r] = rec(l+1,r,N,A)
            else:
                dp[l][r] = rec(l, r-1,N,A)
        else:
            if rec(l+1, r,N,A)+A[l] > rec(l,r-1,N,A)+A[r-1]:
                dp[l][r] = rec(l+1, r,N,A)+A[l]
            else:
                dp[l][r] = rec(l,r-1,N,A)+A[r-1]
#        print(l, r,dp[l][r], dp)
        return dp[l][r]
    print(2*rec(0, N, N, A) - sum(A))
#    print(dp)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**5)
def main():
    N = int( input())
    A = list( map( int, input().split()))
    dp = [[-1]*(N+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][i] = 0

    def rec(l, r, N, A):
        if dp[l][r] >= 0:
            return dp[l][r]
        if (N-(r-l))%2 == 1:
            dp[l][r] = min(rec(l+1,r,N,A), rec(l, r-1,N,A))
        else:
            dp[l][r] = max(rec(l+1, r,N,A)+A[l], rec(l,r-1,N,A)+A[r-1])
#        print(l, r,dp[l][r], dp)
        return dp[l][r]
    print(2*rec(0, N, N, A) - sum(A))
#    print(dp)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def deque(n, arr):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = arr[i]

    for l in range(n-2, -1, -1):
        for r in range(l+1, n):
            dp[l][r] = max(arr[l] - dp[l+1][r], arr[r] - dp[l][r-1])
    return dp[0][n-1]

n = int(input())
arr = [int(x) for x in input().split()]
print(deque(n, arr))

Submission status: Time Limit Exceeded

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

n = int(input())
arr = [int(x) for x in input().split()]
dp = [[0] * n for _ in range(n)]

for i in range(n):
    dp[i][i] = arr[i]

for l in range(n-2, -1, -1):
    for r in range(l+1, n):
        dp[l][r] = max(arr[l] - dp[l+1][r], arr[r] - dp[l][r-1])
print(dp[0][n-1])

Submission status: Time Limit Exceeded

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

n = int(input())
arr = [int(x) for x in input().split()]
Max = 3005

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

for l in range(n-1,-1,-1):
    for r in range(l, n):
        if l == r:
            dp[l][r] = arr[l]
        else:
            dp[l][r] = max(arr[l] - dp[l+1][r], arr[r] - dp[l][r-1])

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

Submission status: Time Limit Exceeded

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

n = int(input())
arr = [int(x) for x in input().split()]
Max = 3005

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

for l in range(n-1,-1,-1):
    for r in range(l, n):
        if l == r:
            dp[l][r] = arr[l]
        else:
            dp[l][r] = max(arr[l] - dp[l+1][r], arr[r] - dp[l][r-1])

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

Submission status: Time Limit Exceeded

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

n = int(input())
arr = [int(x) for x in input().split()]
Max = 3005

dp = [[0 for i in range(Max)] for i in range(Max)]

for l in range(n-1,-1,-1):
    for r in range(l, n):
        if l == r:
            dp[l][r] = arr[l]
        else:
            dp[l][r] = max(arr[l] - dp[l+1][r], arr[r] - dp[l][r-1])

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = [int(x) for x in input().split()]
Max = 3005

dp = [[0 for i in range(Max)] for i in range(Max)]

for l in range(n-1,-1,-1):
    for r in range(l, n):
        if l == r:
            dp[l][r] = arr[l]
        else:
            dp[l][r] = max(arr[l] - dp[l+1][r], arr[r] - dp[l][r-1])

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[[0]*n for i in range(n)]
for i in range(n):
    if n%2==0:
        dp[i][i]=-a[i]
    else:
        dp[i][i]=a[i]
for l in range(1,n):
    if n%2==l%2:
        for right in range(l,n):
            left=right-l
            dp[left][right]=min(dp[left+1][right]-a[left],dp[left][right-1]-a[right])
    else:
        for right in range(l,n):
            left=right-l
            dp[left][right]=max(dp[left+1][right]+a[left],dp[left][right-1]+a[right])
print(dp[0][n-1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

dp = [[0]*N for _ in range(N)]
        
for k in range(N):
    for i in range(N-k):
        if k == 0:
            dp[i][i] = A[i]
            continue
    
        dp[i][i+k] = max(A[i]-dp[i+1][i+k], A[i+k]-dp[i][i+k-1])

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

Submission status: Time Limit Exceeded

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

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

dp = [["0"]*N for _ in range(N)]
        
def f(i, j):
    if i > j or i < 0 or i >= N or j < 0 or j >= N:
        return 0
    
    if i == j:
        dp[i][j] = A[i]
        return A[i]
        
    if dp[i][j] != "0":
        return dp[i][j]
    
    dp[i][j] = max(A[i]-f(i+1, j), A[j]-f(i, j-1))
    return dp[i][j]

ans = f(0, N-1)
print(ans)

Submission status: Time Limit Exceeded

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

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

dpmax = [["0"]*N for _ in range(N)]
dpmin = [["0"]*N for _ in range(N)]
        
def f(i, j, t):
    if i > j or i < 0 or i >= N or j < 0 or j >= N:
        return 0
    
    if i == j:
        if t == 0:
            dpmin[i][j] = -A[i]
            return -A[i]
        if t == 1:
            dpmax[i][j] = A[i]
            return A[i]
        
    if t == 0 and dpmin[i][j] != "0":
        return dpmin[i][j]
    elif t == 1 and dpmax[i][j] != "0":
        return dpmax[i][j]
    
    if t == 0:
        dpmin[i][j] = min(-A[i]+f(i+1, j, 1), -A[j]+f(i, j-1, 1))
        return dpmin[i][j]
    else:
        dpmax[i][j] = max(A[i]+f(i+1, j, 0), A[j]+f(i, j-1, 0))
        return dpmax[i][j]

ans = f(0, N-1, 1)
print(ans)

Submission status: Time Limit Exceeded

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

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

dpmax = [[0]*N for _ in range(N)]
dpmin = [[0]*N for _ in range(N)]
        
def f(i, j, t):
    if i > j or i < 0 or i >= N or j < 0 or j >= N:
        return 0
    
    if i == j:
        if t == 0:
            dpmin[i][j] = -A[i]
            return -A[i]
        if t == 1:
            dpmax[i][j] = A[i]
            return A[i]
        
    if t == 0 and dpmin[i][j] > 0:
        return dpmin[i][j]
    elif t == 1 and dpmax[i][j] > 0:
        return dpmax[i][j]
    
    if t == 0:
        dpmin[i][j] = min(-A[i]+f(i+1, j, 1), -A[j]+f(i, j-1, 1))
        return dpmin[i][j]
    else:
        dpmax[i][j] = max(A[i]+f(i+1, j, 0), A[j]+f(i, j-1, 0))
        return dpmax[i][j]

ans = f(0, N-1, 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = [int(c) for c in input().split()]

dp = [[-1] * N for _ in range(N)]
for i in range(N):
    for L in range(N):
        for R in range(L, N):
            if L == R:
                dp[L][R] = a[L]
            else:
                dp[L][R] = max(a[L] - dp[L+1][R], a[R] - dp[L][R-1])


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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().strip().split()]
dp = [[[None for k in range(2)] for j in range(n)] for i in range(n)]

def solve(a,i,j,t):
    if dp[i][j][t]:
        return dp[i][j][t]

    elif i==j:
        if t==1:
            d=1
        else:
            d=-1
        dp[i][j][t]= d*a[i]

    elif t==1:
        dp[i][j][t]= max(solve(a,i+1,j,0)+a[i], solve(a,i,j-1,0)+a[j])
        
    else:
        dp[i][j][t]= min(solve(a,i+1,j,1)-a[i], solve(a,i,j-1,1)-a[j])

    return dp[i][j][t]

print(solve(a,0,n-1,1))

Submission status: Time Limit Exceeded

Solution code:
def p_l():
    import sys
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    *a, = map(int, input().split())
    # dp[i][j]は区間[i,j]が残っているときの最大化
    dp = [[-1] * n for _ in range(n)]

    def dfs(l, r):
        if dp[l][r] != -1:
            return dp[l][r]
        if l == r:
            dp[l][r] = a[l]
            return a[l]
        dp[l][r] = max(a[l] - dfs(l + 1, r), a[r] - dfs(l, r - 1))
        return dp[l][r]

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

Submission status: Time Limit Exceeded

Solution code:
def p_l_2():
    n = int(input())
    *a, = map(int, input().split())
    # dp[i][j]は区間[i,j]が残っているときの最大化
    dp = [[-1] * n for _ in range(n)]

    for i in range(n):
        for l in range(n - i):
            r = l + i
            if l == r:
                dp[l][r] = a[l]
            else:
                dp[l][r] = max(a[l] - dp[l + 1][r], a[r] - dp[l][r - 1])
    print(dp[0][n - 1])


if __name__ == '__main__':
    p_l_2()

Submission status: Time Limit Exceeded

Solution code:
def p_l():
    import sys
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    *a, = map(int, input().split())
    # dp[i][j]は区間[i,j]が残っているときの最大化
    dp = [[-1] * n for _ in range(n)]

    def dfs(l, r):
        if dp[l][r] != -1:
            return dp[l][r]
        if l == r:
            dp[l][r] = a[l]
            return a[l]
        dp[l][r] = max(a[l] - dfs(l + 1, r), a[r] - dfs(l, r - 1))
        return dp[l][r]

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


if __name__ == '__main__':
    p_l()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    dp=[[None]*(n+1) for _ in range(n+1)]

    def dfs(l,r):
        if(dp[l][r] is not None): return
        if(l==r):
            dp[l][r]=0
            return

        # 1個先の値を確定させておく
        dfs(l+1,r)
        dfs(l,r-1)
        turn=(n-(r-l))%2
        if(turn==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])

    dfs(0,n)
    print(dp[0][n])
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    dp = [[0] * n for _ in range(n)]
    for i, a in enumerate(aa):
        dp[i][i] = a
    # p2D(dp)
    for d in range(1, n):
        for l in range(n - 1):
            r = l + d
            if r >= n: break
            s0 = aa[l] - dp[l + 1][r]
            s1 = aa[r] - dp[l][r - 1]
            dp[l][r] = s0 if s0 > s1 else s1
    # p2D(dp)
    print(dp[0][-1])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    dp = [[0] * n for _ in range(n)]
    for i, a in enumerate(aa):
        dp[i][i] = a
    # p2D(dp)
    for d in range(1, n):
        for l in range(n - 1):
            r = l + d
            if r >= n: break
            dp[l][r] = max(aa[l] - dp[l + 1][r], aa[r] - dp[l][r - 1])
    # p2D(dp)
    print(dp[0][-1])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    dp = [[0] * n for _ in range(n)]
    coff = 1 if n % 2 else -1
    for i, a in enumerate(aa):
        dp[i][i] = coff * a
    # p2D(dp)
    for d in range(1, n):
        coff *= -1
        for l in range(n - 1):
            r = l + d
            if r >= n: break
            if coff == 1:
                dp[l][r] = max(dp[l + 1][r] + aa[l], dp[l][r - 1] + aa[r])
            else:
                dp[l][r] = min(dp[l + 1][r] - aa[l], dp[l][r - 1] - aa[r])
    # p2D(dp)
    print(dp[0][-1])

main()

Submission status: Time Limit Exceeded

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

def main():
    l = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if i + j >= N:
                continue
            s = j
            e = j + i
            if len(a) % 2 != i % 2:
                if i == 0:
                    l[s][e] = a[s]
                elif i == 1:
                    l[s][e] = max(a[s:e+1]) - min(a[s:e+1])
                else:
                    l[s][e] = max(a[s] + l[s+1][e], a[e] + l[s][e-1])
            else:
                if i == 0:
                    l[s][e] -= a[s]
                elif i == 1:
                    l[s][e] = min(a[s:e+1]) - max(a[s:e+1])
                else:
                    l[s][e] = min(l[s+1][e] - a[s], l[s][e-1] - a[e])


    return l[0][-1]
print(main())

Submission status: Time Limit Exceeded

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


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


main()

Submission status: Time Limit Exceeded

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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    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]
        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: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=list(map(int,input().split()))
dp=[[ [0,0] for j in range(N)] for i in range(N)]
for i in reversed(range(N)):
    for j in range(i,N):
        if j>i:
            dp[i][j][0]=max(dp[i+1][j][1]+a[i],dp[i][j-1][1]+a[j])
            dp[i][j][1]=min(dp[i+1][j][0]-a[i],dp[i][j-1][0]-a[j])
        else:
            dp[i][j][0]+=a[i]
            dp[i][j][1]+=-a[i]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    dp=[[-1]*(n+1) for _ in range(n+1)]

    def dfs(l,r):
        if(l>=r): return 0
        if(dp[l][r]!=-1): return dp[l][r]
        turn=n-(r-l)
        if(turn%2==0):
            dp[l][r]=max(dfs(l+1,r)+A[l],dfs(l,r-1)+A[r-1])
        else:
            dp[l][r]=min(dfs(l+1,r)-A[l],dfs(l,r-1)-A[r-1])
        return dp[l][r]

    print(dfs(0,n))
resolve()

Submission status: Time Limit Exceeded

Solution code:

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

dp = [[0] * (N) for _ in range(N+1)]
ans = int(0)
for i in range(N):
    dp[i][i] = a[i]

#for l in range(1,N)
for l in range(1,N):
    for i in range(N-l):
        j = i + l
        dp[i][j] = max(dp[i][i]-dp[i+1][j], dp[j][j]-dp[i][j-1])


ans = dp[0][N-1]

print(ans)
#print(dp)

Submission status: Time Limit Exceeded

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

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        if (N - i) % 2 == 0:
            for l in range(N + 1 - i):
                r = l + i
                t0 = dp[l + 1][r] + a[l]
                t1 = dp[l][r - 1] + a[r - 1]
                if t0 > t1:
                    dp[l][r] = t0
                else:
                    dp[l][r] = t1
        else:
            for l in range(N + 1 - i):
                r = l + i
                t0 = dp[l + 1][r] - a[l]
                t1 = dp[l][r - 1] - a[r - 1]
                if t0 < t1:
                    dp[l][r] = t0
                else:
                    dp[l][r] = t1
    print(dp[0][N])
main()

Submission status: Time Limit Exceeded

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

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        p = (N - i) % 2
        if p == 0:
            for l in range(N + 1 - i):
                r = l + i
                t0 = dp[l + 1][r] + a[l]
                t1 = dp[l][r - 1] + a[r - 1]
                if t0 > t1:
                    dp[l][r] = t0
                else:
                    dp[l][r] = t1
        else:
            for l in range(N + 1 - i):
                r = l + i
                t0 = dp[l + 1][r] - a[l]
                t1 = dp[l][r - 1] - a[r - 1]
                if t0 < t1:
                    dp[l][r] = t0
                else:
                    dp[l][r] = t1
    print(dp[0][N])
main()

Submission status: Time Limit Exceeded

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

dp = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    p = (N - i) % 2
    if p == 0:
        for l in range(N + 1 - i):
            r = l + i
            t0 = dp[l + 1][r] + a[l]
            t1 = dp[l][r - 1] + a[r - 1]
            if t0 > t1:
                dp[l][r] = t0
            else:
                dp[l][r] = t1
    else:
        for l in range(N + 1 - i):
            r = l + i
            t0 = dp[l + 1][r] - a[l]
            t1 = dp[l][r - 1] - a[r - 1]
            if t0 < t1:
                dp[l][r] = t0
            else:
                dp[l][r] = t1
print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit


def f(u, l, r, a, dp):
    if l > r:
        return 0
    if dp[l][r] is not None:
        return dp[l][r]
    if u == 0:
        t0 = f(u ^ 1, l + 1, r, a, dp) + a[l]
        t1 = f(u ^ 1, l, r - 1, a, dp) + a[r]
        if t0 > t1:
            result = t0
        else:
            result = t1
    else:
        t0 = f(u ^ 1, l + 1, r, a, dp) - a[l]
        t1 = f(u ^ 1, l, r - 1, a, dp) - a[r]
        if t0 < t1:
            result = t0
        else:
            result = t1
    dp[l][r] = result
    return result


setrecursionlimit(1000000)

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

dp = [[None] * N for _ in range(N)]
print(f(0, 0, N - 1, a, dp))

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit


def f(u, l, r, a, dp):
    if l > r:
        return 0
    t = dp[l][r]
    if t is not None:
        return t
    if u == 0:
        t0 = f(u ^ 1, l + 1, r, a, dp) + a[l]
        t1 = f(u ^ 1, l, r - 1, a, dp) + a[r]
        if t0 > t1:
            result = t0
        else:
            result = t1
    else:
        t0 = f(u ^ 1, l + 1, r, a, dp) - a[l]
        t1 = f(u ^ 1, l, r - 1, a, dp) - a[r]
        if t0 < t1:
            result = t0
        else:
            result = t1
    dp[l][r] = result
    return result


setrecursionlimit(1000000)

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

dp = [[None] * N for _ in range(N)]
print(f(0, 0, N - 1, a, dp))

Submission status: Time Limit Exceeded

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

dp = [[0] * (N + 1) for _ in range(N + 1)]
for l in range(1, N + 1):
  for i in range(N + 1 - l):
    j = i + l
    if (N - l) % 2 == 0:
      dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
    else:
      dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])
print(dp[0][N])

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit


def f(u, l, r, a, dp):
    if l > r:
        return (0, 0)
    if dp[l][r] is not None:
        return dp[l][r]
    x, y = f(u ^ 1, l + 1, r, a, dp)
    if u == 0:
        t0 = (x + a[l], y)
    else:
        t0 = (x, y + a[l])
    x, y = f(u ^ 1, l, r - 1, a, dp)
    if u == 0:
        t1 = (x + a[r], y)
    else:
        t1 = (x, y + a[r])
    if t0[u] - t0[u ^ 1] > t1[u] - t1[u ^ 1]:
        result = t0
    else:
        result = t1
    dp[l][r] = result
    return result


setrecursionlimit(1000000)

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

dp = [[None] * N for _ in range(N)]
t = f(0, 0, N - 1, a, dp)
print(t[0] - t[1])

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit


def f(u, l, r, a, dp):
    if l > r:
        return (0, 0)
    if dp[l][r] is not None:
        return dp[l][r]
    t0 = None
    x, y = f(u ^ 1, l + 1, r, a, dp)
    if u == 0:
        t0 = (x + a[l], y)
    else:
        t0 = (x, y + a[l])
    t1 = None
    x, y = f(u ^ 1, l, r - 1, a, dp)
    if u == 0:
        t1 = (x + a[r], y)
    else:
        t1 = (x, y + a[r])
    if t0 is None:
        result = t1
    elif t1 is None:
        result = t0
    else:
        if t0[u] - t0[u ^ 1] > t1[u] - t1[u ^ 1]:
            result = t0
        else:
            result = t1
    dp[l][r] = result
    return result


setrecursionlimit(1000000)

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

dp = [[None] * N for _ in range(N)]
t = f(0, 0, N - 1, a, dp)
print(t[0] - t[1])

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

def f(u, l, r):
    if l > r:
        return (0, 0)
    if dp[l][r] is not None:
        return dp[l][r]
    t0 = None
    x, y = f(u ^ 1, l + 1, r)
    if u == 0:
        t0 = (x + a[l], y)
    else:
        t0 = (x, y + a[l])
    t1 = None
    x, y = f(u ^ 1, l, r - 1)
    if u == 0:
        t1 = (x + a[r], y)
    else:
        t1 = (x, y + a[r])
    if t0 is None:
        result = t1
    elif t1 is None:
        result = t0
    else:
        if t0[u] - t0[u ^ 1] > t1[u] - t1[u ^ 1]:
            result = t0
        else:
            result = t1
    dp[l][r] = result
    return result

setrecursionlimit(1000000)

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

dp = [[None] * N for _ in range(N)]
t = f(0, 0, N - 1)
print(t[0] - t[1])

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 = INT()
aN = LIST()

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

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

print(dfs(0, N-1))