Submission #3973573

Source Code Expand

N = int(input())
*A, = map(int, input().split())
dp = [[-1]*(N+1-i) for i in range(N+1)]
for i in range(N+1):
    dp[0][i] = 0
t = (N & 1)
for l in range(1, N+1):
    S = dp[l-1]; T = dp[l]
    t ^= 1
    if t:
        T[:] = (min(S[i+1] - A[i], S[i] - A[i+l-1]) for i in range(N-l+1))
    else:
        T[:] = (max(S[i+1] + A[i], S[i] + A[i+l-1]) for i in range(N-l+1))
print(dp[N][0])

Submission Info

Submission Time
Task L - Deque
User yaketake08
Language PyPy3 (2.4.0)
Score 100
Code Size 399 Byte
Status AC
Exec Time 473 ms
Memory 85852 KiB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 19
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 0_04, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13
Case Name Status Exec Time Memory
0_00 AC 171 ms 38256 KiB
0_01 AC 173 ms 38256 KiB
0_02 AC 169 ms 38384 KiB
0_03 AC 171 ms 38256 KiB
0_04 AC 166 ms 38256 KiB
1_00 AC 167 ms 38256 KiB
1_01 AC 167 ms 38256 KiB
1_02 AC 464 ms 85852 KiB
1_03 AC 409 ms 81500 KiB
1_04 AC 434 ms 82012 KiB
1_05 AC 435 ms 82012 KiB
1_06 AC 463 ms 83292 KiB
1_07 AC 473 ms 83036 KiB
1_08 AC 462 ms 82780 KiB
1_09 AC 465 ms 83036 KiB
1_10 AC 458 ms 82780 KiB
1_11 AC 461 ms 83036 KiB
1_12 AC 458 ms 82908 KiB
1_13 AC 458 ms 82652 KiB