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: Runtime Error

Solution code:
n=input()
List=list(map(int,input().split()))
def find(List):
    if len(List)==1:
        return(0)
    elif len(List)==2:
        if List[0] >= List[1]:
            return(int(List[0]))
        else:
            return(int(List[1]))
    elif len(List)==3:
        if (List[0]>=List[1] and List[0]>=List[2]):
            return(int(List[0]))
        elif(List[1]>=List[0] and List[1]>=List[2]):
            return(int(List[1]))
        else:
            return(int(List[2]))
    else:
        if len(List)%2==0:
            List2=[]
            sub1=int(List[len(List)-1])
            sub2=0
            for i in range(0,len(List)//2):
                sub2+=List[2*i]
            List.pop(len(List)-1)
            List.pop(len(List)-1)
            sub1+=find(List)
            if sub1 >= sub2:
                return(sub1)
            else:
                return(sub2)
        else:
            List2=[]
            List3=[]
            sub1=int(List[len(List)-1])
            sub2=int(List[len(List)-2])
            sub3=0
            for i in range(0,len(List)//2):
                sub3+=List[2*i]
            List.pop(len(List)-1)
            List.pop(len(List)-1)
            sub1+=find(List)
            List.pop(len(List)-1)
            sub2+=find(List)
            if (sub1>=sub2 and sub1>=sub3):
                return(sub1)
            elif(sub2>=sub1 and sub2>=sub3):
                return(sub2)
            else:
                return(sub3)
print(find(List))

Submission status: Runtime Error

Solution code:
n=input()
List=list(map(int,input().split()))
def find(List):
    if len(List)==1:
        return(int(List[0]))
    elif len(List)==2:
        if List[0] >= List[1]:
            return(int(List[0]))
        else:
            return(int(List[1]))
    elif len(List)==3:
        if (List[0]>=List[1] and List[0]>=List[2]):
            return(int(List[0]))
        elif(List[1]>=List[0] and List[1]>=List[2]):
            return(int(List[1]))
        else:
            return(int(List[2]))
    else:
        if len(List)%2==0:
            List2=[]
            sub1=int(List[len(List)-1])
            sub2=0
            for i in range(0,len(List)//2):
                sub2+=List[2*i]
            List.pop(len(List)-1)
            List.pop(len(List)-1)
            sub1+=find(List)
            if sub1 >= sub2:
                return(sub1)
            else:
                return(sub2)
        else:
            List2=[]
            List3=[]
            sub1=int(List[len(List)-1])
            sub2=int(List[len(List)-2])
            sub3=0
            for i in range(0,len(List)//2):
                sub3+=List[2*i]
            List.pop(len(List)-1)
            List.pop(len(List)-1)
            sub1+=find(List)
            List.pop(len(List)-1)
            sub2+=find(List)
            if (sub1>=sub2 and sub1>=sub3):
                return(sub1)
            elif(sub2>=sub1 and sub2>=sub3):
                return(sub2)
            else:
                return(sub3)
print(find(List))

Submission status: Runtime Error

Solution code:
n=input()
List=list(map(int,input().split()))
def find(List):
    if len(List)==1:
        return(int(List[0]))
    elif len(List)==2:
        if List[0] >= List[1]:
            return(int(List[0]))
        else:
            return(int(List[1]))
    elif len(List)==3:
        if (List[0]>=List[1] and List[0]>=List[2]):
            return(int(List[0]))
        elif(List[1]>=List[0] and List[1]>=List[2]):
            return(int(List[1]))
        else:
            return(int(List[2]))
    else:
        if len(List)%2==0:
            List2=[]
            sub1=int(List[len(List)-1])
            sub2=0
            List.pop(len(List)-1)
            List.pop(len(List)-1)
            sub1+=find(List)
            for i in range(0,len(List)//2):
                sub2+=List[2*i]
            if sub1 >= sub2:
                return(sub1)
            else:
                return(sub2)
        else:
            List2=[]
            List3=[]
            sub1=int(List[len(List)-1])
            sub2=int(List[len(List)-2])
            sub3=0
            List.pop(len(List)-1)
            List.pop(len(List)-1)
            sub1+=find(List)
            List.pop(len(List)-1)
            sub2+=find(List)
            for i in range(0,len(List)//2):
                sub3+=List[2*i]
            if (sub1>=sub2 and sub1>=sub3):
                return(sub1)
            elif(sub2>=sub1 and sub2>=sub3):
                return(sub2)
            else:
                return(sub3)
print(find(List))

Submission status: Runtime Error

Solution code:
n = int(input())
assert n & 1

Submission status: Runtime Error

Solution code:
n = int(input())
*A, = map(int, input().split())
inf = 10**18
# DP[i][0]=i番目まででi//2個選んだ最大値
# DP[i][1]=i番目まででi//2+1個選んだ最大値
DP = [(None, None) for i in range(n)]
DP[0] = (0, A[0])
DP[1] = (0, max(A[0], A[1]))
for i in range(2, n):
    if i % 2 == 0:
        DP[i][0] = max(DP[i-2][0]+A[i], DP[i-1][1])
        DP[i][1] = DP[i-2][1]+A[i]
    else:
        DP[i][0] = max(DP[i-2][0]+A[i], DP[i-1][0])
        DP[i][1] = max(DP[i-2][1]+A[i], DP[i-1][1])
if n % 2 == 0:
    print(DP[n-1][1])
else:
    print(DP[n-1][0])

Submission status: Runtime Error

Solution code:
n = int(input())
*A, = map(int, input().split())
inf = 10**18
X0 = (0, A[0])
X1 = (0, max(A[0], A[1]))
for i in range(2, n):
    X20 = max(X0[0]+A[i], X1[1]*(1-i % 2)+X1[0]*(i % 2))
    X21 = max(X0[1]+A[i], X1[1]*(1-i % 2)+(-inf)*(i % 2))
    X2 = (X20, X21)
    X0, X1 = X1, X2
if n % 2 == 1:
    print(X2[0])
else:
    print(X2[1])

Submission status: Runtime Error

Solution code:
n = int(input())
nums = list(map(int,input().split()))
dp = [[0,0,0] for _ in range(n)]
dp[0][0] = nums[0]
dp[1][0],dp[1][1],dp[1][2] = nums[1],nums[0],-float("inf")
dp[2][0],dp[2][1],dp[2][2] = nums[2],nums[1],nums[0]
for i in range(3,n):
    if i%2 == 0:
        dp[i][0] = max(dp[i-2]) + nums[i]
        dp[i][1] = max(dp[i-3]) + nums[i-1]
        dp[i][2] = sum(nums[0:i-1:2])
    else:
        dp[i][0] = max(dp[i-2]) + nums[i]
        dp[i][1] = sum(nums[0:i-2:2]) + nums[i-1]
        dp[i][2] = -float("inf")
print(max(dp[n-1]))

Submission status: Runtime Error

Solution code:
n = int(input())
nums = list(map(int,input().split()))
dp = [[0,0,0] for _ in range(n)]
dp[0][0] = nums[0]
dp[1][0],dp[1][1],dp[1][2] = nums[1],nums[0],-float("inf")
dp[2][0],dp[2][1],dp[2][2] = nums[2],nums[1],nums[0]
for i in range(3,n):
    if i%2 == 0:
        dp[i][0] = max(dp[i-2]) + nums[i]
        dp[i][1] = max(dp[i-3]) + nums[i-1]
        dp[i][2] = sum(nums[0:i-1:2])
    else:
        dp[i][0] = max(dp[i-2]) + nums[i]
        dp[i][1] = sum(nums[0:i-2:2]) + nums[i-1]
        dp[i][2] = -float("inf")
print(max(dp[n-1]))
print(dp)

Submission status: Runtime Error

Solution code:
def dp(i,k):
    if k<=0:
        return 0
    tmp=N-i
    if k>(tmp//2)+(tmp%2):
        return -float('inf')
    return max(A[i]+dp(i+2,k-1),dp(i+1,k))

N=int(input())
A=[int(_) for _ in input().split()]
print(dp(0,N//2))

Submission status: Runtime Error

Solution code:
from functools import lru_cache

@lru_cache(None)
def dp(N,A,i,k):
    if k<=0:
        return 0
    tmp=N-i
    if k>(tmp//2)+(tmp%2):
        return -float('inf')
    return max(A[i]+dp(N,A,i+2,k-1),dp(N,A,i+1,k))

def main():
    N=int(input())
    A=[int(_) for _ in input().split()]
    print(dp(N,A,0,N//2))

main()

Submission status: Runtime Error

Solution code:
from functools import lru_cache

def main():
    N=int(input())
    A=[int(_) for _ in input().split()]

    @lru_cache(None)
    def dp(i,k):
        if k<=0:
            return 0
        tmp=N-i
        if k>(tmp//2)+(tmp%2):
            return -float('inf')
        return max(A[i]+dp(i+2,k-1),dp(i+1,k))
    print(dp(0,N//2))

main()

Submission status: Runtime Error

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

    def dp(i,k):
        if k<=0:
            return 0
        tmp=N-i
        if k>(tmp//2)+(tmp%2):
            return -float('inf')
        return max(A[i]+dp(i+2,k-1),dp(i+1,k))
    print(dp(0,N//2))

main()

Submission status: Runtime Error

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

    def dp(i,k):
        if k<=0:
            return 0
        tmp=N-i
        if k>tmp//2+tmp%2:
            return -float('inf')
        return max(A[i]+dp(i+2,k-1),dp(i+1,k))

    print(dp(0,N//2))

main()

Submission status: Runtime Error

Solution code:
from math import ceil

def main():
    N=int(input())
    A=[int(_) for _ in input().split()]

    def dp(i,k):
        if k<=0:
            return 0
        tmp=N-i
        if k>ceil(tmp/2):
            return -float('inf')
        return max(A[i]+dp(i+2,k-1),dp(i+1,k))

    print(dp(0,N//2))

main()

Submission status: Runtime Error

Solution code:
from math import ceil

def main():
    N=int(input())
    A=[int(_) for _ in input().split()]

    def dp(i,k):
        print(i,k)
        if k<=0:
            return 0
        tmp=N-i
        if k>ceil(tmp/2):
            return -float('inf')
        return max(A[i]+dp(i+2,k-1),dp(i+1,k))

    print(dp(0,N//2))

main()

Submission status: Runtime Error

Solution code:
from math import ceil
INF=float('inf')

def main():
    N=int(input())
    A=[int(_) for _ in input().split()]

    def dp(i,k):
        print(i,k)
        if k<=0:
            return 0
        tmp=N-i
        if k>ceil(tmp/2):
            return -INF
        return max(A[i]+dp(i+2,k-1),dp(i+1,k))

    print(dp(0,N//2))

main()

Submission status: Runtime Error

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

N = int(readline())
A = list(map(int, readline().split()))

INF = 10**18
limit = 5
dpb = [-INF]*(2*limit+3)
dpw = [-INF]*(2*limit+3)
dpw[0] = 0
for i in range(N):
    a = A[i]
    dpb2 = [-INF]*N
    dpw2 = [-INF]*N
    for j in range(-limit, limit):
        if -limit <= j - 1 < limit:
            dpw2[j-1] = max(dpw2[j-1], dpb[j], dpw[j])
            dpb2[j-1] = max(dpb2[j-1], dpb[j], dpw[j])
        if -limit <= j + 1 < limit:
            dpb2[j+1] = max(dpb2[j+1], dpw[j]+a)
    dpw = dpw2[:]
    dpb = dpb2[:]

idx = N//2*2 - N
print(max(dpw[idx], dpb[idx]))

Submission status: Runtime Error

Solution code:

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

if n % 2 == 0: # 1パス使える
    dp = [[-float('inf') for _ in range(n)] for __ in range(2)]
    dp[1][-1] = a_list[-1]

    for j in reversed(range(2)):
        for i in reversed(range(n)):
            if j == 2 and i >= n-2:
                pass
            elif j == 2:
                dp[j][i] = dp[j][i+2] + a_list[i]
            elif i == n-2:
                dp[j][i] = dp[j+1][i+1]
            elif i > n-2:
                pass
            else:
                dp[j][i] = max(dp[j+1][i+1],dp[j][i+2] + a_list[i])
    print(dp[0][0])
else: # 2パス使える
    dp = [[-float('inf') for _ in range(n)] for __ in range(3)]
    dp[2][-1] = a_list[-1]

    for j in reversed(range(3)):
        for i in reversed(range(n)):
            if j == 2 and i >= n-2:
                pass
            elif j == 2:
                dp[j][i] = dp[j][i+2] + a_list[i]
            elif i == n-2:
                dp[j][i] = dp[j+1][i+1]
            elif i > n-2:
                pass
            else:
                dp[j][i] = max(dp[j+1][i+1],dp[j][i+2] + a_list[i])
    print(dp[0][0])

Submission status: Runtime Error

Solution code:
n=input()
List=list(map(int,input().split()))
def find(List):
    if len(List)==1:
        return(int(List[0]))
    elif len(List)==2:
        if List[0] >= List[1]:
            return(int(List[0]))
        else:
            return(int(List[1]))
    elif len(List)==3:
        if (List[0]>=List[1] and List[0]>=List[2]):
            return(int(List[0]))
        elif(List[1]>=List[0] and List[1]>=List[2]):
            return(int(List[1]))
        else:
            return(int(List[2]))
    else:
        if len(List)%2==0:
            List2=[]
            List3=[]
            for i in range(0,len(List)-2):
                List2.append(List[i])
            for i in range(0,len(List)-3):
                List3.append(List[i])
            sub1=int(int(List[len(List)-1])+find(List2))
            sub2=int(int(List[len(List)-2])+find(List3))
            if sub1 >= sub2:
                return(sub1)
            else:
                return(sub2)
        else:
            List2=[]
            List3=[]
            for i in range(0,len(List)-2):
                List2.append(List[i])
            for i in range(0,len(List)-3):
                List3.append(List[i])
            sub1=int(int(List[len(List)]-1)+find(List2))
            sub2=int(int(List[len(List)-2])+find(List3))
            sub3=0
            for i in range(0,len(List)//2):
                sub3+=List[2*i]
            if sub1 >= sub2:
                if sub1 >= sub3:
                    return(sub1)
                else:
                    if sub3>=sub2:
                        return(sub3)
                    else:
                        return(sub2)
            else:
                if sub2 >= sub3:
                    return(sub2)
                else:
                    if sub3>=sub1:
                        return(sub3)
                    else:
                        return(sub1)
print(find(List))

Submission status: Runtime Error

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

bb = [0] * len(aa)
bb[0] = aa[0]
bb[1] = aa[1]
for i in range(2,len(aa)):
    bb[i] = bb[i-2] + aa[i]

sum0 = bb[len(aa)-2]
sum1 = bb[len(aa)-1]
ret = sum1
if len(aa)%2 == 0:
    ret = max(ret, sum0)
if len(aa)%2:
    sum0 = bb[len(aa)-1]
    sum1 = bb[len(aa)-2]
    for i in range(len(aa)//2):
        ret = max(ret, sum0 - aa[2*i])

# 0 -> 1
for i in range(0,len(aa)//2):
    try:
#        print(i, bb[2*i] - bb[2*i+3] + sum1 + aa[2*i+3])
        ret = max(ret, bb[i] - bb[i+3] + sum1 + aa[i+3] )
    except:
        0
# 1 -> 0
for i in range(0,len(aa)//2):
    try:
#        print(i, bb[2*i+1] - bb[2*i+4] + sum0 + aa[2*i+4])
        ret = max(ret, bb[2*i+1] - bb[2*i+4] + sum0 + aa[2*i+4] )
    except:
        0
print(ret)

Submission status: Runtime Error

Solution code:
bb = [0] * len(aa)
bb[0] = aa[0]
bb[1] = aa[1]
for i in range(2,len(aa)):
    bb[i] = bb[i-2] + aa[i]

sum0 = bb[len(aa)-2]
sum1 = bb[len(aa)-1]
ret = sum1
if len(aa)%2 == 0:
    ret = max(ret, sum0)
if len(aa)%2:
    sum0 = bb[len(aa)-1]
    sum1 = bb[len(aa)-2]
    for i in range(len(aa)//2):
        ret = max(ret, sum0 - aa[2*i])

# 0 -> 1
for i in range(0,len(aa)//2):
    try:
#        print(i, bb[2*i] - bb[2*i+3] + sum1 + aa[2*i+3])
        ret = max(ret, bb[i] - bb[i+3] + sum1 + aa[i+3] )
    except:
        0
# 1 -> 0
for i in range(0,len(aa)//2):
    try:
#        print(i, bb[2*i+1] - bb[2*i+4] + sum0 + aa[2*i+4])
        ret = max(ret, bb[2*i+1] - bb[2*i+4] + sum0 + aa[2*i+4] )
    except:
        0
print(ret)

Submission status: Runtime Error

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

def f(i,j):
  a = 0
  if not 2*j-1 <= i <= 2*j+1+(N-2*int(N/2)):
    a = 0
  elif i == 1 and j == 0:
    a = 0
  elif i == 1 and j == 1:
    a = A[0]
  elif i == 2 and j == 1:
    a = max(A[0],A[1])
  elif i == 2 and j == 0:
    a = 0
  else:
    a = max(f(i-2,j-1)+A[i-1],f(i-1,j))
  return a

print(f(N,int(N/2)))

Submission status: Runtime Error

Solution code:
from functools import lru_cache as lru

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


@lru(None)
def calc(l,used):
    if l >= n and used < n//2:return -pow(10,17)
    if l>=n:return 0
    
    ans = 0
    if used < n//2 : ans = arr[l] + calc(l+2,used+1) 
    ans = max(ans,calc(l+1,used))
    
    return ans

print(calc(0,0))

Submission status: Runtime Error

Solution code:
from functools import lru_cache as lru

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


@lru(None)
def calc(l,used):
    if l >= n and used < n//2:return -pow(10,17)
    if used == n//2 or l >= n:return 0
    
    ans = 0
    ans = arr[l] + calc(l+2,used+1)
    ans = max(ans,calc(l+1,used))
    
    return ans

print(calc(0,0))

Submission status: Runtime Error

Solution code:
n,*l=open(0);n=int(n);l=list(map(int,l.split()))
p=[0]*n;d=[0]*n
for i in range(n):p[i]=l[i]+p[i-2];d[i]=max(p[i-1]if(i&1)else d[i-1],l[i]+d[i-2])
print(d[-1])

Submission status: Runtime Error

Solution code:
n,*l=open(0);n=int(n);l=list(map(int,l))
p=[0]*n;d=[0]*n
for i in range(n):p[i]=l[i]+p[i-2];d[i]=max(p[i-1]if(i&1)else d[i-1],l[i]+d[i-2])
print(d[-1])

Submission status: Runtime Error

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
c=np.zeros((n+1,2,(n+1)//2+1),"i8")
for i in range(n):
    c[i+1][1][(i+1)//2]=c[i][0][(i-1)//2]+a[i]
    c[i+1][1][(i-1)//2]=c[i][0][(i-2)//2]+a[i]
    c[i+1][0][(i+1)//2]=c[i][1][(i+1)//2]+c[i][0][(i+1)//2]
    c[i+1][0][(i-1)//2]=c[i][1][(i-1)//2]+c[i][0][(i-1)//2]
print(max(c[-1][1][n//2],c[-1][0][n//2]))

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n%2==1:
    dp=[[0 for j in range(3)] for i in range(n//2)]
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    dp[0][2]=a[2]
    for i in range(n//2-1):
        dp[i+1][0]=(dp[i][0]+a[2*(i+1)])
        dp[i+1][1]=max(dp[i][0],dp[i][1])+a[2*(i+1)+1]
        dp[i+1][2]=max(dp[i])+a[2*(i+2)+2]
    print(max(dp[-1]))
if n%2==0:
    dp=[[0 for j in range(2)] for i in range(n//2)]
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    for i in range(n//2-1):
        dp[i+1][0]=(dp[i][0]+a[2*(i+1)])
        dp[i+1][1]=max(dp[i][0],dp[i][1])+a[2*(i+1)+1]
        #dp[i+1][2]=max(dp[i])+a[2*(i+2)+2]
    print(max(dp[-1]))

Submission status: Runtime Error

Solution code:
z=[]

def foo(i,n,su,count,limit,l,select):

	if count==limit:
		z.append(su)
		return 
	if i>=n:
		return
	if select==0:
		foo(i+1,n,su+l[i],count+1,limit,l,1)
		foo(i+1,n,su,count,limit,l,0)
	else:
		foo(i+1,n,su,count,limit,l,0)


n=int(input())
l=list(map(int,input().split()))
foo(0,n,0,0,n//2,l,0)
print(max(z))

Submission status: Runtime Error

Solution code:
def dfs(n, arr, rest, i, sum):
    if n <= i:
        if rest > 0:
            return None
        else:
            return sum
    if rest == 0:
        return sum
    # add early return for over-skipping?

    a = dfs(n, arr, rest - 1, i+2, sum + arr[i])
    b = dfs(n, arr, rest, i + 1, sum)
    if a is None and b is None:
        return None
    else:
        if a is None:
            return b
        if b is None:
            return a
        if b > a:
            return b
        else:
            return a


n = int(input())
arr = list(map(int, input().split()))
if n % 2 == 0:
    a = dfs(n, arr, n//2, 0, 0)
    b = dfs(n, arr, n//2,  1, 0)
    if a > b:
        print(a)
    else:
        print(b)
else:
    selected = n//2
    a = dfs(n, arr, selected,  0, 0)
    print(a)

Submission status: Runtime Error

Solution code:
n = int(input())
A = [int(_) for _ in input().split()]

# dp = [[0 for i in range((n//2)+1)] for j in range(n)]

dp = [[0, 0] for j in range(n)]
M = - float('inf')
for i in range(4):
    M = max(M, A[i])
    dp[i][0] = M
dp[2][1] = dp[0][0] + A[2]
dp[3][1] = max(dp[1][0] + A[3], dp[2][1])


# for i in range(len(dp)):
#     print(dp[i])

# for i in range(4, n):
#     for j in range(max(0, i // 2 - 1), (i + 2) // 2):
#         # print(i, j)
#         if i % 2 == 0 and j == (i + 2) // 2 - 1 :
#             dp[i][j] = dp[i-2][j-1] + A[i]
#         else:
            # dp[i][j] = max(dp[i-2][j-1] + A[i], dp[i-1][j])

for i in range(4, n):
    for j in range(2):
        # print(i, j)
        if i % 2 == 0 and j == 1:
            dp[i][j] = dp[i-2][1] + A[i]
        elif i % 2 == 0 and j == 0:
            dp[i][j] = max(dp[i-2][0] + A[i], dp[i-1][1])
        elif i % 2 == 1 and j == 1:
            dp[i][j] = max(dp[i-2][1] + A[i], dp[i-1][1])
        else:
            dp[i][j] = max(dp[i-2][0] + A[i], dp[i-1][0])

# for i in range(len(dp)):
#     print(dp[i])

print(dp[n-1][(n+1)%2])

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [[0]*3 for _ in range(N+1)]

dp[1][3] = A[0]
dp[2][2] = max(A[1],dp[1][3])

for i in range(2,N):
  a = A[i]
  mid = (i+1)//2
  ma = (i+2)//2
  mi = i//2
  dp[i+1][2+ma-mid] = max(dp[i][2+ma-i//2],dp[i-1][1+ma-(i-1)//2]+a)
  dp[i+1][2+mi-mid] = max(dp[i][2+mi-i//2],dp[i-1][1+mi-(i-1)//2]+a)

print(dp[-1][2])

Submission status: Runtime Error

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

dp = [[0 for i in range((n//2)+1)] for j in range(n)]

M = - float('inf')
for i in range(4):
    M = max(M, A[i])
    dp[i][0] = M
dp[2][1] = dp[0][0] + A[2]
dp[3][1] = max(dp[1][0] + A[3], dp[2][1])


# for i in range(len(dp)):
#     print(dp[i])

for i in range(4, n):
    for j in range(max(0, i // 2 - 1), (i + 2) // 2):
        # print(i, j)
        if i % 2 == 0 and j == (i + 2) // 2 - 1 :
            dp[i][j] = dp[i-2][j-1] + A[i]
        else:
            dp[i][j] = max(dp[i-2][j-1] + A[i], dp[i-1][j])

# for i in range(len(dp)):
#     print(dp[i])

print(dp[n-1][-2])

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [0]*(N//2)
for i in range(N//2):
  dp[i] = max(dp[i]+A[i+1],dp[i]+A[i+2])
ans = 0
for j in range(len(dp)):
  if dp[j] > 0:
    ans += dp[j]
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque, Counter
from itertools import chain, combinations
import json
import numpy as np
import bisect
import sys
import math
import bisect

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7


def main():
    N = int(input())
    A = [int(a) for a in input().split()]

    DP = np.zeros((N + 1, N + 1))
    DP[1][1] = A[0]

    for i in range(2, N + 1):
        a = math.floor((i - 1) / 2)
        b = math.floor((i + 1) / 2)
        for j in range(a, b + 1):
            DP[i][j] = max(DP[i - 1][j], DP[i - 2][j - 1] + A[i - 1])
    print(int(DP[N][math.floor(N / 2)]))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

dp = [[0 for i in range((n//2)+1)] for j in range(n)]

M = - float('inf')
for i in range(4):
    M = max(M, A[i])
    dp[i][0] = M
dp[2][1] = dp[0][0] + A[2]
dp[3][1] = max(dp[1][0] + A[3], dp[2][1])


# for i in range(len(dp)):
#     print(dp[i])

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

# for i in range(len(dp)):
#     print(dp[i])

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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(2*1000000)

N = int(input())
A = list(map(int, input().split(" ")))



def dp(i, j):
    if i >= N:
        return (-1*1000000000)
    if (N//2)-j < (i-1)//2:
        return (-1*1000000000)
    if j == 1:
        return A[i]
	else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        dp_dict[(i, j)] = temp
        return temp


select = N//2
if select == 1:
    print(max(A))
else:
    print(dp(0, select))

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    a = LI()
    dp = [0] * N
    dp[1] = max(a[0], a[1])
    c = a[0]

    for i in range(2, n):
        if i % 2 == 0:
            c += a[i]
            dp[i] = max(dp[i-2] + a[i], dp[i-1])
        else:
            dp[i] = max(dp[i-2] + a[i], c)

    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    a = LI()
    dp[1] = max(a[0],a[1])
    c = a[0]

    for i in range(2, n):
        if i % 2 == 0:
            c += a[i]
            dp[i] = max(dp[i-2] + a[i], dp[i-1])
        else:
            dp[i] = max(dp[i-2] + a[i], c)

    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

dp_dict = {}


def dp(i, j):
    print(i, j)
    if i >= N:
        return (-1*10e+9)-1
    if j == 1:
        return A[i]
    if (i, j) in dp_dict:
        return dp_dict[(i, j)]
    else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        dp_dict[(i, j)] = temp
        return temp


print(dp(0, (N//2)))

Submission status: Runtime Error

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

dp_dict = {}


def dp(i, j):
    if i >= N:
        return -1*10e+9
    if (i+1)//2 > (N//2)-j+1:
        return -1*10e+9
    if j == 1:
        return A[i]
    if (i, j) in dp_dict:
        return dp_dict[(i, j)]
    else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        dp_dict[(i, j)] = temp
        return temp


print(dp(0, (N//2)))

Submission status: Runtime Error

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

dp_dict = {}


def dp(i, j):
    if j == 1:
        return A[i]
    # if (i-1)//2 > (N//2)-j:
        # return -1*10e+9
    if (N-1)-i < j:
        return -1*10e+9

    if (i, j) in dp_dict:
        return dp_dict[(i, j)]
    else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        dp_dict[(i, j)] = temp
        return temp


print(dp(0, N//2))

Submission status: Runtime Error

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


dp_dict = {}


def dp(i, j):
    if j == 1:
        return A[i]
    if (i-1)//2 > (N//2)-j:
        return -1*10e+9
    if (N-1)-i < j:
        return -1*10e+9

    if (i, j) in dp_dict:
        return dp_dict[(i, j)]
    else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        dp_dict[(i, j)] = temp
        return temp


print(dp(0, N//2))

Submission status: Runtime Error

Solution code:
def solve(pick, idx):

    if pick == 0: return 0
    if idx >= n: return -float('inf')
    if (pick, idx) in dp: return dp[pick, idx]
    if n-idx+2 < pick*2: return -float('inf')
    total = max(A[idx] + solve(pick-1, idx+2), solve(pick, idx+1))

    dp[(pick, idx)] = total
    return total

n = int(input())
A = list(map(int, input().split()))
dp = {}
pick = n//2

print(solve(pick, 0))
"""
@lru_cache(None)
def F(index, n):
    if index >= N:
        return -INF
    if N - index + 2 < 2 * n:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret
"""

Submission status: Runtime Error

Solution code:
def solve(pick, idx):

    if pick == 0: return 0
    if idx >= n: return -float('inf')
    if (pick, idx) in dp: return dp[pick, idx]
    # if n-idx+2 < pick*2: return -float('inf')
    total = max(A[idx] + solve(pick-1, idx+2), solve(pick, idx+1))

    dp[(pick, idx)] = total
    return total

n = int(input())
A = list(map(int, input().split()))
dp = {}
pick = n//2

print(solve(pick, 0))

Submission status: Runtime Error

Solution code:
def solve(pick, idx):

    if pick == 0: return 0
    if idx >= n: return -float('inf')

    if n-idx+2 < pick*2: return -float('inf')
    total = max(A[idx] + solve(pick-1, idx+2), solve(pick, idx+1))

    dp[(pick, idx)] = total
    return total

n = int(input())
A = list(map(int, input().split()))
dp = {}
pick = n//2

print(solve(pick, 0))

Submission status: Runtime Error

Solution code:
def solve(pick, idx):

    if pick == 0: return 0
    if idx >= n: return -float('inf')

    total = max(A[idx] + solve(pick-1, idx+2), solve(pick, idx+1))

    dp[(pick, idx)] = total
    return total

n = int(input())
A = list(map(int, input().split()))
dp = {}
pick = n//2

print(solve(pick, 0))

Submission status: Runtime Error

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

if N % 2 == 1:
    ans_1 = 0
    ans_2 = 0
    ans_3 = 0
    for i in range(0,N-2,2):
        ans_1 += a_list[i]
        #print(i)
    for j in range(1,N-1,2):
        ans_2 += a_list[i]
    for k in range(2,N,2):
        ans_3 += a_list[i]
    print(max(ans_1,ans_2,ans_3))
else:
    ns_1 = 0
    ns_2 = 0
    for i in range(0,N,2):
        ns_1 += a_list[i]
        #print(i)
    for j in range(1,N+1,2):
        ns_2 += a_list[j]
        #print(a_list[j])
    print(max(ns_2,ns_1)

Submission status: Runtime Error

Solution code:
import sys
import math
import itertools
from functools import lru_cache
input = sys.stdin.readline

@lru_cache(maxsize=None)
def dfs(i, h):
	if h == 0:
		return 0
	if h == 1:
		if i >= 0:
			return max(A[:i+1])
		else:
			return -float('inf')
	if i < 2:
		return -float('inf')
	s1 = A[i] + dfs(i-2, h-1)
	s2 = A[i-1] + dfs(i-3, h-1)
	s3 = A[i-2] + dfs(i-4, h-1)
	return max(s1, s2, s3)

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

H = N // 2

print(dfs(N-1, H))