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:
from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin


def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    if n % 2 == 0:
        v = [[None for j in range(2)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        for i in range(2, n):
            for j in range(2):
                c = []
                if v[i-2][j] is not None:
                    c.append(v[i-2][j])
                if j >= 1 and i >= 3:
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(2)]
        print(max(c))
    else:
        v = [[None for j in range(3)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        v[2][0] = a[0]+a[2]
        v[2][2] = a[2]
        for i in range(3, n):
            for j in range(3):
                c = []
                if v[i-2][j] is not None:
                    c.append(v[i-2][j])
                if j >= 1:
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                if j >= 2 and i >= 4:
                    if v[i-4][j-2] is not None:
                        c.append(v[i-4][j-2])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(3) if v[n-1][j] is not None]
        print(max(c))


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


main()

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
def main():
    N = int(stdin.readline())
    A = list(map(int, stdin.readline().rstrip().split()))
    dp = [0] * N
    dp[1] = max(A[0], A[1])
    dp[2] = max(dp[1], A[2])
    for i in range(3, N):
        if i & 1 == 0:
            dp[i] = max(dp[i-1], A[i] + dp[i-2])
        else:
            dp[i] = A[i] + dp[i-2]
    ret=dp[N-1]
    stdout.write(str(ret)+"\n")
main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin


def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    if n % 2 == 0:
        v = [[None for j in range(2)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        v[2][0] = a[0]+a[2]
        for i in range(3, n):
            for j in range(2):
                c = []
                if v[i-2][j] is not None:
                    c.append(v[i-2][j])
                if j == 1:
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(2) if v[n-1][j] is not None]
        print(max(c))
    else:
        v = [[None for j in range(3)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        v[2][2] = a[2]
        for i in range(3, n):
            for j in range(3):
                c = []
                if v[i-2][j] is not None:
                    c.append(v[i-2][j])
                if j == 1:
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                if j == 2 and i > 3:
                    if v[i-4][j-2] is not None:
                        c.append(v[i-4][j-2])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(3) if v[n-1][j] is not None]
        print(max(c))


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


main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
##################################
# University of Wisconsin-Madison
# Author: Yaqi Zhang
##################################

# standard library
import sys
from functools import lru_cache

N = int(input())
INF = 10**18
nums = list(map(int, input().split()))
@lru_cache(None)
def dp(idx, n):
    if idx >= N:
        return -INF
    if N - idx + 2 < 2 * n:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(nums[idx:])
    return max(nums[idx] + dp(idx + 2, n - 1), dp(idx + 1, n))
print(dp(0, N // 2))

Submission status: Runtime Error

Solution code:
import numpy as np

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

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

Submission status: Runtime Error

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

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

for i in range(3, N):
    if i % 2 == 1:
        dp_g = max(dp_k, dp_g) + A[i]
        dp_k += A[i - 1]
        dp.append(max(dp_g, dp_k))
    elif i % 2 == 0:
        dp.append(max(dp[i - 1], dp[i - 2] + A[i]))

print(dp[N - 1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
##################################
# University of Wisconsin-Madison
# Author: Yaqi Zhang
##################################

# standard library
import sys
from functools import lru_cache

def main():
    N = int(input())
    INF = 10**18
    nums = list(map(int, input().split()))
    @lru_cache(None)
    def dp(idx, n):
        if idx >= N:
            return -INF
        if N - idx + 2 < 2 * n:
            return -INF
        if n == 0:
            return 0
        elif n == 1:
            return max(nums[idx:])
        return max(nums[idx] + dp(idx + 2, n - 1), dp(idx + 1, n))
    print(dp(0, N // 2))



if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

if N%2==0:
    1/0
    ans = max(sum(A[::2]),sum(A[1::2]))
    print(ans)
else:
    INF = 2* 10**9
    dp = [[-INF]*N for _ in [0]*3]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for i in range(2,N,2):
        a = A[i]
        dp[0][i] = dp[0][i-2] + a
    for i in range(3,N):
        a = A[i]
        dp[1][i] = max(dp[1][i-2],dp[0][i-3]) + a
    for i in range(4,N,2):
        a = A[i]
        dp[2][i] = max(dp[2][i-2],dp[1][i-3],dp[0][i-4]) + a
    print(dp[2][-1])

Submission status: Runtime Error

Solution code:
from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin


def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    if n % 2 == 0:
        v = [[None for j in range(2)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        v[2][0] = a[0]+a[2]
        for i in range(3, n):
            for j in range(2):
                c = []
                if j == 1:
                    if v[i-2][j] is not None:
                        c.append(v[i-2][j])
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                else:
                    if v[i-2][j] is not None:
                        c.append(v[i-2][j])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(2) if v[n-1][j] is not None]
        print(max(c))
    else:
        v = [[None for j in range(3)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        v[2][2] = a[2]
        for i in range(3, n):
            for j in range(3):
                c = []
                if j == 2:
                    if v[i-2][j] is not None:
                        c.append(v[i-2][j])
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                    if v[i-4][j-2] is not None:
                        c.append(v[i-4][j-2])
                elif j == 1:
                    if v[i-2][j] is not None:
                        c.append(v[i-2][j])
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                else:
                    if v[i-2][j] is not None:
                        c.append(v[i-2][j])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(3) if v[n-1][j] is not None]
        print(max(c))


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


main()

Submission status: Runtime Error

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

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

def main():
    mod=10**9+7
    inf=10**20
    N=I()
    A=LI()
    if N%2==0:
        ans=0
        for i in range(0,N,2):
            ans+=A[i]
        ans=max(ans,sum(A)-ans)
        print(ans)
    else:
        """左から見ていく，i個を見たときに，
        iが偶数：
        　現在i//2個取得　or i//2 - 1取得(もう余裕がない)
        
        iが奇数：
        　現在i// +12個取得　or i//2取得(もう余裕がない)
        さらにi番目をとったか撮ってないかで2通り 
        ただし，余裕がある状態から取らないのは，数が足りなくなる
        """
        tight_get=[0]*N
        tight_not=[0]*N
        lo=[0]*N
        
        #最初だけ，取ったら必ずlooseになる
        lo[0]=A[0]
        lo[1]=A[1]
        
        for i in range(2,max(3,N)):
            LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i]+tight_not[i-1]]
            tight_get[i]=max(LL)
            LL=[lo[i-2]]
            tight_not[i]=max(LL)
            lo[i]=lo[i-2]+A[i]
            
        for i in range(3,max(4,N)):
            LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i],tight_not[i-1]+A[i],lo[i-3]+A[i]]
            tight_get[i]=max(LL)
            LL=[lo[i-2]]
            tight_not[i]=max(LL)
            lo[i]=max(lo[i-2]+A[i],lo[i-3]+A[i])
            
        for i in range(4,N):
            LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i],tight_not[i-1]+A[i],lo[i-3]+A[i],lo[i-4]+A[i]]
            tight_get[i]=max(LL)
            LL=[lo[i-2]]
            tight_not[i]=max(LL)
            lo[i]=lo[i-2]+A[i]
            
        print(max(tight_get[-1],tight_not[-1],lo[-1]))
    
    
    
        
        
        

main()

Submission status: Runtime Error

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

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

def main():
    mod=10**9+7
    inf=10**20
    N=I()
    A=LI()
    if N%2==0:
        ans=0
        for i in range(0,N,2):
            ans+=A[i]
        ans=max(ans,sum(A)-ans)
        print(ans)
    else:
        """左から見ていく，i個を見たときに，
        iが偶数：
        　現在i//2個取得　or i//2 - 1取得(もう余裕がない)
        
        iが奇数：
        　現在i// +12個取得　or i//2取得(もう余裕がない)
        さらにi番目をとったか撮ってないかで2通り 
        ただし，余裕がある状態から取らないのは，数が足りなくなる
        """
        tight_get=[0]*N
        tight_not=[0]*N
        lo=[0]*N
        
        #最初だけ，取ったら必ずlooseになる
        lo[0]=A[0]
        lo[1]=A[1]
        
        for i in range(2,3):
            LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i]+tight_not[i-1]]
            tight_get[i]=max(LL)
            LL=[lo[i-2]]
            tight_not[i]=max(LL)
            lo[i]=lo[i-2]+A[i]
            
        for i in range(3,4):
            LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i],tight_not[i-1]+A[i],lo[i-3]+A[i]]
            tight_get[i]=max(LL)
            LL=[lo[i-2]]
            tight_not[i]=max(LL)
            lo[i]=max(lo[i-2]+A[i],lo[i-3]+A[i])
            
        for i in range(4,N):
            LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i],tight_not[i-1]+A[i],lo[i-3]+A[i],lo[i-4]+A[i]]
            tight_get[i]=max(LL)
            LL=[lo[i-2]]
            tight_not[i]=max(LL)
            lo[i]=lo[i-2]+A[i]
            
        print(max(tight_get[-1],tight_not[-1],lo[-1]))
    
    
    
        
        
        

main()

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    if n % 2 == 0:
        print(max(sum(a[::2]), sum(a[1::2])))
        return
    else:
        print(1/0)


main()

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)==3:
        if List[0]>=List[1]:
            if List[0]>=List[2]:
                return(int(List[0]))
            else:
                if List[1]>=List[2]:
                    return(int(List[1]))
                else:
                    return(int(List[2]))
        else:
            if List[1]>=List[2]:
                return(int(List[1]))
            else:
                if List[0]>=List[2]:
                    return(int(List[0]))
                else:
                    return(int(List[2]))
    else:
        if len(List)==2:
            if List[0]>=List[1]:
                return(int(List[0]))
            else:
                return(int(List[1]))
        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:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    if n == 2:
    dp = [-10**15]*(n+1)
    dp[2] = max(a[0], a[1])
    if n > 2:
        dp[3] = max(a[:3])
        aa = a[0]+a[2]
        for i in range(4, n+1):
            if i%2:
                aa += a[i-1]
                dp[i] = max(dp[i-1], dp[i-2]+a[i-1])
            else:
                dp[i] = max(aa, dp[i-2]+a[i-1])
    print(dp[n])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [-10**15]*(n+1)
    dp[2] = max(a[0], a[1])
    dp[3] = max(a[:3])
    aa = a[0]+a[2]
    for i in range(4, n+1):
        if i%2:
            aa += a[i-1]
            dp[i] = max(dp[i-1], dp[i-2]+a[i-1])
        else:
            dp[i] = max(aa, dp[i-2]+a[i-1])
    print(dp[n])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
lst = list(map(int,input().split())).sort()
if N % 2 == 0:
    print(sum(lst[::2]))
else:
    print(sum(lst[2::2]))

Submission status: Runtime Error

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

dp = [0]*N

cum = A[0]
for i in range(N):
    if i == 0:
        dp[i] = 0
        continue
    if i == 1:
        dp[i] = max(A[0],A[1])
        continue
    if i%2==0: #奇数の時
        cum += A[i]
        dp[i] = max(dp[i−1],dp[i-2]+A[i])

    if i%2==1: #偶数の時
        dp[i] = max(dp[i-2]+A[i],cum)

ans = dp[-1]


print(ans)
#print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
dp = {}
def dfs(l, n):
    if n == 0 or l <= 0:
        return float('-inf')
    if n == 1:
        dp[(l, n)] = max(A[:l])
    if (l, n) not in dp:
        dp[(l, n)] = max(A[l-1] + dfs(l-2, n-1), dfs(l-1, n))
        # print((l, n), dp[(l, n)])
    return dp[(l, n)]

N = int(input())
A = list(map(int, input().split()))
dfs(N, N // 2)
print(dp[(N, N // 2)])

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N%2==0:
    n1=0
    n2=0
    for i in range(N):
        if i%2==0:
            n1=n1+A[i]
        else:
            n2=n2+A[i]
    print(max(n1,n2))
else:
    #print(A[0],A[1])
    dp=[[-float("inf") for _ in range(3)] for _ in range(N+10)]
    if N==3:
        print(max(A[0],A[1],A[2]))
    else:
        for i in range(N):
            if i<4:
                if i==0:
                    dp[i][0]=A[0]
                if i==1:
                    dp[i][1]=A[0]
                    dp[i][0]=A[1]
                if i==2:
                    dp[i][2]=A[2]
                    dp[i][1]=A[1]
                    dp[i][0]=A[0]+A[2]
                if i==3:
                    dp[i][0]=dp[1][0]+A[3]
                    dp[i][1]=max(dp[1][1]+A[3],dp[0][0]+A[3])
                    dp[i][2]=max(dp[1][2]+A[3],dp[0][1]+A[3])
            else:
                for j in range(3):
                    if j==0:#ここでも2こずつ規則よく飛ばすと決めた
                        dp[i][0]=max(dp[i][0],dp[i-2][0]+A[i])
                    elif j==1:#1回だけ無茶した
                        dp[i][1]=max(dp[i][1],dp[i-2][1]+A[i],dp[i-3][0]+A[i])
                    else:
                        dp[i][2]=max(dp[i][2],dp[i-2][2]+A[i],dp[i-3][1]+A[i],dp[i-4][0]+A[i])
print(max(dp[N-1]))

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N%2==0:
    n1=0
    n2=0
    for i in range(N):
        if i%2==0:
            n1=n1+A[i]
        else:
            n2=n2+A[i]
    #print(max(n1,n2))
else:
    #print(A[0],A[1])
    dp=[[-float("inf") for _ in range(3)] for _ in range(N+10)]
    if N==3:
        print(max(A[0],A[1],A[2]))
    else:
        for i in range(N):
            if i<4:
                if i==0:
                    dp[i][0]=A[0]
                if i==1:
                    dp[i][1]=A[0]
                    dp[i][0]=A[1]
                if i==2:
                    dp[i][2]=A[2]
                    dp[i][1]=A[1]
                    dp[i][0]=A[0]+A[2]
                if i==3:
                    dp[i][0]=dp[1][0]+A[3]
                    dp[i][1]=max(dp[1][1]+A[3],dp[0][0]+A[3])
                    dp[i][2]=max(dp[1][2]+A[3],dp[0][1]+A[3])
            else:
                for j in range(3):
                    if j==0:#ここでも2こずつ規則よく飛ばすと決めた
                        dp[i][0]=max(dp[i][0],dp[i-2][0]+A[i])
                    elif j==1:#1回だけ無茶した
                        dp[i][1]=max(dp[i][1],dp[i-2][1]+A[i],dp[i-3][0]+A[i])
                    else:
                        dp[i][2]=max(dp[i][2],dp[i-2][2]+A[i],dp[i-3][1]+A[i],dp[i-4][0]+A[i])
print(max(dp[N-1]))

Submission status: Runtime Error

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

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

        a = b.copy()
    print(ans)
    exit()

b = a[:10]
e = [True]*10

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

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N%2==0:
    n1=0
    n2=0
    for i in range(N):
        if i%2==0:
            n1=n1+A[i]
        else:
            n2=n2+A[i]
    #print(max(n1,n2))
else:
    #print(A[0],A[1])
    dp=[[-float("inf") for _ in range(3)] for _ in range(N+10)]
    if N==3:
        print(max(A[0],A[1],A[2]))
    else:
        for i in range(N):
            if i<3:
                if i==0:
                    dp[i][0]=A[0]
                if i==1:
                    dp[i][1]=A[0]
                    dp[i][0]=A[1]
                if i==2:
                    dp[i][2]=A[2]
                    dp[i][1]=A[1]
                    dp[i][0]=A[0]+A[2]
                if i==3:
                    dp[i][0]=dp[1][0]+A[3]
                    dp[i][1]=max(dp[1][1]+A[3],dp[0][0]+A[3])
                    dp[i][2]=max(dp[1][2]+A[3],dp[0][1]+A[3])
            else:
                for j in range(3):
                    if j==0:#ここでも2こずつ規則よく飛ばすと決めた
                        dp[i][0]=max(dp[i][0],dp[i-2][0]+A[i])
                    elif j==1:#1回だけ無茶した
                        dp[i][1]=max(dp[i][1],dp[i-2][1]+A[i],dp[i-3][0]+A[i])
                    else:
                        dp[i][2]=max(dp[i][2],dp[i-2][2]+A[i],dp[i-3][1]+A[i],dp[i-4][0]+A[i])
print(max(dp[N-1]))

Submission status: Runtime Error

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

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

if N==2:
  print(max(0,A[0],A[1]))

dp=[[-10**18 for i in range(N)] for j in range(3)]
dp[0][0]=A[0]
dp[1][1]=A[1]
dp[2][2]=A[2]

for n in range(3):
    for index in range(N):
        if dp[n][index]!=-1:
            if n!=2 and index+3<N:
                dp[n+1][index+3]=max(dp[n+1][index+3],dp[n][index]+A[index+3])
            if n==0 and index+4<N:
                dp[n+2][index+4]=max(dp[n+2][index+4],dp[n][index]+A[index+4])
            if index+2<N:
                dp[n][index+2]=max(dp[n][index+2],dp[n][index]+A[index+2])

a=(dp[0][-1])
b=(dp[1][-1])
c=(dp[2][-1])

print(max(a,b,c))

Submission status: Runtime Error

Solution code:
dp = {}
def dfs(l, n):
    if l < n * 2 or n == 0 or l <= 0:
        return float('-inf')
    if n == 1:
        dp[(l, n)] = max(A[:l])
    if (l, n) not in dp:
        dp[(l, n)] = max(A[l-1] + dfs(l-2, n-1), dfs(l-1, n))
    return dp[(l, n)]

N = int(input())
A = list(map(int, input().split()))
dfs(N, N // 2)
print(dp[(N, N // 2)])

Submission status: Runtime Error

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

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

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

        a = b.copy()
    print(ans)
    exit()

b = a[:10]
e = [True]*10

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

Submission status: Runtime Error

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


def dp(index, skips):
    
    if index >= n:
        return 0
    else:
        maxx = line[index] + dp(index+2, skips)

        if skips >= 1 and index+1 < n:
            maxx = max([maxx, line[index+1] + dp(index+3, skips-1)])
        if skips >= 2 and index+2 < n:
            maxx = max([maxx, line[index+2] + dp(index+4, skips-2)])
        
        return maxx
    
if n%2 ==0:
    sumA = 0
    sumB = 0

    for i in range(0, n):
        if i%2 == 0:
            sumA = sumA + line[i]
        else:
            sumB = sumB + line[i]

    print(max([sumA, sumB]))

else:
    print(dp(0,2))

Submission status: Runtime Error

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

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

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

        a = b.copy()
    print(ans)
    exit()
    
b = a[:4]
e = [True]*4

for i in range(1, n // 2):
    c = [0] * 4
    f = [False]*4
    d = -10**24
    for j in range(4):
        if 2 * i + j >= n:
            continue
        if not e[j]:
            continue
        d = max(d, b[j])
        c[j] = d + a[2 * i + j]
        f[j] = True
    e = f.copy()
    b = c.copy()
ans = -10 ** 24
for i in range(4):
    if e[i]:
        ans = max(ans, b[i])
print(e)
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N%2==0:
    n1=0
    n2=0
    for i in range(N):
        if i%2==0:
            n1=n1+A[i]
        else:
            n2=n2+A[i]
    #print(max(n1,n2))
else:
    #print(A[0],A[1])
    dp=[[-float("inf") for _ in range(3)] for _ in range(N+1)]
    if N==3:
        print(max(A[0],A[1],A[2]))
    elif N==1:
        print(A[0])
    else:
        for i in range(N):
            if i<3:
                if i==0:
                    dp[i][0]=A[0]
                if i==1:
                    dp[i][1]=A[0]
                    dp[i][0]=A[1]
                if i==2:
                    dp[i][2]=A[2]
                    dp[i][1]=A[1]
                    dp[i][0]=A[0]+A[1]
            else:
                for j in range(3):
                    if j==0:#ここでも2こずつ規則よく飛ばすと決めた
                        dp[i][0]=max(dp[i][0],dp[i-2][0]+A[i])
                    elif j==1:#1回だけ無茶した
                        dp[i][1]=max(dp[i][1],dp[i-2][1]+A[i],dp[i-3][0]+A[i])
                    else:
                        dp[i][2]=max(dp[i][2],dp[i-2][2]+A[i],dp[i-3][1]+A[i],dp[i-4][0]+A[i])
print(max(dp[N-1]))

Submission status: Runtime Error

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
A = list(map(int, input().split()))
INF = 10**9 + 1

dp = [[-INF]*(N//2+1) for _ in range(N+1)]
dp[1][1] = max(-INF, A[0])

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

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

Submission status: Runtime Error

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

P = [A[0]]
Q = [A[1]]
for i in range(2,N):
    if i % 2 == 0:
        P.append(P[-1] + A[i])
    else:
        Q.append(Q[-1] + A[i])

if N % 2 == 0:
    ans = max(P[-1],Q[-1])
    for i in range(N//2-1):
        ans = max(ans,P[i]+Q[-1]-Q[i])
else:
    ans = max(Q[-1],P[-1] - min(A[0::2]))
    ans = max(ans, Q[-2]-Q[0]+A[0]+A[-1])
    for i in range(N//2-1):
        ans = max(ans,P[i]+Q[-1]-Q[i])
    for i in range(N//2-1):
        ans = max(ans,P[-1]-P[i+1]+Q[i])
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
a=input().split()
b=0
c=0
d=[]
a1=[int(s) for s in a]
print(N,a1)
import copy

if N%2==0 :
  for i in range(0,N,2):
    b+=a1[i]
    c+=a1[i+1]
  if b>c:
    print(b)
  else:
    print(c)
else:
  for i in range(0,N-1):
    for j in range (0,i,2):
      b+=a1[j]
      c+=a1[N-j]
      d.append(b+c)
  print(max(d))

Submission status: Runtime Error

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

dic = {}

def dp(index, skips):

    if dic.get((index, skips)) != None:
        return dic.get((index, skips))
    
    if index >= n:
        return 0
    else:

        maxx = line[index] + dp(index+2, skips)

        if skips >= 1 and index+1 < n:
            maxx = max([maxx, line[index+1] + dp(index+3, skips-1)])
        if skips >= 2 and index+2 < n:
            maxx = max([maxx, line[index+2] + dp(index+4, skips-2)])

        dic[(index, skips)] = maxx
        
        return maxx
    
if n%2 ==0:
    sumA = 0
    sumB = 0

    for i in range(0, n):
        if i%2 == 0:
            sumA = sumA + line[i]
        else:
            sumB = sumB + line[i]

    print(max([sumA, sumB]))

else:
    print(dp(0,2))

Submission status: Runtime Error

Solution code:
def even(N, A):
    total_A_odd = 0
    for i in range(N):
        if i % 2 == 0:
            dis.append(A[i+1] - A[i])
            total_A_odd += A[i]

    M = len(dis)
    ruikeiwa = list()
    for j in range(M-1, -1, -1):
        if j == M-1:
            ruikeiwa.append(dis[j])
        else:
            ruikeiwa.append(ruikeiwa[-1]+dis[j])
    
    return max(ruikeiwa)+total_A_odd
    


N = int(input())

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

dis = list()
if N % 2 == 0:
    print(even(N ,A))
else:
    A1 = [0]*(N-1)
    for i in range(N-1):
        A1[i] = A[i]
    
    A2 = [0]*(N-1)
    for i in range(N-1):
        A2[i] = A[i+1]

    A3 = [0]*(N-1)
    for i in range(N-1):
        if i == 0:
            A3[0] = A[0]
        if i > 1:
            A3[i] = A[i-1]
    
    print(max(even(N, A1), even(N, A2), even(N, A3)))