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())
an = list(map(int, input().split()))
dp = [[0 for i in range(3)] for j in range(n+1)]

for i in range(1, n+1):
    ai = an[i-1]
    if i % 2 == 0:
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        dp[i][1] = dp[i-1][1]+ai
    else:
        dp[i][2] = dp[i-1][2]+ai
        dp[i][1] = max(dp[i-1][2],dp[i-1][1])
# print(dp)
if n % 2 == 0:
    print(max(dp[n][0], dp[n][1]))
else:
    print(max(dp[n][2], dp[n][1]))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    N=int(input())
    A=list(map(int,input().split()))
    dp=[[-INF]*3 for _ in range(N+10)]
    dp[0][0]=0
    for i in range(N):
        for j in range(3):
            if j+1<3:
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j])
            dp[i+2][j]=max(dp[i+2][j],dp[i][j]+A[i])
    if N%2:
        print(dp[N+1][2])
    else:
        print(dp[N+1][1])
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
an = list(map(int, input().split()))
dp = [[0 for i in range(3)] for j in range(n+1)]

for i in range(1, n+1):
    ai = an[i-1]
    if i % 2 == 0:
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        dp[i][1] = dp[i-1][1]+ai
    else:
        dp[i][2] = dp[i-1][2]+ai
        dp[i][1] = max(dp[i-1][2],dp[i-1][1])
# print(dp)
print(max(dp[n]))

Submission status: Wrong Answer

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

dp0 = [-INF] * (N + 2)
dp1 = [-INF] * (N + 2)
dp2 = [-INF] * (N + 2)
dp0[0] = 0
dp1[0] = 0

for i, a in enumerate(A, start=2):
    dp0[i] = dp0[i - 2] + a
    dp1[i] = max(dp1[i - 2] + a, dp0[i - 1])
    dp2[i] = max(dp2[i - 2] + a, dp1[i - 1], dp0[i - 3])

if N % 2 == 1:
    print(dp2[-1])
else:
    print(max(dp1[-1], dp0[-1]))

Submission status: Wrong Answer

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

dp0 = [-INF] * (N + 2)
dp1 = [-INF] * (N + 2)
dp2 = [-INF] * (N + 2)
dp0[0] = 0
dp0[1] = 0

for i, a in enumerate(A, start=2):
    dp0[i] = dp0[i - 2] + a
    dp1[i] = max(dp1[i - 2] + a, dp0[i - 1])
    dp2[i] = max(dp2[i - 2] + a, dp1[i - 1], dp0[i - 2])

if N % 2 == 1:
    print(dp2[-1])
else:
    print(max(dp2[-1], dp1[-1], dp0[-1]))

Submission status: Wrong Answer

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

dp0 = [-INF] * (N + 2)
dp1 = [-INF] * (N + 2)
dp2 = [-INF] * (N + 2)
dp0[0] = 0
dp0[1] = 0

for i, a in enumerate(A, start=2):
    dp0[i] = dp0[i - 2] + a
    dp1[i] = max(dp1[i - 2] + a, dp0[i - 1])
    dp2[i] = max(dp2[i - 2] + a, dp1[i - 1])

if N % 2 == 1:
    print(dp2[-1])
else:
    print(max(dp2[-1], dp1[-1], dp0[-1]))

Submission status: Wrong Answer

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

dp0 = [-INF] * (N + 2)
dp1 = [-INF] * (N + 2)
dp2 = [-INF] * (N + 2)
dp0[0] = 0
dp0[1] = 0

for i, a in enumerate(A, start=2):
    dp0[i] = dp0[i - 2] + a
    dp1[i] = max(dp1[i - 2] + a, dp0[i - 1])
    dp2[i] = max(dp2[i - 2] + a, dp1[i - 1], dp0[i - 2])

if N % 2 == 1:
    print(dp2[-1])
else:
    print(max(dp1[-1], dp0[-2]))

Submission status: Wrong Answer

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

dp0 = [-INF] * (N + 2)
dp1 = [-INF] * (N + 2)
dp2 = [-INF] * (N + 2)
dp0[0] = 0
dp0[1] = 0

for i, a in enumerate(A, start=2):
    dp0[i] = dp0[i - 2] + a
    dp1[i] = max(dp1[i - 2] + a, dp0[i - 1])
    dp2[i] = max(dp2[i - 2] + a, dp1[i - 1], dp0[i - 2])

if N % 2 == 1:
    print(dp2[-1])
else:
    print(max(dp1[-1], dp0[-1]))

Submission status: Wrong Answer

Solution code:
NumSeq = int(input())
SeqList = list(map(int, input().split()))

if NumSeq % 2 == 0:
    even_sum = sum([SeqList[i] for i in range(NumSeq) if i % 2 == 0])
    odd_sum = sum([SeqList[i] for i in range(NumSeq) if i % 2 == 1])
    print(max(even_sum, odd_sum))
    exit()

left_even = [0] * NumSeq
left_odd = [0] * NumSeq
right_even = [0] * NumSeq
right_odd = [0] * NumSeq

left_even[0] = SeqList[0]
left_odd[1] = SeqList[1]
right_even[NumSeq-1] = SeqList[NumSeq-1]
right_odd[NumSeq-2] = SeqList[NumSeq-2]

for i in range(2, NumSeq):
    if i % 2 == 0:
        left_even[i] = left_even[i-2] + SeqList[i]
        right_even[NumSeq-1-i] = right_even[NumSeq-i+1] + SeqList[NumSeq-1-i]
    else:
        left_odd[i] = left_odd[i-2] + SeqList[i]
        right_odd[NumSeq-1-i] = right_odd[NumSeq-i+1] + SeqList[NumSeq-1-i]


max_sum = max(left_even[-3], left_odd[-2], right_even[2])

for i in range(1, NumSeq - 3):
    if i % 2 == 0:
        max_sum = max(max_sum, left_even[i] + right_odd[i+3], \
                                                 left_even[i] + right_even[i+4])
    else:
        max_sum = max(max_sum, left_odd[i] + right_even[i+3])
        
    if max_sum == 249:
        max_i = i

print(max_sum)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
if(N%2==0):
    res1,res2=0,0
    for i in range(N):
        if(i%2==0):
            res1+=A[i]
        else:
            res2+=A[i]
    print(max(res1,res2))
    exit()
    
dp=[[-10000,-10000,-10000] for i in range(N+20)]
for i in range(3):
    dp[0][i]=0
for i in range(3):
    dp[1][i]=A[0]
for i in range(3):
    dp[2][i]=A[1]
for i in range(N):
    if(0<=i-1):
        dp[i+1][0]=max(dp[i+1][0],dp[i-1][0]+A[i])
        dp[i+1][1]=max(dp[i+1][1],dp[i-1][1]+A[i])
        dp[i+1][2]=max(dp[i+1][2],dp[i-1][2]+A[i])
    if(0<=i-2):
        dp[i+1][1]=max(dp[i+1][1],dp[i-2][0]+A[i])
        dp[i+1][2]=max(dp[i+1][2],dp[i-2][1]+A[i])
    if(0<=i-3):
        dp[i+1][2]=max(dp[i+1][2],dp[i-3][0]+A[i])
    
print(max(dp[N-1][0],dp[N-1][1],dp[N][2]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N%2==0:
  oddsum=A[0]
  other=max(A[0],A[1])
  for i in range(1,N//2):
    oddsum+=A[2*i]
    other+=A[2*i+1]
    if oddsum>other:
      other=oddsum
  print(max(other,oddsum))
else:
  oddsum=A[0]
  evensum=max(A[0],A[1])
  other=max(A[0],A[1],A[2])
  for i in range(1,N//2):
    oddsum+=A[2*i]
    evensum+=A[2*i+1]
    other+=A[2*i+2]
    if evensum>other:
      other=evensum
  print(max(oddsum,evensum,other))

Submission status: Wrong Answer

Solution code:
N = int(input()) + 2
X = [0, 0] + list(map(int, input().split()))
dp = [[0, 0] for _ in range(N)]
for i in range(2, N):
    if i%2:
        dp[i][1] = max(dp[i-2][1] + X[i], dp[i-1][1])
        dp[i][0] = max(dp[i-2][0] + X[i], dp[i-1][0])
    else:
        dp[i][1] = dp[i-2][1] + X[i]
        dp[i][0] = max(dp[i-2][0] + X[i], dp[i-1][1])
if N%2:
    print(dp[-1][0])
else:
    print(dp[-1][1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int,input().split()))

    if n & 1 == 0:
        res = -INF
        score = sum(A[::2])
        for i in range(n-1,-1,-1):
            if i & 1:
                score += A[i]
            else:
                score -= A[i]
                res = max(res, score)
        print(res)
        return

    front_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(1, n, 2):
        choose, not_choose = max(choose, not_choose) + A[i], not_choose + A[i-1]
        front_dp[i] = max(choose, not_choose)

    back_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(n-2, -1, -2):
        choose, not_choose = max(choose, not_choose) + A[i], not_choose + A[i+1]
        back_dp[i] = max(choose, not_choose)

    res = -INF
    for i in range(1, n, 2):
        if i + 2 < n:
            res = max(res, front_dp[i] + back_dp[i+2])

    res = max(res, front_dp[-2])
    res = max(res, back_dp[1])

    score = sum(A[::2])
    score -= A[-1]
    res = max(res, score)

    for i in range(n-3, -1, -2):
        score -= A[i]
        score += A[i]
        res = max(res, score)

    score = sum(A[::2])
    score -= A[-1]
    res = max(res, score)
    for i in range(n-2, -1, -1):
        if i & 1:
            score += A[i]
        else:
            score -= A[i]
            res = max(res, score)

    A.reverse()
    score = sum(A[::2])
    score -= A[-1]
    res = max(res, score)
    for i in range(n-2, -1, -1):
        if i & 1:
            score += A[i]
        else:
            score -= A[i]
            res = max(res, score)

    if n <= 5:
        print(res)
        return

    A.reverse()
    score = sum(A[1::2])
    score += A[0]
    score += A[6]
    score -= A[1]
    score -= A[5]
    res = max(res, score)

    left = 3
    right = 6
    while right + 2 < n:
        score -= A[left]
        score -= A[right]
        left += 2
        right += 2
        score += A[left]
        score += A[right]
        res = max(res, score)

    print(res)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int,input().split()))

    if n & 1 == 0:
        res = -INF
        score = sum(A[::2])
        for i in range(n-1,-1,-1):
            if i & 1:
                score += A[i]
            else:
                score -= A[i]
                res = max(res, score)
        print(res)
        return

    front_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(1, n, 2):
        choose, not_choose = max(choose+A[i],not_choose+A[i]), not_choose + A[i-1]
        front_dp[i] = max(choose, not_choose)

    back_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(n-2, -1, -2):
        choose, not_choose = max(choose+A[i],not_choose+A[i]), not_choose + A[i+1]
        back_dp[i] = max(choose, not_choose)

    res = -INF
    for i in range(1, n, 2):
        if i + 2 < n:
            res = max(res, front_dp[i] + back_dp[i+2])

    res = max(res, front_dp[-2])
    res = max(res, back_dp[1])
    print(res)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int,input().split()))

    if n & 1 == 0:
        res = -INF
        score = sum(A[::2])
        for i in range(n-1,-1,-1):
            if i & 1:
                score += A[i]
            else:
                score -= A[i]
                res = max(res, score)
        print(res)
        return

    front_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(1, n, 2):
        choose, not_choose = max(choose+A[i],not_choose+A[i]), not_choose + A[i-1]
        front_dp[i] = max(choose, not_choose)

    back_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(n-2, -1, -2):
        choose, not_choose = max(choose+A[i],not_choose+A[i]), not_choose + A[i+1]
        back_dp[i] = max(choose, not_choose)

    res = -INF
    for i in range(1, n, 2):
        if i + 2 < n:
            res = max(res, front_dp[i] + back_dp[i])

    res = max(res, front_dp[-2])
    res = max(res, back_dp[1])
    print(res)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int,input().split()))


    if n & 1:
        front_dp = [None] * n
        choose = -INF
        not_choose = 0
        for i in range(1, n, 2):
            next_choose = max(choose + A[i], not_choose + A[i])
            next_not_choose = not_choose + A[i-1]
            choose = next_choose
            not_choose = next_not_choose
            front_dp[i] = max(choose, not_choose)

        back_dp = [None] * n
        choose = -INF
        not_choose = 0
        for i in range(n-2, -1 , -2):
            next_choose = max(choose + A[i], not_choose + A[i])
            next_not_choose = not_choose + A[i+1]
            choose = next_choose
            not_choose = next_not_choose
            back_dp[i] = max(choose, not_choose)

        res = 0
        for i in range(1, n, 2):
            if i + 2 < n:
                res = max(res, front_dp[i] + back_dp[i + 2])

        res = max(front_dp[-2], res)
        res = max(back_dp[1], res)
        print(res)
        return

    res = -INF
    score = sum(A[::2])
    res = max(res, score)
    for i in range(n-1, -1, -1):
        if i & 1:
            score += A[i]
        else:
            score -= A[i]
            res = max(res, score)

    print(res)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int,input().split()))

    if n & 1 == 0:
        print(max(sum(A[::2]), sum(A[1::2])))
        return

    front_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(1, n, 2):
        next_choose = max(choose + A[i], not_choose + A[i])
        next_not_choose = not_choose + A[i-1]
        choose = next_choose
        not_choose = next_not_choose
        front_dp[i] = max(choose, not_choose)

    back_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(n-2, -1 , -2):
        next_choose = max(choose + A[i], not_choose + A[i])
        next_not_choose = not_choose + A[i+1]
        choose = next_choose
        not_choose = next_not_choose
        back_dp[i] = max(choose, not_choose)

    res = 0
    for i in range(1, n, 2):
        if i + 2 < n:
            res = max(res, front_dp[i] + back_dp[i + 2])

    res = max(front_dp[-2], res)
    res = max(back_dp[1], res)
    print(res)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int,input().split()))

    if n & 1 == 0:
        print(max(sum(A[::2]), sum(A[1::2])))
        return

    front_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(1, n, 2):
        next_choose = max(choose + A[i], not_choose + A[i])
        next_not_choose = not_choose + A[i-1]
        choose = next_choose
        not_choose = next_not_choose
        front_dp[i] = max(choose, not_choose)

    back_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(n-2, -1 , -2):
        next_choose = max(choose + A[i], not_choose + A[i])
        next_not_choose = not_choose + A[i+1]
        choose = next_choose
        not_choose = next_not_choose
        back_dp[i] = max(choose, not_choose)


    res = 0
    for i in range(1, n-2, 2):
        res = max(res, front_dp[i] + back_dp[i + 2])

    res = max(front_dp[-2], res)
    res = max(front_dp[1], res)
    print(res)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int,input().split()))

    if n & 1 == 0:
        print(max(sum(A[::2]), sum(A[1::2])))
        return

    res = 0
    score = sum(A[::2])
    score -= A[-1]
    res = max(res, score)

    for i in range(n-3, -1, -2):
        score -= A[i]
        score += A[i]
        res = max(res, score)

    score = sum(A[::2])
    score -= A[-1]
    res = max(res, score)
    for i in range(n-2, -1, -1):
        if i & 1:
            score += A[i]
        else:
            score -= A[i]
            res = max(res, score)

    A.reverse()
    score = sum(A[::2])
    score -= A[-1]
    res = max(res, score)
    for i in range(n-2, -1, -1):
        if i & 1:
            score += A[i]
        else:
            score -= A[i]
            res = max(res, score)

    if n <= 5:
        print(res)
        return

    A.reverse()
    score = sum(A[1::2])
    score += A[0]
    score += A[6]
    score -= A[1]
    score -= A[5]
    res = max(res, score)

    left = 3
    right = 6
    while right + 2 < n:
        score -= A[left]
        score -= A[right]
        left += 2
        right += 2
        score += A[left]
        score += A[right]
        res = max(res, score)


    front_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(1, n, 2):
        next_choose = max(choose + A[i], not_choose + A[i])
        next_not_choose = not_choose + A[i-1]
        choose = next_choose
        not_choose = next_not_choose
        front_dp[i] = max(choose, not_choose)

    back_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(n-2, -1 , -2):
        next_choose = max(choose + A[i], not_choose + A[i])
        next_not_choose = not_choose + A[i+1]
        choose = next_choose
        not_choose = next_not_choose
        back_dp[i] = max(choose, not_choose)

    res = 0
    for i in range(1, n-2, 2):
        res = max(res, front_dp[i] + back_dp[i+2])
    
    print(res)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int,input().split()))

    if n & 1 == 0:
        print(max(sum(A[::2]), sum(A[1::2])))
        return

    front_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(1, n, 2):
        next_choose = max(choose + A[i], not_choose + A[i])
        next_not_choose = not_choose + A[i-1]
        choose = next_choose
        not_choose = next_not_choose
        front_dp[i] = max(choose, not_choose)

    back_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(n-2, -1 , -2):
        next_choose = max(choose + A[i], not_choose + A[i])
        next_not_choose = not_choose + A[i+1]
        choose = next_choose
        not_choose = next_not_choose
        back_dp[i] = max(choose, not_choose)

    res = 0
    for i in range(1, n-2, 2):
        res = max(res, front_dp[i] + back_dp[i+2])
    print(res)
resolve()

Submission status: Wrong Answer

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

if N % 2 == 0:
    dp = [[[0, 0] for j in range(2)] for i in range(N)]

    for i, a in enumerate(aa):
        dp[i][0][1] = dp[i - 1][0][0] + a
        dp[i][0][0] = dp[i - 1][0][1]

        dp[i][1][0] = max(dp[i - 1][1][1], dp[i - 1][0][0])
        dp[i][1][1] = dp[i - 1][1][0] + a

    print(max(max(dp[-1][0]), dp[-1][1][1]))
else:
    dp = [[[0, 0] for j in range(3)] for i in range(N)]

    for i, a in enumerate(aa):
        dp[i][0][1] = dp[i - 1][0][0] + a
        dp[i][0][0] = dp[i - 1][0][1]

        dp[i][1][0] = max(dp[i - 1][1][1], dp[i - 1][0][0])
        dp[i][1][1] = dp[i - 1][1][0] + a

        dp[i][2][0] = max(dp[i - 1][2][1], dp[i - 1][1][0])
        dp[i][2][1] = dp[i - 1][2][0] + a

    print(max(max(dp[-1][1]), dp[-1][2][1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 18
if n % 2:
    dp = [[[-INF,-INF,-INF] for i in range(2)] for i in range(n+1)]
    dp[0][0][0] = 0
    # 初期化条件考える
    for i,v in enumerate(a):
        for j in range(2):
            if j:
                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])
            else:
                dp[i+1][1][0] = max(dp[i+1][1][0],dp[i][0][0] + v)
                dp[i+1][0][1] = max(dp[i+1][0][1],dp[i][0][0])
                dp[i+1][1][1] = max(dp[i+1][1][1],dp[i][0][1] + v)
                dp[i+1][0][2] = max(dp[i+1][0][2],dp[i][0][1])
                dp[i+1][1][2] = max(dp[i+1][1][2],dp[i][0][2] + v)
    print(max(max(dp[n][0]),max(dp[n][1])))
else:
    odd_sum,even_sum = 0,0
    cumsum = []
    for k,v in enumerate(a):
        if k % 2:
            odd_sum += v
            cumsum.append(odd_sum)
        else:
            even_sum += v
            cumsum.append(even_sum)
    ans = max(cumsum[n-2],cumsum[n-1])
    for i in range(2,n,2):
        ans = max(ans, cumsum[i-2]+cumsum[n-1]-cumsum[i-1])
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**18
 
n = int(input())
a = [int(item) for item in input().split()]
 
 
# dp[i-th][wait num][used / not used]
dp = [[[-INF] * 2 for _ in range(3)] for _ in range(n+1)]
dp[0][0][0] = 0
 
for i in range(n):
    # use i
    for j in range(3):
        dp[i+1][j][1] = max(dp[i+1][j][1] ,dp[i][j][0] + a[i])
    # skip i
    for j in range(2):
        dp[i+1][j+1][0] = max(dp[i+1][j+1][0] ,dp[i][j][0])
    # not use i
    for j in range(3):
        dp[i+1][j][0] = max(dp[i][j][1], dp[i+1][j][0])
 
ans = -INF
if n % 2 == 0:
    ans = max(dp[-1][1][1], ans)
    ans = max(dp[-1][0][0], ans)
else:
    ans = max(dp[-1][2][1], ans)
    ans = max(dp[-1][1][0], ans)
    # Take ceil(n // 2) items in even case
    ans = max(ans, sum(a[0::2]))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**18
 
n = int(input())
a = [int(item) for item in input().split()]
 
 
# dp[i-th][wait num][used / not used]
dp = [[[-INF] * 2 for _ in range(3)] for _ in range(n+1)]
dp[0][0][0] = 0
 
for i in range(n):
    # use in i
    for j in range(3):
        dp[i+1][j][1] = max(dp[i+1][j][1] ,dp[i][j][0] + a[i])
    # rest in i
    for j in range(2):
        dp[i+1][j+1][0] = max(dp[i+1][j+1][0] ,dp[i][j][0])
    # not use in i
    for j in range(3):
        dp[i+1][j][0] = max(dp[i][j][1], dp[i+1][j][0])
 
ans = -INF
if n % 2 == 0:
    ans = max(dp[-1][1][1], ans)
    ans = max(dp[-1][0][0], ans)
else:
    ans = max(dp[-1][2][1], ans)
    ans = max(dp[-1][1][0], ans)
    ans = max(ans, sum(a[0::2]))
print(ans)

Submission status: Wrong Answer

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

if n%2 == 0:
    a1 = []
    a2 = []
    for i in range(int(n/2)):
        a1.append(a[2*i])
        a2.append(a[2*i +1])
    print(max(sum(a1),sum(a2)))

u = []
if n%2 == 1:
    for i in range(n):
        a1 = []
        a2 = []
        copy = list(a)
        del copy[i]
        for j in range(int((n-1)/2)):
            a1.append(copy[2*j])
            a2.append(copy[2*j +1])
        u.append(max(sum(a1),sum(a2)))
    print(max(u))

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	n = II()
	a = LI()
	a = [0]+a
	dp_t = defaultdict(lambda: -10**9-1)
	dp_f =  defaultdict(lambda: -10**9-1)
	dp_f[(0,0)]=0
	for i in range(1,n+1):
		dp_f[(i,(i-1)//2)]=max(dp_f[(i-1,(i-1)//2)], dp_t[(i-1,(i-1)//2)])
		dp_t[(i,(i-1)//2)]=dp_f[(i-1,(i-1)//2-1)]+a[i]
		dp_f[(i,(i-1)//2+1)]=max(dp_f[(i-1,(i-1)//2+1)], dp_t[(i-1,(i-1)//2+1)])
		dp_t[(i,(i-1)//2+1)]=dp_f[(i-1,(i-1)//2)]+a[i]
	print(max(dp_t[(n,n//2)],dp_f[(n,n//2)]))
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 20
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
from collections import defaultdict
dy = (-1,0,1,0)
dx = (0,1,0,-1)

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

    dp = [{(i - 1)//2: -INF, (i + 1)//2: -INF} for i in range(n + 1)]
    dp[0][0] = 0
    dp[1][0] = 0
    dp[1][1] = a[0]
    for i in range(1,n):
        if i%2 == 1:
            m1,m2 = (i + 2)//2,i//2
            dp[i + 1][m1] = max(dp[i - 1][m1 - 1] + a[i],dp[i][m1])
            dp[i + 1][m2] = max(dp[i - 1][m2 - 1] + a[i],dp[i][m2])
        else:
            m1,m2 = (i + 1)//2,i//2
            dp[i + 1][m1] = dp[i - 1][m1 - 1] + a[i]
            dp[i + 1][m2] = max(dp[i - 1][m2 - 1] + a[i],dp[i][m2])

    print(dp[n][(n//2)])

if __name__ =='__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()
if n % 2:
    dp = [[0] * n for _ in range(3)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for i in range(2, n):
        if i % 2 == 0:
            dp[0][i] = dp[0][i - 2] + A[i]
        if i % 2 and i >= 3:
            dp[1][i] = max(dp[1][i - 2], dp[0][i - 3]) + A[i]
        if i % 2 == 0 and i >= 4:
            dp[2][i] = max(dp[2][i - 2], dp[1][i - 3], dp[0][i - 4]) + A[i]
    print(max(dp[2][n - 1], dp[1][n - 2], dp[0][n - 3]))
else:
    dp = [0] * n
    dp[0] = A[0]
    dp[1] = A[1]
    for i in range(2, n):
        ret = dp[i - 2] + A[i]
        if i >= 3:
            ret = max(ret, dp[i - 3] + A[i])
        dp[i] = ret
    print(max(dp[-1], dp[-2]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()
dp = [0] * n
if n % 2:
    dp = [[0] * n for _ in range(3)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for i in range(2, n):
        if i % 2 == 0:
            dp[0][i] = dp[0][i - 2] + A[i]
        if i % 2 and i >= 3:
            dp[1][i] = max(dp[1][i - 2], dp[0][i - 3]) + A[i]
        if i % 2 == 0 and i >= 4:
            dp[2][i] = max(dp[2][i - 2], dp[1][i - 3], dp[0][i - 4]) + A[i]
    print(max(dp[2][n - 1], dp[1][n - 2], dp[0][n - 3]))
else:
    for i in range(n):
        ret = A[i]
        if i >= 2:
            ret = max(ret, dp[i - 2] + A[i])
        if i >= 3:
            ret = max(ret, dp[i - 3] + A[i])
        dp[i] = ret
    print(max(dp[-1], dp[-2]))