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())
A = list(map(int, input().split()))

ans = 0

A_even = A[0::2] # 0,2,4... (奇数のときn+1個)
A_odd  = A[1::2] # 1,3,5... (奇数のときn個)

A_even_sum = [0 for i in range(len(A_even))]
A_odd_sum  = [0 for i in range(len(A_odd))]

for i in range(len(A_even)):
    if(i==0):
        A_even_sum[i] = A_even[i]
    else:
        A_even_sum[i] = A_even_sum[i-1] + A_even[i]

for i in range(len(A_odd)):
    if(i==0):
        A_odd_sum[i] = A_odd[i]
    else:
        A_odd_sum[i] = A_odd_sum[i-1] + A_odd[i]

if(N%2 == 0):
    # 偶数個の場合 例 [0 2 4] [1 3 5]
    n = int(N/2)

    # A_evenの(0からi-1まで)、A_oddから(iからn-1まで)を選択する
    ans = max(A_even_sum[n-1],A_odd_sum[n-1])
    if(n >= 2):
        for i in range(1,n):
            new_ans = A_even_sum[i-1] + A_odd_sum[n-1] - A_odd_sum[i-1]
            if(new_ans > ans):
                ans = new_ans
                
else:
    # 奇数個の場合 例 [0 2 4 6] [1 3 5]
    n = int((N-1)/2)
    
    # 1.A_evenのみから選択→最も小さい1個を除外したものが最適
    if(n == 1):
        ans = max(A)
    else:
        ans = A_even_sum[n] - min(A_even)
    
    # 1-1. A_oddのみから全部選択
    ans = max(ans,A_odd_sum[n-1])
    
    # 2.A_even(0からn_s-1まで) → A_odd(n_sからn_eまで) → A_even(n_e+2からnまで) と選択する
    # n_s≧1, n_e≦n-2, n_e＞n_s
    
    if(n >= 3):
        flag = 0
        ans2 = 0
        n_e_max = 0
        
        # まず、n_s=1とおいて、A_oddの終点を定める
        n_s = 1
        for n_e in range(2,n-1):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e+1] + A_odd_sum[n_e] - A_odd_sum[n_s-1]
            if(flag == 0):
                flag = 1
                n_e_max = n_e
                ans2 = new_ans2
            elif(new_ans2 > ans2):
                n_e_max = n_e
                ans2 = new_ans2
        
        # 次に、n_sを変化させて考える
        for n_s in range(1,n_e_max):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e_max+1] + A_odd_sum[n_e_max] - A_odd_sum[n_s-1]
            if(new_ans2 > ans2):
                ans2 = new_ans2
        
        ans = max(ans,ans2)
        
        
print(ans)

Submission status: Wrong Answer

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

ans = 0

A_even = A[0::2] # 0,2,4... (奇数のときn+1個)
A_odd  = A[1::2] # 1,3,5... (奇数のときn個)

A_even_sum = [0 for i in range(len(A_even))]
A_odd_sum  = [0 for i in range(len(A_odd))]

for i in range(len(A_even)):
    if(i==0):
        A_even_sum[i] = A_even[i]
    else:
        A_even_sum[i] = A_even_sum[i-1] + A_even[i]

for i in range(len(A_odd)):
    if(i==0):
        A_odd_sum[i] = A_odd[i]
    else:
        A_odd_sum[i] = A_odd_sum[i-1] + A_odd[i]

if(N%2 == 0):
    # 偶数個の場合
    n = int(N/2)

    # A_evenの(0からi-1まで)、A_oddから(iからn-1まで)を選択する
    ans = max(A_even_sum[n-1],A_odd_sum[n-1])
    if(n >= 2):
        for i in range(1,n):
            new_ans = A_even_sum[i-1] + A_odd_sum[n-1] - A_odd_sum[i-1]
            if(new_ans > ans):
                ans = new_ans
                
else:
    # 奇数個の場合
    n = int((N-1)/2)
    
    # 1.A_evenのみから選択→最も小さい1個を除外したものが最適
    if(n == 1):
        ans = max(A)
    else:
        ans = A_even_sum[n] - min(A_even)
    
    # 1-1. A_oddのみから全部選択
    ans = max(ans,A_odd_sum[n-1])
    
    # 2.A_even(0からn_s-1まで) → A_odd(n_sからn_e-1まで) → A_even(n_e+1からnまで) と選択する
    # n_s≧1, n_e≦n-1, n_e＞n_s
    
    if(n >= 3):
        flag = 0
        ans2 = 0
        n_e_max = 0
        
        # まず、n_s=1とおいて、A_oddの終点を定める
        n_s = 1
        for n_e in range(2,n):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e] + A_odd_sum[n_e-1] - A_odd_sum[n_s-1]
            if(flag == 0):
                flag = 1
                n_e_max = n_e
                ans2 = new_ans2
            elif(new_ans2 > ans2):
                n_e_max = n_e
                ans2 = new_ans2
        
        # 次に、n_sを変化させて考える
        for n_s in range(1,n_e_max):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e_max] + A_odd_sum[n_e_max-1] - A_odd_sum[n_s-1]            
            if(new_ans2 > ans2):
                ans2 = new_ans2
        
        ans = max(ans,ans2)
        
        
print(ans)

Submission status: Wrong Answer

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

ans = 0

A_even = A[0::2] # 0,2,4... (奇数のときn+1個)
A_odd  = A[1::2] # 1,3,5... (奇数のときn個)

A_even_sum = [0 for i in range(len(A_even))]
A_odd_sum  = [0 for i in range(len(A_odd))]

for i in range(len(A_even)):
    if(i==0):
        A_even_sum[i] = A_even[i]
    else:
        A_even_sum[i] = A_even_sum[i-1] + A_even[i]

for i in range(len(A_odd)):
    if(i==0):
        A_odd_sum[i] = A_odd[i]
    else:
        A_odd_sum[i] = A_odd_sum[i-1] + A_odd[i]

if(N%2 == 0):
    # 偶数個の場合
    n = int(N/2)

    # A_evenの(0からi-1まで)、A_oddから(iからn-1まで)を選択する
    ans = max(A_even_sum[n-1],A_odd_sum[n-1])
    if(n >= 2):
        for i in range(1,n):
            new_ans = A_even_sum[i-1] + A_odd_sum[n-1] - A_odd_sum[i-1]
            if(new_ans > ans):
                ans = new_ans
                
else:
    # 奇数個の場合
    n = int((N-1)/2)
    
    # 1.A_evenのみから選択→最も小さい1個を除外したものが最適
    if(n == 1):
        ans = max(A)
    else:
        ans = A_even_sum[n] - min(A_even)

    # 2.A_even(0からn_s-1まで) → A_odd(n_sからn_e-1まで) → A_even(n_e+1からnまで) と選択する
    # n_s≧1, n_e≦n-1, n_e＞n_s
    
    if(n >= 3):
        flag = 0
        ans2 = 0
        n_e_max = 0
        
        # まず、n_s=1とおいて、A_oddの終点を定める
        n_s = 1
        for n_e in range(2,n):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e] + A_odd_sum[n_e-1] - A_odd_sum[n_s-1]
            if(flag == 0):
                flag = 1
                n_e_max = n_e
                ans2 = new_ans2
            elif(new_ans2 > ans2):
                n_e_max = n_e
                ans2 = new_ans2
        
        # 次に、n_sを変化させて考える
        for n_s in range(1,n_e_max):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e_max] + A_odd_sum[n_e_max-1] - A_odd_sum[n_s-1]            
            if(new_ans2 > ans2):
                ans2 = new_ans2
        
        ans = max(ans,ans2)
        
        
print(ans)

Submission status: Wrong Answer

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

ans = 0

A_even = A[0::2] # 0,2,4... (奇数のときn+1個)
A_odd  = A[1::2] # 1,3,5... (奇数のときn個)

A_even_sum = [0 for i in range(len(A_even))]
A_odd_sum  = [0 for i in range(len(A_odd))]

for i in range(len(A_even)):
    if(i==0):
        A_even_sum[i] = A_even[i]
    else:
        A_even_sum[i] = A_even_sum[i-1] + A_even[i]

for i in range(len(A_odd)):
    if(i==0):
        A_odd_sum[i] = A_odd[i]
    else:
        A_odd_sum[i] = A_odd_sum[i-1] + A_odd[i]

if(N%2 == 0):
    # 偶数個の場合
    n = int(N/2)

    # A_evenの(0からi-1まで)、A_oddから(iからn-1まで)を選択する
    ans = max(A_even_sum[n-1],A_odd_sum[n-1])
    if(n >= 2):
        for i in range(1,n):
            new_ans = A_even_sum[i-1] + A_odd_sum[n-1] - A_odd_sum[i-1]
            if(new_ans > ans):
                ans = new_ans
                
else:
    # 奇数個の場合
    n = int((N-1)/2)
    
    # 1.A_evenのみから選択→最も小さい1個を除外したものが最適
    if(n == 1):
        ans = A[0] + A[2]
    else:
        ans = sum(A_even[0:(n+1)])-min(A_even)            

    # 2.A_even(0からn_s-1まで) → A_odd(n_sからn_e-1まで) → A_even(n_e+1からnまで) と選択する
    # n_s≧1, n_e≦n-1, n_e＞n_s
    
    if(n >= 3):
        flag = 0
        ans2 = 0
        n_e_max = 0
        
        # まず、n_s=1とおいて、A_oddの終点を定める
        n_s = 1
        for n_e in range(2,n):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e] + A_odd_sum[n_e-1] - A_odd_sum[n_s-1]
            if(flag == 0):
                flag = 1
                n_e_max = n_e
                ans2 = new_ans2
            elif(new_ans2 > ans2):
                n_e_max = n_e
                ans2 = new_ans2
        
        # 次に、n_sを変化させて考える
        for n_s in range(1,n_e_max):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e_max] + A_odd_sum[n_e_max-1] - A_odd_sum[n_s-1]            
            if(new_ans2 > ans2):
                ans2 = new_ans2
        
        ans = max(ans,ans2)
        
        
print(ans)

Submission status: Wrong Answer

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

ans = 0

A_even = A[0::2] # 0,2,4... (奇数のときn+1個)
A_odd  = A[1::2] # 1,3,5... (奇数のときn個)

A_even_sum = [0 for i in range(len(A_even))]
A_odd_sum  = [0 for i in range(len(A_odd))]

for i in range(len(A_even)):
    if(i==0):
        A_even_sum[i] = A_even[i]
    else:
        A_even_sum[i] = A_even_sum[i-1] + A_even[i]

for i in range(len(A_odd)):
    if(i==0):
        A_odd_sum[i] = A_odd[i]
    else:
        A_odd_sum[i] = A_odd_sum[i-1] + A_odd[i]

if(N%2 == 0):
    # 偶数個の場合
    n = int(N/2)

    # A_evenの(0からi-1まで)、A_oddから(iからn-1まで)を選択する
    ans = max(A_even_sum[n-1],A_odd_sum[n-1])
    if(n >= 2):
        for i in range(1,n):
            new_ans = A_even_sum[i-1] + A_odd_sum[n-1] - A_odd_sum[i-1]
            if(new_ans > ans):
                ans = new_ans
                
else:
    # 奇数個の場合
    n = int((N-1)/2)
    
    # 1.A_evenのみから選択→最も小さい1個を除外したものが最適
    if(n == 1):
        ans = A[0] + A[2]
    else:
        ans = sum(A_even[0:(n+1)])-min(A_even)            

    # 2.A_even(0からn_s-1まで) → A_odd(n_sからn_e-1まで) → A_even(n_e+1からnまで) と選択する
    # n_s≧1, n_e≦n-1, n_e＞n_s
    
    if(n >= 3):
        flag = 0
        ans2 = 0
        n_e_max = 0
        
        # まず、n_s=1とおいて、A_oddの終点を定める
        n_s = 1
        for n_e in range(2,n):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e] + A_odd_sum[n_e-1] - A_odd_sum[n_s-1]
            if(flag == 0):
                flag = 1
                n_e_max = n_e
                ans2 = new_ans2
            elif(new_ans2 > ans2):
                n_e_max = n_e
                ans2 = new_ans2
        
        # 次に、n_sを変化させて考える
        for n_s in range(1,n_e_max):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e_max] + A_odd_sum[n_e_max-1] - A_odd_sum[n_s-1]            
            if(new_ans2 > ans2):
                n_e_max = n_e
                ans2 = new_ans2
        
        ans = max(ans,ans2)
        
        
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])))
else:
    # oを選択 xを非選択とする　左から見て
    # 二回連続xはまだきてなく　x,xで終わり o,oで終わり
    # 二回連続xはすでにあり ox,xで終わり oo,oで終わり
    # 三回連続xがいずれかにあり
    x,o,xx,xo=a[0],a[1],0,-10**9
    for i in a[2:-1]:
        x,o,xx,xo=o,x+i,max(x,xo),xx+i
    s=sum(a[::2])
    li=[s-i for i in a[::2]]
    print(max(x,xx,xo))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
iseven=(n%2==0)

if n==2:
    exit()
dp = [[-float("inf") for _ in range(3)] for _ in range(n)]
dp[0][0]=a[0]
dp[1][1]=a[1]
if n>2:
    dp[2][2]=a[2]

for i in range(n):
    for k in range(3):
        if i+2<n:
            dp[i+2][k] = max(dp[i+2][k], dp[i][k] + a[i+2])
        if k<=1 and i+3<n:
            dp[i+3][k+1] = max(dp[i+3][k+1], dp[i][k] + a[i+3])
        if not iseven and k==0 and i+4<n:
            dp[i+4][k+2] = max(dp[i+4][k+2], dp[i][k] + a[i+4])


if iseven:
    ans=max([dp[-1][0],dp[-1][1]])
else:
    ans=max([dp[-3][0],dp[-2][1],dp[-1][2]])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
iseven=(n%2==0)

dp = [[-float("inf") for _ in range(3)] for _ in range(n)]
dp[0][0]=a[0]
dp[1][1]=a[1]
if n>2:
    dp[2][2]=a[2]

for i in range(n):
    for k in range(3):
        if i+2<n:
            dp[i+2][k] = max(dp[i+2][k], dp[i][k] + a[i+2])
        if k<=1 and i+3<n:
            dp[i+3][k+1] = max(dp[i+3][k+1], dp[i][k] + a[i+3])
        if not iseven and k==0 and i+4<n:
            dp[i+4][k+2] = max(dp[i+4][k+2], dp[i][k] + a[i+4])


if iseven:
    ans=max([dp[-1][0],dp[-1][1]])
else:
    ans=max([dp[-3][0],dp[-2][1],dp[-1][2]])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
inf = float('inf')
ans = -1 *inf

if N % 2 == 0:
    S_odd = [0]*(N//2+1)
    S_even = [0]*(N//2+1)
    s_odd = 0
    s_even = 0
    for i in range(len(A)):
        if i%2 == 0:
            s_odd += A[i]
            S_odd[i//2+1] = s_odd
        else:
            s_even += A[i]
            S_even[i//2+1] = s_even
    
    s = 0
    for j in range(N//2+1):
        s = S_odd[j] + S_even[N//2]-S_even[j] 
        ans = max(ans,s)
else:
    # S_odd = [0]*(N//2+2)
    # S_even = [0]*(N//2+1)
    # odd = []
    # even = []
    # s_odd = 0
    # s_even = 0
    # for i in range(len(A)):
    #     if i%2 == 0:
    #         s_odd += A[i]
    #         S_odd[i//2+1] = s_odd
    #         odd.append(A[i])
    #     else:
    #         s_even += A[i]
    #         S_even[i//2+1] = s_even
    #         even.append(A[i])
    
    # s = 0
    # ans = sum(odd)

    # for j in range(N//2):
    #     for k in range(j,N//2):
    #         s = S_odd[j] + S_even[k]-S_even[j] +S_odd[N//2+1]-S_odd[k+1]
    #         ans = max(ans,s)

    dp = [[0]*(N+1) for _ in range(N+1)]

    for i in range(1,N):
        for j in range((N-1)//2,(N+1)//2+1):
            dp[i+1][j] = max(dp[i][j],dp[i-1][j-1]+A[i])
    
    print(dp)
    print(dp[N][N//2])

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
if N % 2 == 0:
    x, y, px, py = 0, 0, 0, 0
    for a in A:
        x, y, px, py = px+a, max(x, py+a), x, y
    print(max(x, y))
else:
    x, y, z, px, py, pz = 0, 0, 0, 0, 0, 0
    for a in A:
        x, y, z, px, py, pz = px+a, max(x, py+a), max(x, y, pz+a), x, y, z
    print(max(x, y, z))

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:
    m = n//2
    INF = 10**18
    dp = [[-INF]*(m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in reversed(range(1, m+1)):
            if j == 1:
                dp[i][j] = max(dp[i-1][j], A[i-1])
                continue
            if 0 <= i-2:
                dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+A[i-1])
    print(dp[-1][m])

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:
    m = n//2
    INF = 10**18
    dp = [[-INF]*(m+1) for _ in range(2)]
    for i in range(1, n+1):
        for j in reversed(range(1, m+1)):
            if j == 1:
                dp[i % 2][j] = max(dp[i % 2-1][j], A[i-1])
                continue
            if 0 <= i-2:
                dp[i % 2][j] = max(dp[i % 2-1][j], dp[i % 2][j-1]+A[i-1])
    print(dp[-1][m])

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
inf=float("inf")
DP=[[-inf]*4 for _ in range(n+1)]
DP[0][2]=0
for i,a in enumerate(A):
  if (i+1)%2==0:
    DP[i+1][0]=DP[i][3]+a
    if i>=1:
      DP[i+1][0]=max(DP[i+1][0],DP[i-1][2]+a)
    DP[i+1][2]=DP[i][0]
    DP[i+1][3]=max(DP[i][1],DP[i][3])
    if i>=1:
      DP[i+1][3]=max(DP[i+1][3],DP[i-1][2])
  else:
    DP[i+1][0]=DP[i][2]+a
    DP[i+1][1]=DP[i][3]+a
    DP[i+1][3]=max(DP[i][0],DP[i][2])
print(max(DP[n][0],DP[n][1]))

Submission status: Wrong Answer

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

num = 0
n = N // 2

for i in range(n):
    num += data[i*2]    

ans = num

if N % 2 == 0:
    for i in range(n):
        num = num + data[N-1-2*i] - data[N-2-2*i]
        ans = max(ans, num)
else:
    for i in range(n):
        num = num + data[N-1-2*i] - data[N-3-2*i]
        ans = max(ans, num)
        temp = num
        for j in range(i+1, n):
            temp = temp + data[N-2-2*j] - data[N-3-2*j]
            ans = max(ans, temp)

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = list(map(int,input().split()))
dp0 = [0] * (n+11)
dp1 = [0] * (n+11)
dp2 = [0] * (n+11)
for i,ai in enumerate(A):
  dp2[i+11] = (max(dp0[i+7] + ai, dp1[i+8] + ai, dp2[i+9] + ai) if i >= 2 else 0)
  dp1[i+11] = (max(dp0[i+8] + ai, dp1[i+9] + ai) if i >= 1 else 0)
  dp0[i+11] = dp0[i+9] + ai 
if n % 2 == 0:
  print(dp1[n + 10])
else:
  print(dp2[n + 10])

# debug
# print(dp0,dp1,dp2,sep="\n")

Submission status: Wrong Answer

Solution code:
n=int(input())
A=sorted(list(map(int,input().split())),reverse=True)
li=[]
for i in range(n//2):
  li.append(A[2*i])
print(sum(li))

Submission status: Wrong Answer

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

# dp = [[-10**9] * 4 for _ in range(200005)]
# k = 1 + N % 2
# dp[0][0] = 0
# for i in range(N):
#     for j in range(k+1):
#         dp[i+1][j+1] = max(dp[i][j], dp[i+1][j+1])
#         now = dp[i][j]
#         if (i+j) % 2 == 0: now += A[i]
#         dp[i+1][j] = max(dp[i+1][j], now)

# print(dp[N][k])

Submission status: Wrong Answer

Solution code:
INF = -10000000001

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

a = int(n/2)

dpa = [[INF for j in range(a+1)] for i in range(n+1)]

dpa[0][0] = 0
for i in range(1,n+1):
	dpa[i][0] = 0
	if i % 2 == 0:
		j = int(i / 2)
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
	else:
		j = int((i-1)/2)
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
		if (i != n):
			j += 1
#			print(i,j,i-2,j-1,i-1,j)
			dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])

#print(dpa)
print(dpa[n][a])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)
INF = -10000000001

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

a = int(n/2)

dpa = [[INF for j in range(a+1)] for i in range(n+1)]

def dp(x,y):
	ret = 0
	if 2*y-1 > x:
		ret = INF
	elif 2*y-1 == x:
		for i in range(0,x,2):
			ret+= l[i]
	elif 2*y == x:
		z = 0
		o = 0
		for i in range(0,x,2):
			z+= l[i]

	elif y == 0:
		ret = 0
	else:
		if dpa[x][y] != INF:
			ret = dpa[x][y]
		else:
			ret = max(dp(x-2,y-1)+l[x-1],dp(x-1,y))
#			print(x,y,"->",x-2,y-1,x-1,y)
#	print(x,y,ret)
	dpa[x][y] = ret
	return ret

print(dp(n,a))

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

    dp = [[-inf]*3 for _ in range(N+1)]
    dp[0][0] = 0
    dp[0][1] = 0
    dp[0][2] = 0
    dp[1][0] = -inf
    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:
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()

    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] = -inf
    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
"""