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

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] = -inf
    dp[0][2] = -inf
    dp[1][0] = -inf
    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
"""

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] = -inf
    dp[0][2] = -inf
    dp[1][0] = -inf
    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])
    if N%2==1:
        ans = max(dp[-1][0],dp[-1][1])
    else:
        ans = max(dp[-1][1],dp[-1][2])
    #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())
A = list(map(int, input().split()))

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

Submission status: Wrong Answer

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

N = Int()
A = IntList()

Even = A[::2]
Odd = A[1::2]

RE = [0]
RO = [0]

for i in Even:
    RE.append(RE[-1]+i)
    
for i in Odd:
    RO.append(RO[-1]+i)

if N%2==0:
    EtoR = []
    for i in range(N//2+1):
        EtoR.append(RE[i]+RO[N//2]-RO[i])
    print(max(EtoR))

Submission status: Wrong Answer

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

N = Int()
A = IntList()

Even = A[::2]
Odd = A[1::2]

RE = [0]
RO = [0]

for i in Even:
    RE.append(RE[-1]+i)
    
for i in Odd:
    RO.append(RO[-1]+i)

if N%2==0:
    EtoR = []
    for i in range(N//2+1):
        EtoR.append(RE[i]+RO[N//2]-RO[i])
    print(max(EtoR))
else:
    OtoE = []
    for i in range((N-1)//2):
        OtoE.append(RO[i+1]+RE[(N+1)//2]-RE[i+2])
    MOtoE = [0]
    for i in OtoE[::-1]:
        MOtoE.append(max(MOtoE[-1],i))
    MOtoE = MOtoE[::-1]
    
    ans = MOtoE[0]
    for i in range((N+1)//2):
        ans = max(ans, RE[i]+MOtoE[i]-RO[i])
    for i in Even:
        ans = max(ans, RE[-1]-i)
    print(ans)

Submission status: Wrong Answer

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

is_odd = True

if n % 2 == 0:
    is_odd = False

if is_odd == True:
    dp = [[0 for i in range(3)] for j in range(n)]
else:
    dp = [[0 for i in range(2)] for j in range(n)]

if n == 3:
    print(max(ai[0],ai[2],ai[1]))
    exit()
elif n == 2:
    print(max(ai[0],ai[1]))
    exit()
    

if is_odd == True:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
        dp[i][2] = max(dp[i-4][0]+ai[i],dp[i-3][1]+ai[i],dp[i-2][2]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))
else:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1]))

Submission status: Wrong Answer

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

is_odd = True

if n % 2 == 0:
    is_odd = False

if is_odd == True:
    dp = [[0 for i in range(3)] for j in range(n)]
else:
    dp = [[0 for i in range(2)] for j in range(n)]

if n == 3:
    print(max(ai[0]+ai[2],ai[1]))
    exit()
elif n == 2:
    print(max(ai[0],ai[1]))
    exit()
    

if is_odd == True:
    dp[0][0] = ai[0]
    dp[1][1] = ai[1]
    dp[2][0] = ai[0]+ai[2]
    dp[2][2] = ai[2]
    dp[3][1] = max(ai[0]+ai[3],ai[1]+ai[3])    
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
        dp[i][2] = max(dp[i-4][0]+ai[i],dp[i-3][1]+ai[i],dp[i-2][2]+ai[i])
    print(max(dp[n-3][0],dp[n-2][1],dp[n-1][2]))
else:
    dp[0][0] = ai[0]
    dp[1][1] = ai[1]
    dp[2][0] = ai[0]+ai[2]       
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
    print(max(dp[n-2][0],dp[n-1][1]))

Submission status: Wrong Answer

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

is_odd = True

if n % 2 == 0:
    is_odd = False

if is_odd == True:
    dp = [[0 for i in range(3)] for j in range(n)]
else:
    dp = [[0 for i in range(2)] for j in range(n)]

if n == 3:
    print(max(ai[0]+ai[2],ai[1]))
    exit()
elif n == 2:
    print(max(ai[0],ai[1]))
    exit()
    

if is_odd == True:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
        dp[i][2] = max(dp[i-4][0]+ai[i],dp[i-3][1]+ai[i],dp[i-2][2]+ai[i])
    print(max(dp[n-3][0],dp[n-2][1],dp[n-1][2]))
else:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1]))

Submission status: Wrong Answer

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

is_odd = True

if n % 2 == 0:
    is_odd = False

if is_odd == True:
    dp = [[0 for i in range(3)] for j in range(n)]
else:
    dp = [[0 for i in range(2)] for j in range(n)]

if n == 3:
    print(max(ai[0]+ai[2],ai[1]))
    exit()
elif n == 2:
    print(max(ai[0],ai[1]))
    exit()

if is_odd == True:
    if n == 3:
        print(max(max(ai[0],ai[1]),ai[2]))
        exit()
    dp[0][0] = ai[0]
    dp[1][1] = ai[1]
    dp[2][0] = ai[0]+ai[2]
    dp[2][2] = ai[2]
    dp[3][1] = max(ai[0]+ai[3],ai[1]+ai[3])
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
        dp[i][2] = max(dp[i-4][0]+ai[i],dp[i-3][1]+ai[i],dp[i-2][2]+ai[i])
    print(max(dp[n-3][0],dp[n-2][0],dp[n-1][1],dp[n-1][2]))
else:
    dp[0][0] = ai[0]
    dp[1][1] = ai[1]
    dp[2][0] = ai[0]+ai[2]    
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1]))

Submission status: Wrong Answer

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

N = Int()
A = IntList()

Even = A[::2]
Odd = A[1::2]

RE = [0]
RO = [0]

for i in Even:
    RE.append(RE[-1]+i)
    
for i in Odd:
    RO.append(RO[-1]+i)

if N%2==0:
    EtoR = []
    for i in range(N//2+1):
        EtoR.append(RE[i]+RO[N//2]-RO[i])
    print(max(EtoR))
else:
    OtoE = []
    for i in range((N-1)//2):
        OtoE.append(RO[i+1]+RE[(N+1)//2]-RE[i+2])
    MOtoE = [0]
    for i in OtoE[::-1]:
        MOtoE.append(max(MOtoE[-1],i))
    MOtoE = MOtoE[::-1]
    
    ans = MOtoE[0]
    for i in range((N+1)//2):
        ans = max(ans, RE[i]+MOtoE[i]-RO[i])
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

def find(idx, c, arr, tb):

    if c == 0:
        return 0

    if idx <= 0 or idx < 2 * (c - 1):
        return -100000

    if (idx, c) in tb:
        return tb[(idx, c)]

    rs = find(idx - 2, c - 1, arr, tb) + arr[idx - 1]
    rs = max(rs, find(idx - 1, c, arr, tb))

    tb[(idx, c)] = rs
    return rs

def main():

    n = int(input())
    arr = [int(e) for e in input().split(' ')]
    print(find(n, n // 2, arr, {}))
    return 0


main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

def find(idx, c, arr, tb):

    if c == 0:
        return 0

    if idx <= 0 or idx < 2 * c - 1:
        return -100000

    if (idx, c) in tb:
        return tb[(idx, c)]

    rs = find(idx - 2, c - 1, arr, tb) + arr[idx - 1]
    rs = max(rs, find(idx - 1, c, arr, tb))

    tb[(idx, c)] = rs
    return rs

def main():

    n = int(input())
    arr = [int(e) for e in input().split(' ')]
    print(find(n, n // 2, arr, {}))
    return 0


main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())

_A = list(map(int, input().split()))

A1 = [0]
A2 = [0]
for i in range(0, len(_A),2):
    A1.append(A1[-1]+_A[i])
for i in range(1, len(_A),2):
    A2.append(A2[-1]+_A[i])

num = N // 2
max_val = 0
if N % 2 == 0:
    max_val = max([A1[-1], A2[-1]])
if N % 2 == 1:
    if num == 1:
        vals = _A
    else:
        for i in range(0, num+1):
            for s in range(0,num-i+1):
                val = A1[i] + A2[i+s] - A2[i] + A1[-1] - A1[i+s+1]
                if max_val < val:
                    max_val = val

print(max_val)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N = int(input())

_A = list(map(int, input().split()))
A1 = [0]
A2 = [0]
for i in range(0, len(_A),2):
    A1.append(A1[-1]+_A[i])
for i in range(1, len(_A),2):
    A2.append(A2[-1]+_A[i])

num = N // 2
vals = []
if N % 2 == 0:
    vals.append(A1[-1])
    vals.append(A2[-1])
if N % 2 == 1:
    if num == 1:
        vals = _A
    else:
        for i in range(0, num+1):
            for s in range(0,num-i+1):
                vals.append(A1[i] + A2[i+s] - A2[i] + A1[-1] - A1[i+s+1])

print(max(vals))

Submission status: Wrong Answer

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

# dp[i][k] 列iを選択し、k個持っているときの最大値
# kは(i-1)//2 or i//2 or (i+1)//2
# それぞれki=0,1,2とする。
# 最大でも4マス前まで(oxxxo)
# iが奇数
# dp[i+2][0]=Ai + max(dp[i][0], dp[i][1], dp[i-1][1],  dp[i-2][2])
# dp[i+2][1]=dp[i+2][0]
# dp[i+2][2]=Ai + max(dp[i][2])
# iが偶数
# dp[i+2][0]=0
# dp[i+2][1]=Ai + max(dp[i][1], dp[i][2], dp[i-1][2])
# dp[i+2][2]=dp[i+2][1]

dp = [[0 for i in range(3)] for j in range(n)]
ans = 0

dp[0][2] = a[0]
ans = dp[0][2]
dp[1][0] = 0
dp[1][1] = a[1]
dp[1][2] = a[1]
ans = max([ans, dp[1][1]])

if n == 2:
    print(ans)
else:
    for i in range(2, n):
        for j in range(3):
            if (i + 1) % 2 == 0:
                dp[i][0] = 0
                dp[i][1] = a[i] + max(dp[i - 2][1], dp[i - 3][2])
                dp[i][2] = dp[i][1]
            else:
                if i > 2:
                    dp[i][0] = a[i] + max(dp[i - 2][0], dp[i - 3][1], dp[i - 4][2])
                else:
                    dp[i][0] = a[i] + dp[i - 2][0]
                dp[i][1] = dp[i][0]
                dp[i][2] = a[i] + dp[i - 2][2]

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

Submission status: Wrong Answer

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

num = N // 2
vals = []
if N % 2 == 0:
    tmp = sum(A[1::2])
    vals.append(tmp)
    tmp = sum(A[2::2])
    vals.append(tmp)
if N % 2 == 1:
    pat1 = A[1::2]
    pat2 = A[2::2]
    pat3 = pat1[::-1]
    pat4 = pat2[::-1]
    if num == 1:
        vals = A
    else:
        for i in range(num+1):
            pat = pat1[0:i] + pat2[i:]
            vals.append(sum(pat))
            pat = pat3[0:i] + pat4[i:]
            vals.append(sum(pat))
        for i in range(1, num-1):
            for s in range(1,len(pat2)-i):
                vals.append(sum(pat1[0:s] + pat2[s:s+i] + pat1[s+i+1:]))

print(max(vals))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# coding: utf-8
import collections
import math
def debug(arg):
    if __debug__:
        pass
    else:
        import sys
        print(arg, file=sys.stderr)

N, *A = map(int, open(0).read().split())
a = dict(enumerate(A, 1))
dp = collections.defaultdict(int)
dp[1, 1] = a[1]
for i in range(2, N + 1):
    jj = range(max(math.floor(i // 2 - 1), 1), math.ceil((i + 1) // 2) + 1)
    debug(jj)
    for j in jj:
        x = dp[i - 2, j - 1] + a[i]
        y = dp[i - 1, j]
        dp[i, j] = max(x, y)
print(dp[N, N // 2])

Submission status: Wrong Answer

Solution code:
import collections
import math
 
N, *A = map(int, open(0).read().split())
a = dict(enumerate(A, 1))
dp = collections.defaultdict(int)
dp[1, 1] = a[1]
 
for i in range(2, N + 1):
    jj = range(math.floor(i // 2 - 1), math.ceil((i + 1) // 2) + 1)
    for j in jj:
        x = dp[i - 2, j - 1] + a[i]
        y = dp[i - 1, j]
        dp[i, j] = max(x, y)
 
print(dp[N, N // 2])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
x=0
y=0
for i in range(0,len(a),2):
  x+=a[i]
for i in range(1,len(a),2):
  y+=a[i]
if x>y:
  print(x)
else:
  print(y)

Submission status: Wrong Answer

Solution code:
n=int(input())

t = list(map(int, input().split()))
v1=v2=v3=0
if n==2:
	print(max(t))
else:
	v1 = t[0]
	v2 = max(t[:2])
	v3 = max(t[:3])
	for k in range(1, n//2):
		i = 2*k
		f1 = t[i] + v1
		f2 = max(f1, t[i+1] + max(v1, v2))
		f3 = v3
		if i+2<n : f3 = max(f2, t[i+2] + max(v1, v2, v3))
		v1 = f1
		v2 = f2
		v3 = f3
# ~ print(v1, v2, v3)
print(max(v2, v3))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
K = 2 if N%2 else 1
INF = float('inf')
dp = [[[-INF]*2 for _ in range(K+1)] for _ in range(N+1)]
dp[0][K][0] = 0 #dp[i][can_skip][must_skip]
for i,a in enumerate(A):
    for k in range(K,-1,-1):
        dp[i+1][k][0] = max(dp[i+1][k][0], dp[i][k][1])
        dp[i+1][k][1] = max(dp[i+1][k][1], dp[i][k][0] + a)
        if k:
            dp[i+1][k-1][0] = max(dp[i+1][k-1][0], dp[i][k][0])
print(max(max(row) for row in dp[-1]))

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007

def solve(N: int, A: "List[int]"):
    from collections import defaultdict
    M = N // 2
    def get_range(idx):
        r = (N - idx) // 2 + 1        
        return range(max(0, M-r), idx//2+1+1)
    
    dp_a = defaultdict(lambda:-float('inf'))
    dp_s = defaultdict(lambda:-float('inf'))
    dp_s[(0, -1)] = 0 
    dp_s[(-1, -1)] = 0
    for i in range(N):
        for j in get_range(i):
            dp_s[(j, i)] = max(dp_s[(j, i)], dp_a[(j, i-1)], dp_s[(j, i-1)])
            dp_a[(j, i)] = max(dp_a[(j, i)], dp_s[(j, i)], dp_s[(j-1, i-1)]+A[i])

    print(max(max(v for (i, j), v in dp_a.items() if i == M),
              max(v for (i, j), v in dp_s.items() if i == M)))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()