Problem:


Score : 600 points

Problem Statement

Given is an integer sequence A_1, ..., A_N of length N.

We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.

Find the maximum possible sum of the chosen elements.

Here \lfloor x \rfloor denotes the greatest integer not greater than x.

Constraints

2 \leq N \leq 2\times 10^5

|A_i|\leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the maximum possible sum of the chosen elements.

Sample Input 1

6
1 2 3 4 5 6

Sample Output 1

12

Choosing 2, 4, and 6 makes the sum 12, which is the maximum possible value.

Sample Input 2

5
-1000 -100 -10 0 10

Sample Output 2

0

Choosing -10 and 10 makes the sum 0, which is the maximum possible value.

Sample Input 3

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5000000000

Watch out for overflow.

Sample Input 4

27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49

Sample Output 4

295



Sample input:
6
1 2 3 4 5 6


Sample output:
12

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(map(int,input().split()))
import numpy as np
get_DP  = [[-np.inf for i in range(3)] for j in range(N)]
pass_DP = [[-np.inf for i in range(3)] for j in range(N)]
for i in range(N):
    # 常にとるやつ
    get_DP[i][0] = (pass_DP[i-1][0] if i>0 else 0) + S[i] 
    pass_DP[i][0] = get_DP[i-1][0]
    if i>0:
        get_DP[i][1] = (pass_DP[i-1][1] if i!=1 else 0) + S[i]
        pass_DP[i][1] = max(pass_DP[i-1][0], get_DP[i-1][1])
    if i>1:
        get_DP[i][2] = (pass_DP[i-1][2] if i!=2 else 0) + S[i]
        pass_DP[i][2] = max(pass_DP[i-1][1], get_DP[i-1][2])

    
print(max(get_DP[-1]))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N % 2 == 0:
        return max(sum(A[::2]), sum(A[1::2]))
    dp = [[0] * 3 for _ in range(N)]
    l = [[0] * 3 for _ in range(N)]
    r1 = sum(A[::2])
    r2 = sum(A[1::2])
    r3 = sum(A[2::2])
    os = [0] * N
    es = [0] * N
    for i, v in enumerate(A):
        if i % 2 == 0:
            os[i] = os[i-2] + v
        else:
            es[i] = es[i-2] + v
    for i in range(N):
        s = es[i] + r1 - os[i-1]
        r2 = max(s, r2)
    r0 = -1 * N * pow(10, 10)
    for i in range(N):
        if i % 2 == 0:
            s = r1 - A[i]
            r0 = max(r0,s)
    dp = [[-1 * N * pow(10,10)] * 3 for _ in range(N)]
    dp[0][0] = A[0]
    for i, v in enumerate(A):
        if i < 2:
            continue
        dp[i][0] = dp[i-2][0] + v
        if i < 3:
            continue
        dp[i][1] = max(dp[i-3][0] + v, dp[i-2][1] + v)
        if i < 4:
            continue
        dp[i][2] = max(dp[i-4][0] + v, dp[i-3][1] + v, dp[i-2][2] + v)
    return max(r2, r3, r0, dp[-1][2], dp[-2][1])
print(main())

Submission status: Wrong Answer

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

if n % 2 == 0:
  print(max(sum(a[::2]), sum(a[1::2])))
else:
  dp = a[:3]
  for i in range(1, n // 2):
    dp = [dp[0] + a[2*i], max(dp[:2]) + a[2*i+1], max(dp) + a[2*i+2]]
  print(max(dp))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N % 2 == 0:
        return max(sum(A[::2]), sum(A[1::2]))
    dp = [[0] * 3 for _ in range(N)]
    l = [[0] * 3 for _ in range(N)]
    r1 = sum(A[::2])
    r2 = sum(A[1::2])
    r3 = sum(A[2::2])
    os = [0] * N
    es = [0] * N
    for i, v in enumerate(A):
        if i % 2 == 0:
            os[i] = os[i-2] + v
        else:
            es[i] = es[i-2] + v
    for i in range(N):
        s = es[i] + r1 - os[i-1]
        r2 = max(s, r2)
    r0 = -1 * N * pow(10, 10)
    for i in range(N):
        s = r1 - A[i]
        r0 = max(r0,s)
    dp = [[-1 * N * pow(10,10)] * 3 for _ in range(N)]
    dp[0][0] = A[0]
    for i, v in enumerate(A):
        if i < 2:
            continue
        dp[i][0] = dp[i-2][0] + v
        if i < 3:
            continue
        dp[i][1] = max(dp[i-3][0] + v, dp[i-2][1] + v)
        if i < 4:
            continue
        dp[i][2] = max(dp[i-4][0] + v, dp[i-3][1] + v, dp[i-2][2] + v)
    return max(r2, r3, r0, dp[-1][2], dp[-2][1])
print(main())

Submission status: Wrong Answer

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

if N%2==0:
    INF = 2* 10**9
    dp = [[-INF]*N for _ in [0]*2]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    for i in range(2,N,2):
        a = A[i]
        dp[0][i] = dp[0][i-2] + a
    for i in range(3,N):
        dp[1][i] = max(dp[1][i-2],dp[0][i-3]) + a
    print(max(dp[1][-1],dp[0][-2]))
else:
    INF = 2* 10**9
    dp = [[-INF]*N for _ in [0]*3]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for i in range(2,N,2):
        a = A[i]
        dp[0][i] = dp[0][i-2] + a
    for i in range(3,N):
        a = A[i]
        dp[1][i] = max(dp[1][i-2],dp[0][i-3]) + a
    for i in range(4,N,2):
        a = A[i]
        dp[2][i] = max(dp[2][i-2],dp[1][i-3],dp[0][i-4]) + a
    print(max(dp[2][-1],dp[1][-2],dp[0][-3]))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N==2:
    print(max(A))
elif N==3:
    print(max(A))
else:
    if N%2==1:
        dp=[[0 for i in range(0,3)] for i in range(0,N)]
        dp[0][2]=A[0]
        dp[0][1]=-float('inf')
        dp[0][0]=-float('inf')
        dp[1][2]=-float('inf')
        dp[1][1]=A[0]
        dp[1][0]=-float('inf')

        for i in range(2,N):
            if i==N-1:
                dp[N-1][0]=dp[N-3][0]+A[N-1]
            else:
                dp[i][0]=max(dp[i-2][0]+A[i],dp[i-1][1])
                dp[i][1]=max(dp[i-2][1]+A[i],dp[i-1][2])
                dp[i][2]=dp[i-2][2]+A[i]

        test1=dp[N-1][0]


        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=-float('inf')
        dp[0][0]=0
        dp[1][1]=A[1]
        dp[1][0]=-float('inf')

        for i in range(2,N):
            if i==N-1:
                dp[N-1][0]=dp[N-3][0]+A[N-1]
            else:
                dp[i][0]=max(dp[i-2][0]+A[i],dp[i-1][1])
                dp[i][1]=dp[i-2][1]

        test2=dp[N-1][0]

        A=A[::-1]
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=-float('inf')
        dp[0][0]=0
        dp[1][1]=A[1]
        dp[1][0]=-float('inf')

        for i in range(2,N):
            if i==N-1:
                dp[N-1][0]=dp[N-3][0]+A[N-1]
            else:
                dp[i][0]=max(dp[i-2][0]+A[i],dp[i-1][1])
                dp[i][1]=dp[i-2][1]

        test3=dp[N-1][0]

        test4=sum(A[i] for i in range(0,N) if i%2==1)

        print(max(test1,test2,test3,test4))

    if N%2==0:
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=A[0]
        dp[0][0]=-float('inf')
        dp[1][1]=-float('inf')
        dp[1][0]=-float('inf')

        for i in range(2,N):
            if i==N-1:
                dp[N-1][0]=dp[N-3][0]+A[N-1]
            else:
                dp[i][0]=max(dp[i-2][0]+A[i],dp[i-1][1])
                dp[i][1]=dp[i-2][1]

        test1=dp[N-1][0]

        A=A[::-1]
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=A[0]
        dp[0][0]=-float('inf')
        dp[1][1]=-float('inf')
        dp[1][0]=-float('inf')

        for i in range(2,N):
            if i==N-1:
                dp[N-1][0]=dp[N-3][0]+A[N-1]
            else:
                dp[i][0]=max(dp[i-2][0]+A[i],dp[i-1][1])
                dp[i][1]=dp[i-2][1]

        test2=dp[N-1][0]

        test3=sum(A[i] for i in range(0,N) if i%2==0)
        test4=sum(A[i] for i in range(0,N) if i%2==1)

        print(max(test1,test2,test3,test4))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N==2:
    print(max(A))
elif N==3:
    print(max(A))
else:
    if N%2==1:
        dp=[[0 for i in range(0,3)] for i in range(0,N)]
        dp[0][2]=A[0]
        dp[0][1]=-float('inf')
        dp[0][0]=-float('inf')
        dp[1][2]=-float('inf')
        dp[1][1]=-float('inf')
        dp[1][0]=-float('inf')

        for i in range(2,N):
            if i==N-1:
                dp[N-1][0]=dp[N-3][0]+A[N-1]
            else:
                dp[i][0]=max(dp[i-2][0]+A[i],dp[i-1][1])
                dp[i][1]=max(dp[i-2][1]+A[i],dp[i-1][2])
                dp[i][2]=dp[i-2][2]+A[i]

        test1=dp[N-1][0]

        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=-float('inf')
        dp[0][0]=0
        dp[1][1]=A[1]
        dp[1][0]=-float('inf')

        for i in range(2,N):
            if i==N-1:
                dp[N-1][0]=dp[N-3][0]+A[N-1]
            else:
                dp[i][0]=max(dp[i-2][0]+A[i],dp[i-1][1])
                dp[i][1]=dp[i-2][1]

        test2=dp[N-1][0]

        A=A[::-1]
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=-float('inf')
        dp[0][0]=0
        dp[1][1]=A[1]
        dp[1][0]=-float('inf')

        for i in range(2,N):
            if i==N-1:
                dp[N-1][0]=dp[N-3][0]+A[N-1]
            else:
                dp[i][0]=max(dp[i-2][0]+A[i],dp[i-1][1])
                dp[i][1]=dp[i-2][1]

        test3=dp[N-1][0]

        test4=sum(A[i] for i in range(0,N) if i%2==1)

        print(max(test1,test2,test3,test4))

    if N%2==0:
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=A[0]
        dp[0][0]=-float('inf')
        dp[1][1]=-float('inf')
        dp[1][0]=-float('inf')

        for i in range(2,N):
            if i==N-1:
                dp[N-1][0]=dp[N-3][0]+A[N-1]
            else:
                dp[i][0]=max(dp[i-2][0]+A[i],dp[i-1][1])
                dp[i][1]=dp[i-2][1]

        test1=dp[N-1][0]

        A=A[::-1]
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=A[0]
        dp[0][0]=-float('inf')
        dp[1][1]=-float('inf')
        dp[1][0]=-float('inf')

        for i in range(2,N):
            if i==N-1:
                dp[N-1][0]=dp[N-3][0]+A[N-1]
            else:
                dp[i][0]=max(dp[i-2][0]+A[i],dp[i-1][1])
                dp[i][1]=dp[i-2][1]

        test2=dp[N-1][0]

        test3=sum(A[i] for i in range(0,N) if i%2==0)
        test4=sum(A[i] for i in range(0,N) if i%2==1)

        print(max(test1,test2,test3,test4))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N % 2 == 0:
        return max(sum(A[::2]), sum(A[1::2]))
    dp = [[0] * 3 for _ in range(N)]
    l = [[0] * 3 for _ in range(N)]
    r1 = sum(A[::2])
    r2 = sum(A[1::2])
    r3 = sum(A[2::2])
    os = [0] * N
    es = [0] * N
    for i, v in enumerate(A):
        if i % 2 == 0:
            os[i] = os[i-2] + v
        else:
            es[i] = es[i-2] + v
    for i in range(N):
        s = es[i] + r1 - os[i-1]
        r2 = max(s, r2)
    r0 = -1 * N * pow(10, 10)
    for i in range(N):
        s = r1 - A[i]
        r0 = max(r0,s)
    dp = [[-1 * N * pow(10,10)] * 3 for _ in range(N)]
    dp[0][0] = A[0]
    for i, v in enumerate(A):
        if i < 2:
            continue
        dp[i][0] = dp[i-2][0] + v
        if i < 3:
            continue
        dp[i][1] = max(dp[i-3][0] + v, dp[i-2][1] + v)
        if i < 4:
            continue
        dp[i][2] = max(dp[i-4][0] + v, dp[i-3][1] + v, dp[i-2][2] + v)
    return max(r2, r3, r0, dp[-1][2])
print(main())

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
if n<=3:
  print(max(arr))
else:
  if n%2==0:
    ans=0
    tmp1=0
    tmp2=0
    acum1=[0]
    acum2=[0]
    for i in range(n):
      if i%2==0:
        tmp1+=arr[i]
        acum1.append(acum1[-1]+arr[i])
        acum2.append(acum2[-1]+0)
      else:
        tmp2+=arr[i]
        acum1.append(acum1[-1]+0)
        acum2.append(acum2[-1]+arr[i])
    ans=max(ans,tmp1,tmp2)
    for i in range(0,n-3,2):
      tmp=(acum1[i+1]-acum1[0])+(acum2[-1]-acum2[i+2])
      ans=max(ans,tmp)
    print(ans)
  else:
    ans=0
    tmp1=0
    tmp2=0
    tmp3=0
    acum1=[0]
    acum2=[0]
    for i in range(n):
      if i%2==0:
        tmp1+=arr[i]
        tmp3+=arr[i]
        acum1.append(acum1[-1]+arr[i])
        acum2.append(acum2[-1]+0)
      else:
        tmp2+=arr[i]
        acum1.append(acum1[-1]+0)
        acum2.append(acum2[-1]+arr[i])
    ans=max(ans,tmp1-arr[-1],tmp2,tmp3-arr[0])
    for i in range(0,n-3,2):
      tmp=(acum1[i+1]-acum1[0])+(acum2[-1]-acum2[i+2])
      ans=max(ans,tmp)
    for i in range(1,n-3,2):
      tmp=(acum2[i+1]-acum2[0])+(acum1[-1]-acum1[i+2])
      ans=max(ans,tmp)
    acummax=[-10**18]
    for i in range(n-2,-1,-1):
      tmp=acum1[-1]-acum1[i+2]+acum2[i+1]
      acummax.append(max(acummax[-1],tmp))
    acummax=acummax[::-1]
    for i in range(0,n-3,2):
      tmp=acum1[i+1]-acum1[0]-acum2[i+2]+acummax[i+3]
      ans=max(ans,tmp)
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
if n<=3:
  print(max(arr))
else:
  if n%2==0:
    ans=0
    tmp1=0
    tmp2=0
    acum1=[0]
    acum2=[0]
    for i in range(n):
      if i%2==0:
        tmp1+=arr[i]
        acum1.append(acum1[-1]+arr[i])
        acum2.append(acum2[-1]+0)
      else:
        tmp2+=arr[i]
        acum1.append(acum1[-1]+0)
        acum2.append(acum2[-1]+arr[i])
    ans=max(ans,tmp1,tmp2)
    for i in range(0,n-3,2):
      tmp=(acum1[i+1]-acum1[0])+(acum2[-1]-acum2[i+2])
      ans=max(ans,tmp)
    print(ans)
  else:
    ans=0
    tmp1=0
    tmp2=0
    tmp3=0
    acum1=[0]
    acum2=[0]
    for i in range(n):
      if i%2==0:
        tmp1+=arr[i]
        tmp3+=arr[i]
        acum1.append(acum1[-1]+arr[i])
        acum2.append(acum2[-1]+0)
      else:
        tmp2+=arr[i]
        acum1.append(acum1[-1]+0)
        acum2.append(acum2[-1]+arr[i])
    ans=max(ans,tmp1-arr[-1],tmp2,tmp3-arr[0])
    for i in range(0,n-3,2):
      tmp=(acum1[i+1]-acum1[0])+(acum2[-1]-acum2[i+2])
      ans=max(ans,tmp)
    for i in range(1,n-3,2):
      tmp=(acum2[i+1]-acum2[0])+(acum1[-1]-acum1[i+2])
      ans=max(ans,tmp)
    acummax=[-10**18]
    for i in range(n-2,-1,-1):
      tmp=acum1[-1]-acum1[i+2]+acum2[i+1]
      acummax.append(max(acummax[-1],tmp))
    acummax=acummax[::-1]
    for i in range(0,n-3,2):
      tmp=acum1[i+1]-acum1[0]-acum2[i+2]+acummax[i]
      ans=max(ans,tmp)
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
if n<=3:
  print(max(arr))
else:
  if n%2==0:
    ans=0
    tmp1=0
    tmp2=0
    acum1=[0]
    acum2=[0]
    for i in range(n):
      if i%2==0:
        tmp1+=arr[i]
        acum1.append(acum1[-1]+arr[i])
        acum2.append(acum2[-1]+0)
      else:
        tmp2+=arr[i]
        acum1.append(acum1[-1]+0)
        acum2.append(acum2[-1]+arr[i])
    ans=max(ans,tmp1,tmp2)
    for i in range(0,n-3,2):
      tmp=(acum1[i+1]-acum1[0])+(acum2[-1]-acum2[i+2])
      ans=max(ans,tmp)
    print(ans)
  else:
    ans=0
    tmp1=0
    tmp2=0
    tmp3=0
    acum1=[0]
    acum2=[0]
    for i in range(n):
      if i%2==0:
        tmp1+=arr[i]
        tmp3+=arr[i]
        acum1.append(acum1[-1]+arr[i])
        acum2.append(acum2[-1]+0)
      else:
        tmp2+=arr[i]
        acum1.append(acum1[-1]+0)
        acum2.append(acum2[-1]+arr[i])
    ans=max(ans,tmp1-arr[-1],tmp2,tmp3-arr[0])
    for i in range(0,n-3,2):
      tmp=(acum1[i+1]-acum1[0])+(acum2[-1]-acum2[i+2])
      ans=max(ans,tmp)
    for i in range(1,n-3,2):
      tmp=(acum2[i+1]-acum2[0])+(acum1[-1]-acum1[i+2])
      ans=max(ans,tmp)
    acummax=[-10**18]
    for i in range(n-2,-1,-1):
      tmp=acum1[-1]-acum1[i+2]+acum2[i+1]
      acummax.append(max(acummax[-1],tmp))
    acummax=acummax[::-1]
    print(acummax)
    for i in range(0,n-3,2):
      tmp=acum1[i+1]-acum1[0]-acum2[i+2]+acummax[i]
      ans=max(ans,tmp)
    print(ans)

Submission status: Wrong Answer

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

def func(As):
    if N % 2 == 0:
        sum1 = sum(As[::2])
        sum2 = sum(As[1::2])
        return max(sum1, sum2)

    else:
        ans1 = sum(As[1::2])

        accAs = [0] * N
        accAs[0] = As[0]
        accRevAs = [0] * N
        accRevAs[-1] = As[-1]
        for i in range(2, N, 2):
            accAs[i] = accAs[i-2] + As[i]
        for i in reversed(range(0, N-2, 2)):
            accRevAs[i] = accRevAs[i+2] + As[i]

        ans2 = -float('inf')
        for i in range(0, N-4, 2):
            sm = accAs[i] + accRevAs[i+4]
            if sm > ans2:
                ans2 = sm

        dp0 = [0, As[0]] + [0] * (N-2)
        dp1 = [As[0], As[1]] + [0] * (N-2)
        for i in range(2, N-2, 2):
            dp1[i] = dp0[i-1] + As[i]
            v = dp0[i-1] if dp0[i-1] >= dp1[i-1] else dp1[i-1]
            dp1[i+1] = v + As[i+1]
            dp0[i+1] = dp1[i]

        ans3 = sum(As[2::2])
        for i in range(1, N-2, 2):
            sm = dp0[i] if dp0[i] >= dp1[i] else dp1[i]
            sm += accRevAs[i+3]
            if sm > ans3:
                ans3 = sm

        return max(ans1, ans2, ans3)


ans = max(func(As), func(As[::-1]))
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
if n<=3:
  print(max(arr))
else:
  if n%2==0:
    ans=0
    tmp1=0
    tmp2=0
    acum1=[0]
    acum2=[0]
    for i in range(n):
      if i%2==0:
        tmp1+=arr[i]
        acum1.append(acum1[-1]+arr[i])
        acum2.append(acum2[-1]+0)
      else:
        tmp2+=arr[i]
        acum1.append(acum1[-1]+0)
        acum2.append(acum2[-1]+arr[i])
    ans=max(ans,tmp1,tmp2)
    for i in range(0,n-3,2):
      tmp=(acum1[i+1]-acum1[0])+(acum2[-1]-acum2[i+2])
      ans=max(ans,tmp)
    print(ans)
  else:
    ans=0
    tmp1=0
    tmp2=0
    tmp3=0
    acum1=[0]
    acum2=[0]
    for i in range(n):
      if i%2==0:
        tmp1+=arr[i]
        tmp3+=arr[i]
        acum1.append(acum1[-1]+arr[i])
        acum2.append(acum2[-1]+0)
      else:
        tmp2+=arr[i]
        acum1.append(acum1[-1]+0)
        acum2.append(acum2[-1]+arr[i])
    ans=max(ans,tmp1-arr[-1],tmp2,tmp3-arr[0])
    for i in range(0,n-3,2):
      tmp=(acum1[i+1]-acum1[0])+(acum2[-1]-acum2[i+2])
      ans=max(ans,tmp)
    for i in range(1,n-3,2):
      tmp=(acum2[i+1]-acum2[0])+(acum1[-1]-acum1[i+2])
      ans=max(ans,tmp)
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
out = 0
if N%2==0:
    for i in range(N//2):
        out += max(A[2*i],A[2*i+1])
    print(out)
else:
    X = []
    Y = []
    for i in range(N):
        if i%2==0:
            X.append(A[i])
        else:
            Y.append(A[i])
    Z = []
    W = []
    for i in range(N//2):
        Z.append(X[i]-Y[i])
        W.append(X[i+1]-Y[i])
    P = [0]*(N//2+1)
    Q = [0]*(N//2+1)
    max1 = 0
    max2 = 0
    sum1 = 0
    sum2 = 0
    for i in range(N//2):
        sum1 += Z[i]
        if max1 < sum1:
            max1 = sum1
        sum2 += W[N//2-1-i]
        if max2 < sum2:
            max2 = sum2
        P[i+1] = max1
        Q[-1*i-1-1] = max2
    R = []
    for i in range(N//2+1):
        R.append(P[i]+Q[i])
    # print(Z)
    # print(W)
    # print(P)
    # print(Q)
    # print(sum(Y))
    print(sum(Y)+max(max(R),0))

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10**20
    N=I()
    A=LI()
    if N%2==0:
        ans=0
        for i in range(0,N,2):
            ans+=A[i]
        ans=max(ans,sum(A)-ans)
        print(ans)
    else:
        """左から見ていく，i個を見たときに，
        iが偶数：
        　現在i//2個取得　or i//2 - 1取得(もう余裕がない)
        
        iが奇数：
        　現在i// +12個取得　or i//2取得(もう余裕がない)
        さらにi番目をとったか撮ってないかで2通り 
        ただし，余裕がある状態から取らないのは，数が足りなくなる
        """
        tight_get=[0]*N
        tight_not=[0]*N
        lo=[0]*N
        
        #最初だけ，取ったら必ずlooseになる
        lo[0]=A[0]
        lo[1]=A[1]
        
        for i in range(2,min(3,N)):
            LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i]+tight_not[i-1]]
            tight_get[i]=max(LL)
            LL=[lo[i-2]]
            tight_not[i]=max(LL)
            lo[i]=lo[i-2]+A[i]
            
        for i in range(3,min(4,N)):
            LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i],tight_not[i-1]+A[i],lo[i-3]+A[i]]
            tight_get[i]=max(LL)
            LL=[lo[i-2]]
            tight_not[i]=max(LL)
            lo[i]=max(lo[i-2]+A[i],lo[i-3]+A[i])
            
        for i in range(4,N):
            LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i],tight_not[i-1]+A[i],lo[i-3]+A[i],lo[i-4]+A[i]]
            tight_get[i]=max(LL)
            LL=[lo[i-2]]
            tight_not[i]=max(LL)
            lo[i]=lo[i-2]+A[i]
            
        print(max(tight_get[-1],tight_not[-1]))
    
    
    
        
        
        

main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
out = 0
if N%2==0:
    for i in range(N//2):
        out += max(A[2*i],A[2*i+1])
    print(out)
else:
    X = []
    Y = []
    for i in range(N):
        if i%2==0:
            X.append(A[i])
        else:
            Y.append(A[i])
    Z = []
    W = []
    for i in range(N//2):
        Z.append(X[i]-Y[i])
        W.append(X[i+1]-Y[i])
    P = [0]*(N//2+1)
    Q = [0]*(N//2+1)
    max1 = 0
    max2 = 0
    sum1 = 0
    sum2 = 0
    for i in range(N//2):
        sum1 += Z[i]
        if max1 < sum1:
            max1 = sum1
        sum2 += W[N//2-1-i]
        if max2 < sum2:
            max2 = sum2
        P[i+1] = max1
        Q[-1*i-1-1] = max2
    R = []
    for i in range(N//2+1):
        R.append(P[i]+Q[i])
    # print(Z)
    # print(W)
    # print(P)
    # print(Q)
    # print(sum(Y))
    print(sum(Y)+max(R))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n,*a = [int(i) for i in open(0).read().split()]
a1 = list(accumulate([0]+a[::2]))
a2 = list(accumulate([0]+a[n-1::-2]))[::-1]
ans = max(x+y for x,y in zip(a1,a2[n&1:]))
if n&1: ans = max(ans, max(x+y+mid for x,y,mid in zip(a1,a2[2:],a[1::2])))
print(ans)

Submission status: Wrong Answer

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

if N%2==0:
    ans = max(sum(A[::2]),sum(A[1::2]))
    print(ans)
else:
    INF = 2* 10**9
    dp = [[-INF]*N for _ in [0]*3]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for i in range(2,N,2):
        a = A[i]
        dp[0][i] = dp[0][i-2] + a
    for i in range(3,N):
        a = A[i]
        dp[1][i] = max(dp[1][i-2],dp[0][i-3]) + a
    for i in range(4,N,2):
        a = A[i]
        dp[2][i] = max(dp[2][i-2],dp[1][i-3],dp[0][i-4]) + a
    print(dp[2][-1])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n,*a = [int(i) for i in open(0).read().split()]
a1 = list(accumulate([0]+a[::2]))
a2 = list(accumulate([0]+a[n-1::-2]))[::-1]
ans = max(x+y for x,y in zip(a1,a2[1:]))
if n&1: ans = max(ans, max(x+y+mid for x,y,mid in zip(a1,a2[2:],a[1::2])))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for s in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# d = collections.defaultdict(list)
import sys
sys.setrecursionlimit(15000)

n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
dp = [[None]*n for _ in range(n//2+1)]
dp[0] = [0]*n
dp[1][0] = a[0]
dp[1][1] = a[1]
if n > 2:
    dp[1][2] = a[2]
ret = 0
if n % 2 == 0:
    for i in range(2,n):
        for j in range(1,n//2+1):
            if dp[j-1][i-2] != None:
                dp[j][i] = dp[j-1][i-2]+a[i]
                if j == n//2:
                    ret = max(ret,dp[j][i])
else:
    for i in range(2,n):
        for j in range(1,n//2+1):
            if dp[j-1][i-2] != None or dp[j-1][i-3] != None:
                if dp[j-1][i-2] != None and dp[j-1][i-3] != None:
                    dp[j][i] = max(dp[j-1][i-2],dp[j-1][i-3])+a[i]
                elif dp[j-1][i-2] != None:
                    dp[j][i] = dp[j-1][i-2]+a[i]
                elif dp[j-1][i-3] != None:
                    dp[j][i] = dp[j-1][i-3]+a[i]
                if j == n//2:
                    ret = max(ret,dp[j][i])
#print(dp)
print(ret)

Submission status: Wrong Answer

Solution code:
N=int(input())
A= list(map(int,input().split()))
kin=[0]*N
gin=[0]*N
if N<=3:
 print(max(A))
else:
 kin[0]=A[0]
 kin[1]=A[1]
 kin[2]=kin[0]+A[2]
 gin[2]=A[2]
 for i in range(3,N):
  if i%2==1:
   kin[i]=max(kin[i-2],kin[i-3])+A[i]
  else:
   kin[i]=kin[i-2]+A[i]
   gin[i]=max(kin[i-3],gin[i-2])+A[i]
if N%2==0:
 print(max(kin[N-1],kin[N-2]))
else:
 print(max(gin[N-1],kin[N-2]))

Submission status: Wrong Answer

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

from itertools import accumulate

# a[i]+...+a[j]までは　b[j+1]-b[i]

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

a0 = a[0::2]
a1 = a[1::2]

if n%2==0:
    ans = max(sum(a0),sum(a1))
    print(ans)
    exit()


b0 = [0] + a0
b0 = list(accumulate(b0))

b1 = [0] + a1
b1 = list(accumulate(b1))


a0.reverse()
a1.reverse()

b0_ = [0] + a0
b0_ = list(accumulate(b0_))

b1_ = [0] + a1
b1_ = list(accumulate(b1_))

ans = 0
for i in range(n//2+1):
    tmp00 = b0[i] + b0_[n//2-i]
    tmp01 = b0[i] + b1_[n//2-i]
    tmp10 = b1[i] + b0_[n//2-i]
    tmp11 = b1[i] + b1_[n//2-i]

    ans = max(ans,tmp00,tmp01,tmp10,tmp11)

a1.reverse()

for i in range(2,n//2+1):
    for j in range(i,n//2+1):
        mid = b1[j] - b1[i-1]
        tmp = b0[i-1] + mid + b0_[n//2-j]
        ans = max(ans,tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
if N%2 == 0:
    t = sum(A[::2])
    print(max(t, sum(A)-t))
else:
    A.insert(0, 0)
    A.insert(N+1, 0)
    ls1 = [0 for _ in range(N+2)]
    ls2 = [0 for _ in range(N+2)]
    rs1 = [0 for _ in range(N+2)]
    rs2 = [0 for _ in range(N+2)]
    for i in range(1, N+1):
        if i%2 == 1:
            ls1[i] += +A[i]
        else:
            ls2[i] += +A[i]
        ls1[i+1] += ls1[i]
        ls2[i+1] += ls2[i]
    for i in range(N, 0, -1):
        if i%2 == 1:
            rs1[i] += A[i]
        else:
            rs2[i] += A[i]
        rs1[i-1] += rs1[i]
        rs2[i-1] += rs2[i]
    
    maxV = 0
    for i in range(N+2):
        if i+3 < N+2:
            maxV = max(maxV, ls1[i]+rs1[i+3])
        if i+2 < N+2:
            maxV = max(maxV, ls1[i]+rs2[i+2], ls2[i]+rs1[i+2])
        if i+1 < N+2:
            maxV = max(maxV, ls2[i]+rs2[i+1])
    print(maxV)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
if n<=3:
  print(max(arr))
else:
  if n%2==0:
    ans=0
    tmp1=0
    tmp2=0
    acum1=[0]
    acum2=[0]
    for i in range(n):
      if i%2==0:
        tmp1+=arr[i]
        acum1.append(acum1[-1]+arr[i])
        acum2.append(acum2[-1]+0)
      else:
        tmp2+=arr[i]
        acum1.append(acum1[-1]+0)
        acum2.append(acum2[-1]+arr[i])
    ans=max(ans,tmp1,tmp2)
    for i in range(0,n-3,2):
      tmp=(acum1[i+1]-acum1[0])+(acum2[-1]-acum2[i+2])
      ans=max(ans,tmp)
    print(ans)
  else:
    ans=0
    tmp1=0
    tmp2=0
    tmp3=0
    acum1=[0]
    acum2=[0]
    for i in range(n):
      if i%2==0:
        tmp1+=arr[i]
        tmp3+=arr[i]
        acum1.append(acum1[-1]+arr[i])
        acum2.append(acum2[-1]+0)
      else:
        tmp2+=arr[i]
        acum1.append(acum1[-1]+0)
        acum2.append(acum2[-1]+arr[i])
    ans=max(ans,tmp1-arr[-1],tmp2,tmp3-arr[0])
    for i in range(0,n-3,2):
      tmp=(acum1[i+1]-acum1[0])+(acum2[-1]-acum2[i+2])
      ans=max(ans,tmp)
    for i in range(1,n-3,2):
      tmp=(acum2[i+1]-acum1[0])+(acum1[-1]-acum1[i+2])
      ans=max(ans,tmp)
    acummax=[0]
    for i in range(n-3,-1,-1):
      tmp=acum1[-1]-acum1[i+2]+acum2[i+1]
      acummax.append(max(acummax[-1],tmp))
    acummax=acummax[::-1]
    for i in range(0,n-3,2):
      tmp=acum1[i+1]-acum1[0]-acum2[i+2]+acummax[i]
      ans=max(ans,tmp)
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin


def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    if n % 2 == 0:
        v = [[None for j in range(2)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        for i in range(2, n):
            for j in range(2):
                c = []
                if j == 1:
                    if v[i-2][j] is not None:
                        c.append(v[i-2][j])
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                else:
                    if v[i-2][j] is not None:
                        c.append(v[i-2][j])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(2) if v[n-1][j] is not None]
        print(max(c))
    else:
        v = [[None for j in range(3)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        v[2][2] = a[2]
        for i in range(3, n):
            for j in range(3):
                c = []
                if j == 2:
                    if v[i-2][j] is not None:
                        c.append(v[i-2][j])
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                    if v[i-4][j-2] is not None:
                        c.append(v[i-4][j-2])
                elif j == 1:
                    if v[i-2][j] is not None:
                        c.append(v[i-2][j])
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                else:
                    if v[i-2][j] is not None:
                        c.append(v[i-2][j])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(3) if v[n-1][j] is not None]
        print(max(c))


def input(): return stdin.readline().rstrip()


main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
F = A[::2]
L = A[1::2]
if N%2 == 0:
    ans = max(sum(L),sum(F))
    print(ans)
else:
    from collections import defaultdict
    dp_non = defaultdict(lambda: -2**60)
    dp_take = defaultdict(lambda: -2**60)
    dp_non[(0,0)] = 0
    for i,x in enumerate(A,1):
        j = (i-1)//2
        for n in (j,j+1):
            dp_non[(i,n)] = max(dp_non[(i-1,n)],dp_take[(i-1,n)])
            dp_take[(i,n)] = dp_non[(i-1,n-1)]+x

    print(max(dp_non[N,N//2],dp_take[(N,N//2)]))