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:
import sys
input = sys.stdin.readline

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

dp = [[0, 0] for _ in range(n + 1)] # 0は選んでない

for i in range(1, n + 1):
    dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
    dp[i][1] = dp[i - 1][0] + a[i - 1]

print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

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

if N % 2 == 0:
    even = A[::2]
    odd = A[1::2]
    assert len(even) == len(odd) == N // 2
    print(max(sum(even), sum(odd)))
    exit()


@lru_cache(maxsize=None)
def dp(i, numSkips):
    if i < 0:
        return 0
    best = A[i] + dp(i - 2, numSkips)
    if numSkips:
        best = max(best, A[i] + dp(i - 3, numSkips - 1))
    return best


# Warm cache
for i in range(N):
    dp(i, 0)
    dp(i, 1)
    dp(i, 2)

print(max(dp(N - 1, 2), dp(N - 2, 1), dp(N - 3, 0)))

Submission status: Wrong Answer

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

sm1 = []
sm2 = []
tmp1 = 0
tmp2 = 0
for i in range(n):
    if i % 2 == 0:
        tmp1 += a[i]
        sm1.append(tmp1)
    else:
        tmp2 += a[i]
        sm2.append(tmp2)

ans = max(sm1[-1], sm2[-1])

if n % 2 != 0:
    for i in range(n):
        if i % 2 == 0:
            ans = max(ans, sm1[-1]-a[i])

for i in range(len(sm2)):
    if n %2 == 0 and i >= len(sm2)-2:
        continue
    ans = max(ans, sm2[i] + sm1[-1] - sm1[i+1])

for i in range(len(sm2)):
    ans = max(ans, sm1[i] + sm2[-1] - sm2[i])
        

# 111222111 pattern

switch_better = [False]*len(sm2)

for i in range(len(sm2)):
    switch_better[i] = sm1[i]-sm2[i]

tmp = 0
val = switch_better[0]

for i in range(len(sm2)):
    if n %2 == 0 and i >= len(sm2)-2:
        continue
    ans = max(ans, sm2[i] + sm1[-1] - sm1[i+1])
    
    if val < switch_better[i]:
        tmp = i
        val = switch_better[i]
    
    ans = max(ans, sm2[i]+sm1[-1]-sm1[i+1]-sm2[tmp]+sm1[tmp])

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
if n<=3:
    print(max(arr))
    exit()
if n%2==0:
    ans=0
    tmp=0
    for i in range(0,n,2):
        tmp+=arr[i]
    ans=max(ans,tmp)
    tmp=0
    for i in range(1,n,2):
        tmp+=arr[i]
    ans=max(ans,tmp)
    acum1=[0]
    acum2=[0]
    for i in range(n):
        if i%2==0:
            acum1.append(acum1[-1]+arr[i])
            acum2.append(acum2[-1]+0)
        else:
            acum1.append(acum1[-1]+0)
            acum2.append(acum2[-1]+arr[i])
    for i in range(0,n,2):
        tmp=(acum1[i]-acum1[0])+(acum2[-1]-acum2[i])
        ans=max(ans,tmp)
    print(ans)
else:
    ans=0
    tmp=0
    for i in range(0,n-2,2):
        tmp+=arr[i]
    ans=max(ans,tmp)
    tmp=0
    for i in range(1,n-1,2):
        tmp+=arr[i]
    ans=max(ans,tmp)
    tmp=0
    for i in range(2,n,2):
        tmp+=arr[i]
    ans=max(ans,tmp)
    acum1=[0]
    acum2=[0]
    for i in range(n):
        if i%2==0:
            acum1.append(acum1[-1]+arr[i])
            acum2.append(acum2[-1]+0)
        else:
            acum1.append(acum1[-1]+0)
            acum2.append(acum2[-1]+arr[i])
    for i in range(0,n-1,2):
        tmp=(acum1[i]-acum1[0])+(acum2[-1]-acum2[i])
        ans=max(ans,tmp)
    for i in range(1,n,2):
        tmp=(acum2[i]-acum2[0])+(acum1[-1]-acum1[i])
        ans=max(ans,tmp)
    acummax=[0]
    for i in range(n-1,-1,-1):
        tmp=acum1[-1]-acum1[i]+acum2[i]
        acummax.append(max(acummax[-1],tmp))
    acummax=acummax[::-1]
    for i in range(0,n,2):
        tmp=(acum1[i]-acum1[0]-acum2[i])+acummax[i+1]
        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:

    e = 0
    o = 0
    

    for i in range(N):

        if i % 2 == 0:
            e += A[i]
        else:
            o += A[i]

    el = [0]
    ol = [0]

    for i in range(N):

        if i % 2 == 0:
            el.append(el[-1] + A[i])
        else:
            ol.append(ol[-1] + A[i])

    eri = [0]
    ori = [0]

    for i in range(N-1,-1,-1):

        if i % 2 == 0:
            eri.append(eri[-1] + A[i])
        else:
            ori.append(ori[-1] + A[i])

    ans = max(e,o)

    for i in range(N//2+1):
        ans = max(ans,el[i]+ori[N//2-i],ol[i]+eri[N//2-i])
    print (ans)

else:

    el = [0]
    ol = [0]

    for i in range(N):

        if i % 2 == 0:
            el.append(el[-1] + A[i])
        else:
            ol.append(ol[-1] + A[i])

    eri = [0]
    ori = [0]

    for i in range(N-1,-1,-1):

        if i % 2 == 0:
            eri.append(eri[-1] + A[i])
        else:
            ori.append(ori[-1] + A[i])

    ans = float("-inf")



    LS = [0]
    LSM = [0]
    for i in range(0,N-1,2):

        LS.append(LS[-1] + A[i] - A[i+1])
        LSM.append(max(LSM[-1],LS[-1]))

    RS = [0]
    RSM = [0]
    for i in range(N-1,0,-2):

        RS.append(RS[-1] + A[i] - A[i-1])
        RSM.append(max(RSM[-1],RS[-1]))

    EOE = float("-inf")
    for i in range(N//2+1):
        EOE = max(EOE , LSM[i] + RSM[N//2-i])

    
    for i in range(N):

        if i <= N//2:

            ans = max(ans , el[i]+ori[N//2-i] , ol[i]+eri[N//2-i] , el[i]+eri[N//2-i] , ol[-1] + EOE)

    print (ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int( input())
    A = list( map( int, input().split()))
    if N == 2:
        print(A[0], A[1])
        return
    OddSum = [0]
    EvenSum = [0]
    for i in range(N):
        if i%2 == 0:
            OddSum.append(OddSum[-1] + A[i])
            EvenSum.append(EvenSum[-1])
        else:
            OddSum.append(OddSum[-1])
            EvenSum.append(EvenSum[-1] + A[i])
    if N%2 == 0:
        ans = max(OddSum[-1], EvenSum[-1])
        for i in range(1,N,2):
            t = EvenSum[-1] - EvenSum[i+1] + OddSum[i] - OddSum[0]
            if ans < t:
                ans = t
        print(ans)
        return

    ans = max( EvenSum[-1], OddSum[-1] - min(A[::2]))
    Head = [0]
    for i in range(1,N+1):
        if i%2 == 1:
            Head.append(Head[-1])
            continue
        if i == 2:
            Head.append(A[i-1])
            continue
        Head.append( max(Head[-1], OddSum[i-2]) + A[i-1])

    Back = [0]
    for i in range(N,0,-1):
        if i%2 == 1:
            Back.append(Back[-1])
            continue
        if i == N-1:
            Back.append(A[i-1])
            continue
        Back.append( max(Back[-1], OddSum[-1] - OddSum[i+2]) + A[i-1])

    # print(Head, Back)
    if ans < Head[-1]:
        ans = Head[-1]
    if ans < Back[-1]:
        ans = Back[-1]
    for i in range(2,N+1,2):
        if ans < Head[i] + Back[N-1-i]:
            ans = Head[i] + Back[N-1-i]
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
from functools import reduce
 
n=int(input())
ar=list(map(int,input().split(' ')))
 
if n%2==0:
	print(max(sum(ar[i] for i in range(0,n,2)),sum(ar[i] for i in range(1,n,2))))
	exit()
	
dp=[[-(10**20)]*5 for i in range(n+5)]+[[0]+[-(10**20)]*5 for i in range(1)]
 
 
#1> 2 3> 4  6> 7 8> 9 10 11> 12> 14
def cn(z,j):
	return (z-j+1)//2
ans=-(10**20)
for i in range(n):
	idx=int(i)
	if idx<2:
		dp[idx][0]=0
	if idx-2>=0:
		dp[idx]=dp[idx-2].copy()
	for j in range(1,4):
			for k in range(j+1):
				if idx-k-1>=0:
					dp[idx][j]=max(dp[idx][j],dp[idx-k-2][j-k])
	for j in range(4):
		dp[i][j]+=ar[i]
		if cn(i+1,j)==n//2:
			ans=max(ans,dp[i][j])
print(ans)

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])))
    exit()
ans=-10**10
t1=a[1::2]
t2=a[::2]
ans=sum(t1)
s=sum(t1)
for i in range(n//2):
    s+=t2[i]
    s-=t1[i]
    ans=max(ans,s)
s+=t2[-1]
s-=t2[0]
ans=max(ans,s)
print(ans)

Submission status: Wrong Answer

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


ruiseki0 = [0] * (n + 10) 
for i in range(n):
    ruiseki0[i + 1] = ruiseki0[i]
    if i % 2 == 0:
        ruiseki0[i + 1] += a[i]
        
l = [0] * (n + 1)
for i in range(n + 1):
    if i % 2 == 0:
        if i == 0:
            l[i] = 0
        else:
            l[i] = max(l[i - 2] + a[i - 1], ruiseki0[i])
    else:
        l[i] = ruiseki0[i]


a = a[::-1]
ruiseki0 = [0] * (n + 10) 
for i in range(n):
    ruiseki0[i + 1] = ruiseki0[i]
    if i % 2 == 0:
        ruiseki0[i + 1] += a[i]
        
r = [0] * (n + 1)
for i in range(n + 1):
    if i % 2 == 0:
        if i == 0:
            r[i] = 0
        else:
            r[i] = max(r[i - 2] + a[i - 1], ruiseki0[i])
    else:
        r[i] = ruiseki0[i]       
   
ans = - 10 ** 20
for i in range(n):
    if n - i - 2 < 0:
        break
    ans = max(ans, l[i] + r[n - i - 2])
    
if n % 2 == 0:
    ans1 = 0
    ans2 = 0
    for i in range(n):
        if i % 2 == 0:
            ans1 += a[i]
        else:
            ans2 += a[i]
    ans = max(ans1, ans2, ans)
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
if n%2 == 0:
     e = [a[0]]
     es = [a[0]]
     o = [a[1]]
     os = [a[1]]
     ans = 0
     for i in range(2,n):
          if i % 2 == 0:
               e.append(a[i])
               es.append(es[-1]+a[i])
          else:
               o.append(a[i])
               os.append(os[-1] + a[i])

     for i in range(0,n//2):
          ans = max([ans,os[i]-es[i]+es[-1],es[i]-os[i]+os[-1]])

else:
     e = [a[0]]
     es = [a[0]]
     o = [a[1]]
     os = [a[1]]
     ans = 0
     for i in range(2, n-1):
          if i % 2 == 0:
               e.append(a[i])
               es.append(es[-1] + a[i])
          else:
               o.append(a[i])
               os.append(os[-1] + a[i])

     for i in range((n-1) // 2):
          ans = max([ans, os[i] - es[i] + es[-1], es[i] - os[i] + os[-1]])
     for i in range((n-1) // 2):
          ans = max([ans,a[-1]+es[-1]-e[i]])
     




print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
if N%2 == 0:
    O = [0] * (N//2+1)
    E = [0] *(N//2+1)
    for i in range(N//2):
        E[i+1] = E[i] + A[2*i]
        O[i+1] = O[i] + A[N-1-2*i]
    ans = 0
    for i in range(N//2+1):
        ans = max(ans, E[i] + O[N//2-i])
    print(ans)
else:
    ans = 0
    Min = 10**10
    for i in range(N//2+1):
        Min = min(Min, A[2*i])
        ans += A[2*i]
    ans -= Min
    O = [0] * (N//2+1)
    E = [0] *(N//2+1)
    for i in range(N//2):
        E[i+1] = E[i] + A[2*i]
        O[i+1] = O[i] + A[N-1-2*i]
    Max = [0, 0]
    li1 = []
    li1.append(Max)
    Min = 10**10
    for i in range(N//2):
        if Max[1] == 0:
            if A[2*i] >= A[2*i+1]:
                Max = [Max[0]+A[2*i], 0]
            else:
                Max = [Max[0]+A[2*i+1], 1]
        else:
            if E[i] + A[2*i] >= Max[0] + A[2*i+1]:
                Max = [E[i] + A[2*i], 0]
            else:
                Max = [Max[0]+A[2*i+1], 1]
        li1.append(Max)
    Max = [0,0]
    li2 = [[0,0]]
    for i in range(N//2):
        if Max[1] == 0:
            if A[N-1-2*i] >= A[N-1-2*i-1]:
                Max = [Max[0]+A[N-1-2*i], 0]
            else:
                Max = [Max[0]+A[N-1-2*i-1], 1]
        else:
            if O[i] + A[N-1-2*i] >= Max[0] + A[N-1-2*i-1]:
                Max = [O[i] + A[N-1-2*i], 0]
            else:
                Max = [Max[0]+A[N-1-2*i-1], 1]
        li2.append(Max)
    for i in range(N//2):
        Max = li1[i] 
        if Max[1] == 1:
            ans = max(ans, Max[0]+li2[N//2-i][0])
        else:
            ans = max(ans, Max[0]+li2[N//2-i][0])
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    if n % 2 == 0:
        print(max(sum(a[::2]), sum(a[1::2])))
        return
    dp = [[[-10**15]*3, [-10**15]*3] for _ in [0]*(n+1)]
    dp[0][0][0] = 0
    for i in range(n):
        # 使う場合
        dp[i+1][1][0] = max(dp[i+1][1][0], dp[i][0][0]+a[i])
        dp[i+1][1][1] = max(dp[i+1][1][1], dp[i][0][1]+a[i])
        dp[i+1][1][2] = max(dp[i+1][1][2], dp[i][0][2]+a[i])
        # 使わない場合
        dp[i+1][0][1] = max(dp[i+1][0][1], dp[i][0][0])
        dp[i+1][0][2] = max(dp[i+1][0][2], dp[i][0][1])
        # 更新
        dp[i+1][0][0] = max(dp[i+1][0][0], dp[i][1][0])
        dp[i+1][0][1] = max(dp[i+1][0][1], dp[i][1][1])
        dp[i+1][0][2] = max(dp[i+1][0][2], dp[i][1][2])
    print(max(dp[n][0][2], dp[n][1][2], dp[n][1][1], dp[n][0][1]))


main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans1=0
ans2=0
inf=-10**18
if n%2:
    dp=[[inf]*3 for i in range(n)]
    dp[0][0]=a[0]
    dp[2][0]=dp[0][0]+a[2]
    for i in range(2,n):
        dp[i][0]=dp[i-2][0]+a[i]
        if i>=3:
            dp[i][1]=max(dp[i-3][0],dp[i-2][1])+a[i]
        if i>=4:
            dp[i][2]=max(dp[i-4][0],dp[i-3][1],dp[i-2][2])+a[i]
    ans=max(dp[n-3][0],dp[n-2][1],dp[n-1][2])
    # print(dp)
    dp=[[inf]*2 for i in range(n)]
    dp[1][0]=a[1]
    for i in range(3,n):
        dp[i][0]=dp[i-2][0]
        dp[i][1]=max(dp[i-3][0],dp[i-2][1])
    ans=max(ans,dp[-1][1],dp[-2][0])
    for i in range(2,n,2):
        ans1+=a[i]
    print(max(ans,ans1))
else:
    dp=[[inf]*2 for i in range(n)]
    dp[0][0]=a[0]
    for i in range(2,n):
        dp[i][0]=dp[i-2][0]
        if i>2:
            dp[i][1]=max(dp[i-3][0],dp[i-2][1])
    ans=max(dp[-1][1],dp[-2][0])
    for i in range(1,n,2):
        ans1+=a[i]
    print(max(ans1,ans))

Submission status: Wrong Answer

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

le, lo, re, ro = [0], [0], [0], [0]

for i in range(n):
    if i % 2 == 0:
        le.append(le[-1] + a[i])
    else:
        lo.append(lo[-1] + a[i])

for i in range(n-1, -1, -1):
    if i % 2 == 0:
        re.append(re[-1] + a[i])
    else:
        ro.append(ro[-1] + a[i])

le_o = [0]
for i in range(len(lo)-1):
    le_o.append(max(0, le_o[-1] + a[2*i+1] - a[2*i]))


if n % 2 == 0:
    n //= 2
    ans = lo[n]
    for i in range(0, n + 1):
        ans = max(ans, le[i] + ro[n-i])

    print(ans)

else:
    n //= 2
    ans = 0
    for i in range(0, n+1):
        ans = max(ans, le[i] + ro[n-i])
        ans = max(ans, lo[i] + re[n-i])
        ans = max(ans, le[i] + re[n-i] + le_o[i])

    print(ans)

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])))
ans=-10**10
t1=a[1::2]
t2=a[::2]
ans=sum(t1)
s=sum(t1)
print(t1,t2)
for i in range(n//2):
    s+=t2[i]
    s-=t1[i]
    ans=max(ans,s)
s+=t2[-1]
s-=t2[0]
ans=max(ans,s)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    indices=[*range(len(a))]
    sorted_indices=sorted(indices,key=lambda i: -a[i])
    dif=[]
    ans=0
    inf=1e+10
    residue=n//2
    for i in range(n):
        nxt=sorted_indices[i]+1
        prv=sorted_indices[i]-1
        if a[sorted_indices[i]]==inf:
            continue
        else:
            ans+=a[sorted_indices[i]]
            residue-=1
            if residue==0:
                break
        if nxt<n:
            a[nxt]=inf
        if prv>=0:
            a[prv]=inf
        
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if n % 2 == 0:
    prefix = [0] * n
    suffix = [0] * n
    for i in range(0, n):
        prefix[i] += nums[i]
        if i - 2 >= 0:
            prefix[i] += prefix[i - 2]

    for i in range(n-1, -1, -1):
        suffix[i] += nums[i]
        if i + 2 < n:
            suffix[i] += suffix[i + 2]
    ans = prefix[-1]

    for i in range(n):
        if i % 2 == 0 and  i + 2 < n:
            ans = max(ans, prefix[i] + suffix[i + 2])
        if i % 2 == 0 and  i + 3 < n:
            ans = max(ans, prefix[i] + suffix[i + 3])
        if i % 2 == 1 and i + 1 < n:
            ans = max(ans, prefix[i] + suffix[i + 1])
        if i % 2 == 1 and i + 2 < n:
            ans = max(ans, prefix[i] + suffix[i + 2])
    print(ans)
else:
    dp = [[0] * n for i in range(3)] # -1, 0, +1
    # dp[delta][num], inclusive
    dp[2][0] = nums[0]
    dp[0][1] = 0
    dp[1][1] = max(nums[0], nums[1])
    dp[2][1] = 0
    dp[0][2] = 0
    dp[1][2] = max(nums[:3])
    dp[2][2] = nums[0] + nums[2]
    if n == 3:
        print(max(nums))
        exit()
    dp[0][3] = max(nums[:4]) # only choose one
    dp[1][3] = max(nums[0] + nums[3], nums[0] + nums[2], nums[1] + nums[3])
    dp[2][3] = 0
    dp[0][4] = max(nums[:5])
    dp[1][4] = max([nums[i] + nums[j] for i in range(5) for j in range(i+2, 5)])
    dp[2][4] = nums[0] + nums[2] + nums[4]

    for i in range(5, n):
        if (i + 1) % 2 == 0: # even
            dp[0][i] = max(dp[1][i - 1], dp[0][i - 2] + nums[i])
            dp[1][i] = max(dp[2][i - 1], dp[1][i - 2] + nums[i])  # 0
        else:
            # odd
            dp[0][i] = max(dp[0][i - 1], nums[i] + dp[0][i - 2])
            dp[1][i] = max(dp[1][i - 2] + nums[i], dp[1][i - 1], dp[2][i - 2])
            dp[2][i] = dp[2][i - 2] + nums[i] # ok
    print(dp[1][-1])

Submission status: Wrong Answer

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

ans = -10**9
if N%2 == 0:
	ans = max(sum(A[0::2]), sum(A[1::2]))
else:
	for i in range(N):
		B = A[:]
		del B[i]
		temp = max(sum(B[0::2]), sum(B[1::2]))
		ans = max(ans, temp)
print(ans)

Submission status: Wrong Answer

Solution code:
"""
F
"""
N=int(input())
A=list(map(int,input().split()))

left=[0]*N
right=[0]*N

left[0]=A[0]
left[1]=A[1]
for i in range(2,N):
    left[i]=A[i]+left[i-2]
right[-1]=A[-1]
right[-2]=A[-2]
for i in range(N-3,-1,-1):
    right[i]=A[i]+right[i+2]

ans=0
if N%2==0:
    ans=max(right[0],left[-1])
    for i in range(N-2):
        if i%2==0:
            continue
        ans=max(ans,left[i]+right[i+2])
else:
    P=[0]*N
    Q=[0]*N
    P[-2]=A[-2]
    Q[-2]=A[-1]
    for i in range(-4,-N-1,-1):
        if i%2==0:
            P[i]=A[i]+max(P[i+2],Q[i+2])
            Q[i]=A[i+1]+Q[i+2]

    data=[0]*N
    for i in range(N):
        data[i]=max(P[i],Q[i])
    
    qqq=0
    for i in range(N-2):
        if i%2==0:
            #使わない
            ans=max(ans,qqq+data[i+1])
            qqq+=A[i]
    ans=max(ans,qqq)
    
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))

answer = [max(A[0],A[1])]
list_sum = []
tmp_sum = 0
for a in A[::2]:
  tmp_sum += a
  list_sum.append(a)

for i in range(2,N):
  if i==2:
    answer.append(max(A[0],A[1],A[2]))
  elif i%2==0:
    answer.append(max(answer[-1], answer[-2]+A[i]))
  else:
    answer.append(max(answer[-2]+A[i],list_sum[(i-1)//2]))

print(answer[-1])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n,*a=map(int,open(0).read().split())
if n%2==0:
	o=a[::2]
	e=a[1::2]
	o=[0]+list(accumulate(o))
	e=list(accumulate(e[::-1]))[::-1]+[0]
	ans=0
	for i in range(n//2+1):
		ans=max(ans,o[i]+e[i])
	print(ans)
	exit()
o=a[::2]
e=a[1::2]
o=[0]+list(accumulate(o))
e=list(accumulate(e[::-1]))[::-1]+[0]
dp=[0]*n
for i in range(n):
	if i%2==1:
		dp[i]=max(o[i//2]+a[i-1],o[i//2]+a[i],dp[i-2]+a[i])
	elif i>0:
		dp[i]=max(dp[i-1],dp[i-2]+a[i])
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(i) for i in input().split()]

if n < 20:
    d = a.copy()

    for i in range(1, n // 2):
        b = [0] * n
        c = -10**18
        for j in range(i * 2, n):
            c = max(c, a[j - 2])
            b[j] = c + d[j]

        a = b.copy()
    print(a[-1])
    exit()
    
b = a[:10]

for i in range(1, n // 2):
    c = [0] * 10
    d = -10**18
    for j in range(10):
        if 2 * i + j >= n:
            continue
        d = max(d, b[j])
        c[j] = d + a[2 * i + j]
    b = c.copy()
print(max(b))

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)
print(ans)

Submission status: Wrong Answer

Solution code:
def examA():
    N = SI()
    ans = "No"
    for s in N:
        if s=="7":
            ans = "Yes"
    print(ans)
    return

def examB():
    N = I()
    ans = 0
    for i in range(1,N+1):
        if i%3==0:
            continue
        if i%5==0:
            continue
        ans += i
    print(ans)
    return

def examC():
    def gcd(x, y):
        if y == 0:
            return x
        while (y != 0):
            x, y = y, x % y
        return x
    K = I()
    ans = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            cur = gcd(i,j)
            for k in range(1,K+1):
                ans += gcd(cur,k)
    print(ans)
    return

def examD():
    N = I()
    S = SI()
    R = [0]*(N+1)
    G = [0]*(N+1)
    B = [0]*(N+1)
    for i in range(N):
        s = S[i]
        R[i+1] += R[i]
        G[i+1] += G[i]
        B[i+1] += B[i]
        if s=="R":
            R[i+1] += 1
        elif s=="G":
            G[i+1] += 1
        elif s=="B":
            B[i+1] += 1
    ans = 0
    for l in range(N):
        Ls = S[l]
        for r in range(l+3,N):
            Rs = S[r]
            if (Ls=="R" and Rs=="B") or (Ls=="B" and Rs=="R"):
                ans += G[r] - G[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="G":
                        ans -= 1
            elif (Ls=="R" and Rs=="G") or (Ls=="G" and Rs=="R"):
                ans += B[r] - B[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="B":
                        ans -= 1
            elif (Ls=="G" and Rs=="B") or (Ls=="B" and Rs=="G"):
                ans += R[r] - R[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="R":
                        ans -= 1
    print(ans)
    return

def examE():
    N, K = LI()

    ans = 0
    print(ans)
    return

def examF():
    N = I()
    A = LI()

    if N%2==0:
        O = [0] * N
        E = [0] * N
        for i in range(N):
            O[i] += O[i - 1]
            E[i] += E[i - 1]
            if i % 2 == 0:
                O[i] += A[i]
            else:
                E[i] += A[i]
        #print(O,E)
        ans = max(O[-1],E[-1])
        print(ans)
        return

    def dfs(n,k):
        if (n+2)//2 <k:
            return -inf
        if k == 0:
            return 0
        if n==0:
            if k==1:
                return A[0]
            return -inf
        if n==1:
            if k==1:
                return max(A[0],A[1])
            return -inf
        res = max(A[n]+dfs(n-2,k-1),dfs(n-1,k))
        return res

    ans = dfs(N-1,N//2)
    #print(dfs(4,2))
    print(ans)
    return

def examF2():
    N = I()
    A = LI()
    if N%2==0:
        O = [0] * N
        E = [0] * N
        for i in range(N):
            O[i] += O[i - 1]
            E[i] += E[i - 1]
            if i % 2 == 0:
                O[i] += A[i]
            else:
                E[i] += A[i]
        #print(O,E)
        ans = max(O[-1],E[-1])
        print(ans)
        return

    dp = [[-inf]*3 for _ in range(N+1)]
    dp[0][0] = 0
    dp[0][1] = 0
    dp[0][2] = 0
    dp[1][0] = 0
    dp[1][1] = 0
    dp[1][2] = A[0]
    for i in range(1,N):
        dp[i+1][2] = A[i] + dp[i-1][2]
        dp[i+1][1] = max(A[i] + dp[i-1][1],dp[i][2])
        dp[i+1][0] = max(A[i] + dp[i-1][0],dp[i][1])
    ans = max(dp[-1][0],dp[-1][1])
    #print(dp)
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF2()

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

Submission status: Wrong Answer

Solution code:
N = int(input())
li = list(map(int, input().split()))
num = int(N / 2)

if N % 2 == 0:
  hoge1 = sum(li[0::2])
  hoge2 = sum(li[1::2])
  # if hoge1 > hoge2:
  #   ans = hoge1
  # else:
  #   ans = hoge2
  ans=max([hoge1,hoge2])
else:
  hoge1 = sum(li[0::2])
  hoge2 = sum(li[1::2])
  hoge3 = sum(li[2::2])
  ans = max([hoge1,hoge2,hoge3])

print(ans)

Submission status: Wrong Answer

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

lis_0 = A[::2]
lis_1 = A[1::2]

if N%2 == 0:
  print(max(sum(lis_0), sum(lis_1)))
else:
  rui_0 = [0 for _ in range(len(lis_0)+1)]
  rui_1 = [0 for _ in range(len(lis_1)+1)]
  for i in range(1, len(lis_1)+1):
    rui_0[i] = rui_0[i-1] + lis_0[i-1]
    rui_1[i] = rui_1[i-1] + lis_1[i-1]
  rui_0[-1] = rui_0[-2] + lis_0[-1]
  last1 = rui_1[-1]
  last0 = rui_0[-1]
  
  
  num = -10**9
  for j in range(len(rui_1)):
    for k in range(j+1, len(rui_1)):
      x = rui_0[j]+rui_1[k]-rui_1[j]+last0-rui_0[k+1]
      if num < x:
      	num = x
  print(max(sum(lis_1), sum(lis_0)-lis_0[0], sum(lis_0)-lis_0[-1], num))

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
a = np.array(input().split(), dtype=np.int)

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

Submission status: Wrong Answer

Solution code:
import math
import random
import sys
import heapq
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, UserString
from functools import lru_cache, cmp_to_key, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)

sys.setrecursionlimit(10**7)
MAX_INT = 2**62-1
input = sys.stdin.buffer.readline


if __name__ == "__main__":
    n = int(input())
    nums = [int(s) for s in input().split()]
    if n % 2 == 0:
        print(max(sum(nums[::2]), sum(nums[1::2])))
    else:
        odd_sum = [0] * (n+1)
        even_sum = [0] * (n+1)
        for i, num in enumerate(nums):
            odd_sum[i+1] = odd_sum[i] + num * (i%2==0)
            even_sum[i+1] = even_sum[i] + num * (i%2!=0)
        # print(odd_sum, even_sum)
        
        max_sum = 0
        for i in range(n):
            pre_odd, post_odd = odd_sum[i], odd_sum[-1] - odd_sum[i+1]
            pre_even, post_even = even_sum[i], even_sum[-1] - even_sum[i+1]
            if i % 2 == 0:
                max_sum = max(max_sum, 
                              max(pre_odd, pre_even) + max(post_even, post_odd))
            else:
                max_sum = max(max_sum, pre_odd + post_even, pre_even + post_odd)
        print(max_sum)

Submission status: Wrong Answer

Solution code:
def solve(n, a_list):
    if n % 2 == 0:
        res_a = [0] * (n // 2 + 1)
        res_b = [0] * (n // 2 + 1)
        for i in range(0, n // 2):
            res_a[i + 1] = res_a[i] + a_list[i * 2]
        for i in range(n // 2 - 1, -1, -1):
            res_b[i] = res_b[i + 1] + a_list[i * 2 + 1]
        return max([res_a[i] + res_b[i] for i in range(n // 2 + 1)])
    else:
        # type a
        dp = [[0] * 3 for _ in range(n)]
        dp[0][0] = a_list[0]
        dp[1][1] = a_list[1]
        dp[2][2] = a_list[2]
        for i in range(n):
            if i % 2 == 0:
                if i >= 2:
                    dp[i][0] = dp[i - 2][0] + a_list[i]
                    dp[i][1] = dp[i - 1][1]
                if i >= 3:
                    dp[i][2] = max(dp[i - 3][1] + a_list[i], dp[i - 2][2] + a_list[i])
            else:
                if i >= 3:
                    dp[i][1] = max(dp[i - 2][1] + a_list[i], dp[i - 3][0] + a_list[i])
                dp[i][0] = dp[i - 1][0]
                dp[i][2] = dp[i - 1][2]
        res_a = dp[-1][2]
        # print(dp)

        # type b
        even = [a_list[i] for i in range(0, n, 2)]
        res_b = sum(even) - min(even)

        return max(res_a, res_b)


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(6, [1, 2, 3, 4, 5, 6]) == 12
    assert solve(5, [-1000, -100, -10, 0, 10]) == 0
    assert solve(10, [1000000000] * 10) == 5000000000


if __name__ == "__main__":
    test()
    main()