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: Accepted

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

INF = 10**17

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

dp = [[-INF]*3 for _ in range(N)]

for i, a in enumerate(A):
    if i == 0:
        dp[i][2] = a
    elif i == 1:
        dp[i][0] = max(a, dp[i-1][1])
    elif i == 2:
        dp[i][1] = a
        dp[i][2] = dp[0][2] + a
    elif (i+1)%2 == 0:
        dp[i][0] = max(dp[i-3][2], dp[i-2][0]) + a
    else:
        dp[i][1] = max([dp[i-4][2], dp[i-3][0], dp[i-2][1]]) + a
        dp[i][2] = dp[i-2][2] + a

if N%2 == 0:
    ans = dp[N-1][0]
    if N > 1:
        ans = max(ans, dp[N-2][2])
else:
    ans = dp[N-1][1]
    if N > 1:
        ans = max(ans, dp[N-2][0])
    if N > 2:
        ans = max(ans, dp[N-3][2])
    # tmp = 0
    # for i in reversed(range(N)):
    #     if i%2 == 0 and i >= 2:
    #         tmp += A[i]
    #         ans = max(ans, dp[i-2][1]+tmp)

print(ans)

Submission status: Accepted

Solution code:
import sys

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

def main():
    inf=10**16
    n=II()
    aa=LI()
    if n%2:
        dp=[[-inf]*3 for _ in range(n)]
        dp[0][2]=0
        dp[0][0]=aa[0]
        dp[1][1]=aa[1]
        for i,a in enumerate(aa[2:],1):
            if i-1>=0:dp[i+1][0]=dp[i-1][0]+a
            if i-2>=0:dp[i+1][1]=max(dp[i-2][0],dp[i-1][1])+a
            elif i-1>=0:dp[i+1][1]=dp[i-1][1]+a
            if i-3>=0:dp[i+1][2]=max(dp[i-3][0],dp[i-2][1],dp[i-1][2])+a
            elif i - 2 >= 0: dp[i + 1][2] = max(dp[i - 2][1], dp[i - 1][2]) + a
            elif i - 1 >= 0: dp[i + 1][2] = dp[i - 1][2] + a
        ans=max(dp[-1][2],dp[-2][1])
        if n>2:ans=max(ans,dp[-3][0])
    else:
        dp=[[-inf]*2 for _ in range(n)]
        dp[0][0]=aa[0]
        dp[1][1]=aa[1]
        for i,a in enumerate(aa[2:],1):
            dp[i+1][0]=dp[i-1][0]+a
            if i-2>=0:dp[i+1][1]=max(dp[i-2][0],dp[i-1][1])+a
            elif i - 1 >= 0: dp[i + 1][1] = dp[i - 1][1] + a
        ans=max(dp[-1][1],dp[-2][0])
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

SUM=[0]*(N+1)
for i in range(N-1,-1,-1):
    SUM[i]=SUM[i+1]

    if (N-i)%2==1:
        SUM[i]+=A[i]

#print(SUM)

ADICT=dict()

def calc(i,select):
    if ADICT.get((i,select))!=None:
        return ADICT.get((i,select))
    rest=N-i

    if rest==0 or select==0:
        ADICT[(i,select)]=0
        return 0

    if rest%2==1 and rest//2+1==select:
        ADICT[(i,select)]=SUM[i]
        return SUM[i]
    
    elif rest%2==0 and rest//2==select:
        ADICT[(i,select)]=max(calc(i+1,select),A[i]+calc(i+2,select-1))
        return ADICT[(i,select)]

    elif rest%2==1 and rest//2==select:
        ADICT[(i,select)]=max(calc(i+1,select),A[i]+calc(i+2,select-1))
        return ADICT[(i,select)]

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

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
odd = list(accumulate([0] + A[::2]))
even = list(accumulate([0] + A[::-1][::2]))
ans = max(odd[i] + even[N//2-i] for i in range(N//2+1))
if N % 2 == 1:
    dp = [0] * (N//2+1)
    for i in range(0, N-1, 2):
        dp[i//2+1] = max(odd[i//2+1], dp[i//2] + A[i+1])
    ans2 = max(dp[i] + even[N//2-i] for i in range(N//2+1))
    ans = max(ans, ans2)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[[-10**15, -10**15] for i in range(4)] for j in range(n+1)]
#dp = [[[0,0] for i in range(4)] for j in range(n+1)]

dp[0][0][0] = 0


for i in range(n):
    for j in range(4):
        for k in range(2):
            if j == 3:
                dp[i+1][3][0] = max(dp[i][3][1],dp[i+1][3][0])
                dp[i+1][3][1] = max(dp[i][3][0]+a[i],dp[i+1][3][1])
            elif j == 2:
                dp[i+1][2][0] = max(dp[i][2][1],dp[i+1][2][0])
                dp[i+1][2][1] = max(dp[i][2][0]+a[i],dp[i+1][2][1])
                dp[i+1][3][0] = max(dp[i][2][0],dp[i+1][3][0])
            elif j == 1:
                dp[i+1][1][0] = max(dp[i][1][1],dp[i+1][1][0])
                dp[i+1][1][1] = max(dp[i][1][0]+a[i],dp[i+1][1][1])
                dp[i+1][2][0] = max(dp[i][1][0],dp[i+1][2][0])
            else:
                dp[i+1][0][0] = max(dp[i][0][1],dp[i+1][0][0])
                dp[i+1][0][1] = max(dp[i][0][0]+a[i],dp[i+1][0][1])
                dp[i+1][1][0] = max(dp[i][0][0],dp[i+1][1][0])


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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin

input = stdin.readline

n = int(input())
a = [int(x) for x in input().split()]
dp = [[0] * 3 for x in range(n)]

dp[0][0] = a[0]
dp[1][1] = a[1]


if n > 2:
    dp[2][0] = a[0] + a[2]
    dp[2][2] = a[2]

if n > 3:
    dp[3][1] = max(a[0] + a[3], a[1] + a[3])

for x in range(4, n):
    if x % 2 == 0:
        dp[x][0] = dp[x - 2][0] + a[x]
    dp[x][1] = max(dp[x - 2][1] + a[x], dp[x - 3][0] + a[x])
    dp[x][2] = max(dp[x - 2][2] + a[x], dp[x - 3][1] + a[x], dp[x - 4][0] + a[x])


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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
if n%2 == 0:
  a.append(-float("inf"))
  n += 1
if n == 3:
  print(max(a))
  exit()
p0 = a[0]
z0 = -float("inf")
z1 = a[1]
y0 = a[0]+a[2]
y1 = -float("inf")
y2 = a[2]
x0 = -float("inf")
x1 = max(p0,z1)+a[3]
x2 = -float("inf")
for i in range(4,n-1):
  w0 = y0+a[i]
  w1 = max(y1,z0)+a[i]
  w2 = max(y2,z1,p0)+a[i]
  p0 = z0
  z0 = y0
  z1 = y1
  y0 = x0
  y1 = x1
  y2 = x2
  x0 = w0
  x1 = w1
  x2 = w2
w0 = y0+a[n-1]
w1 = max(y1,z0)+a[n-1]
w2 = max(y2,z1,p0)+a[n-1]
print(max(y0,x1,w2))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
s = [0]*N
for i in range(N):
    s[i] = s[i-2]+A[i]

dp = [0]*N
dp[1] = max(A[0],A[1])
if N>=3:
    dp[2] = max(A[0],A[1],A[2])
for n in range(3,N):
    if n%2==1:
        dp[n] = max(A[n]+dp[n-2],s[n-1])
    else:
        dp[n] = max(A[n]+dp[n-2],A[n-1]+dp[n-3],s[n-2])

print(dp[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**18

n = int(input())
a = [int(item) for item in input().split()]


# dp[i-th][wait num][used / not used]
dp = [[[-INF] * 2 for _ in range(3)] for _ in range(n+1)]
dp[0][0][0] = 0

for i in range(n):
    # use in i
    for j in range(3):
        dp[i+1][j][1] = max(dp[i+1][j][1] ,dp[i][j][0] + a[i])
    # rest in i
    for j in range(2):
        dp[i+1][j+1][0] = max(dp[i+1][j+1][0] ,dp[i][j][0])
    # not use in i
    for j in range(3):
        dp[i+1][j][0] = max(dp[i][j][1], dp[i+1][j][0])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

from functools import lru_cache

@lru_cache(None)
def dfs(p, remain):

    n = len(arr)

    if remain == 0 or p >= n:
        return 0

    if remain == 1:
        return max(arr[p:])
        
    len_remain = n - (p + 1)

    t = -float('inf')
    if (remain - 1) * 2 + 1 <= len_remain:
        t = dfs(p + 1, remain)

    t2 = arr[p] + dfs(p + 2, remain - 1)

    return max(t, t2)

    


n = int(input())

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

ans = dfs(0, n // 2)

print (ans)

Submission status: Accepted

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

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

if n % 2 == 0:
    inf = - float('inf')
    dp = [[inf, inf] for _ in range(n)]
    dp[0][0] = a[0]
    dp[1][1] = a[1]
    dp[2][0] = a[0] + a[2]

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

    #print(dp)
    print(max(dp[n-1][1], dp[n-2][0]))
    exit()

inf = - float('inf')
dp = [[inf, inf, inf] for _ in range(n)]
dp[0][0] = a[0]
dp[1][1] = a[1]
dp[2][0] = a[0] + a[2]
dp[2][2] = a[2]
dp[3][1] = max(a[0], a[1]) + a[3]

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

ans = max(dp[n-1][2], dp[n-2][1])
print(max(ans, dp[n-3][0]))

Submission status: Accepted

Solution code:
from itertools import accumulate


def solve_odd(n, aaa):
    INF = 10 ** 18
    p0, p1, p2, a0, a1, a2 = INF, INF, INF, INF, INF, 0
    for a in aaa:
        n2 = min(INF, p2 + a)
        n1 = min(INF, a2 + a, p1 + a)
        n0 = min(INF, a1 + a, p0 + a)
        p0, p1, p2, a0, a1, a2 = a0, a1, a2, n0, n1, n2
    return sum(aaa) - min(p0, a1)


def solve_even(n, aaa):
    fwd = [0] + list(accumulate(aaa[::2]))
    bwd = [0] + list(accumulate(aaa[::-2]))
    bwd.reverse()
    return max(f + b for f, b in zip(fwd, bwd))


n = int(input())
aaa = list(map(int, input().split()))
if n % 2 == 0:
    print(solve_even(n, aaa))
else:
    print(solve_odd(n, aaa))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
# sys.setrecursionlimit(10**8)

def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]

# def comp0(n, aList):
# 	num=n//2
# 	score=[[None for _ in range(num)] for i in range(n)]
# 	
# 	for i in range(n):
# 		
# 		if i==0:
# 			score[i][0]=aList[i]
# 		else:
# 			score[i][0]=max(aList[i], score[i-1][0])
# 			
# 		for j in range(1, num):
# 			nextScore=[]
# 			if i>=1:
# 				s=score[i-1][j]
# 				if s is not None:
# 					nextScore.append(s)
# 			if i>=2:
# 				s=score[i-2][j-1]
# 				if s is not None:
# 					s+=aList[i]
# 					nextScore.append(s)
# 			if len(nextScore)>0:
# 				nextScore=max(nextScore)
# 				score[i][j]=nextScore
# 	
# # 		print(i, aList[i], *[str(s) for s in score[i]], sep="\t")
# 	
# 	print(score[-1][-1])
	
	
def comp(n, aList):
	num=n//2
	score=[[None for _ in range(num)] for i in range(3)]
# 	base=[0 for _ in range(num)]
	
	for i in range(n):
		for j in range(max(0, num-(n-i)//2-1), min(i//2+1,num)):
			if j==0:
				if i==0:
					ns=aList[i]
				else:
					ns=max(aList[i], score[(i-1)%3][0])
			else:
				nextScore=[]
				if i>=1:
					s=score[(i-1)%3][j]
					if s is not None:
						nextScore.append(s)
				if i>=2:
					s=score[(i-2)%3][j-1]
					if s is not None:
						s+=aList[i]
						nextScore.append(s)
				if len(nextScore)>0:
					ns=max(nextScore)
			
			score[i%3][j]=ns
	
# 		print(i, *[str(s) for s in score[i%3]], sep="\t")
	
	print(score[(n-1)%3][-1])


def main():
	n=int(nextLine())
	aList=nextIntList()

# 	import numpy as np
# 	n=200000
# # 	aList=list(np.random.randint(-1000000000, 1000000001, n))
# # 	n=22
# 	aList=list(np.random.randint(-9, 10, n))
	
	comp(n, aList)
# 	comp0(n, aList)
	
	
if __name__=="__main__":
	main()

Submission status: Accepted

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N%2:
    a=[None]*N
    b=[None]*N
    c=[None]*N
    a[0]=A[0]
    b[1]=A[1]
    c[2]=A[2]
    for i in range(2,N-2,2):
        a[i]=a[i-2]+A[i]
    for i in range(3,N,2):
        b[i]=max(a[i-3],b[i-2])+A[i]
    for i in range(4,N,2):
        c[i]=max(a[i-4],b[i-3],c[i-2])+A[i]
    print(max(a[-3],b[-2],c[-1]))
else:
    a=[None]*N
    b=[None]*N
    a[0]=A[0]
    for i in range(2,N,2):
        a[i]=a[i-2]+A[i]
    b[1]=A[1]
    for i in range(3,N,2):
        b[i]=max(a[i-3],b[i-2])+A[i]
    print(max(a[-2],b[-1]))

Submission status: Accepted

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################

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

imp = -999999999999999999

dp = [[-1e30,-1e30,-1e30,-1e30] for i in range(n)]
#donthave-Small, donthave-Big, have-Small, have-Big

dp[0][0] = 0
dp[0][1] = imp
dp[0][2] = imp
dp[0][3] = a[0]
dp[1][0] = 0
dp[1][1] = dp[0][3]
dp[1][2] = imp
dp[1][3] = a[1]

for ii in range(n-2):
    i = 2+ii
    must = i//2
    if(i%2==0):
        dp[i][0] = max(dp[i-1][1],dp[i-1][3])
        dp[i][1] = imp
        dp[i][2] = dp[i-1][0] + a[i]
        dp[i][3] = dp[i-1][1] + a[i]
    else:
        dp[i][0] = max(dp[i-1][0],dp[i-1][2])
        dp[i][1] = max(dp[i-1][1],dp[i-1][3])
        dp[i][2] = imp
        dp[i][3] = dp[i-1][0] + a[i]
        
if(n%2==0):
    print(max(dp[-1][1],dp[-1][3]))
else:
    print(max(dp[-1][0],dp[-1][2]))

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    if N % 2 == 0:
        if N == 2: print(max(A))
        else:
            DP = [[-10 ** 20, -10 ** 20] for _ in range(N)]
            DP[0][0] = A[0]
            DP[1][1] = A[1]
            for i in range(2, N):
                DP[i][0] = max(DP[i][0], DP[i-2][0] + A[i])
                DP[i][1] = max(DP[i][1], DP[i-2][1] + A[i])
                if i > 2: DP[i][1] = max(DP[i][1], DP[i-3][0] + A[i])
            print(max(DP[N-2][0], DP[N-1][1]))
    else:
        DP = [[-10**20, -10**20, -10**20] for _ in range(N)]
        DP[0][0] = A[0]
        DP[1][1] = A[1]
        DP[2][2] = A[2]
        DP[2][0] = A[0] + A[2]
        for i in range(3, N):
            DP[i][0] = max(DP[i-2][0] + A[i], DP[i][0])
            DP[i][1] = max(DP[i-2][1] + A[i], DP[i][1])
            DP[i][2] = max(DP[i-2][2] + A[i], DP[i][2])
            if i > 2: 
                DP[i][1] = max(DP[i][1], DP[i-3][0] + A[i])
                DP[i][2] = max(DP[i][2], DP[i-3][1] + A[i])
        ans = max(DP[N-1][2], DP[N-2][1])
        ans = max(ans, DP[N-3][0])

        print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:

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

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

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
if n%2 == 0:
    dmax = 0
    ans = sum(A[::2])
    d = [0]*(n//2 + 1)
    for i in range(n//2):
        d[i+1] = d[i] + A[-2*i-1] - A[-2*i-2]
        dmax = max(dmax, d[i+1])
    print(ans + dmax)
else:
    d1 = [0]*(n//2 + 1)
    d1max = [0]*(n//2 + 1)
    d2 = [0]*(n//2 + 1)
    d2max = 0
    ans = sum(A[:-2:2])
    for i in range(n//2):
      d1[i+1] = d1[i] + A[-2*i-1] - A[-2*i-2]
      d1max[i+1] = max(d1max[i], d1[i+1])
      d2[i+1] = d2[i] + A[-2*i-2] - A[-2*i-3]
      d2max = max(d2max, d2[i+1] + d1max[i+1])
    print(ans + d2max)

Submission status: Accepted

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

ans = sum(A[1::2])
dA = []
for a1, a2 in zip(A, A[1:]):
    dA.append(a1 - a2)

max_cum_l = 0
cum_l = 0
L = [0]
for idx_l in range(0, N - 1, 2):
    cum_l += dA[idx_l]
    max_cum_l = max(max_cum_l, cum_l)
    L.append(max_cum_l)
max_cum_r = 0
cum_r = 0
R = [0]
for idx_r in range(N - 2, -1, -2):
    cum_r -= dA[idx_r]
    max_cum_r = max(max_cum_r, cum_r)
    R.append(max_cum_r)
R.reverse()
if N%2:
    ma = -(1<<60)
    for l, r in zip(L, R):
        if ma < l+r:
            ma = l+r
    print(ans + ma)
else:
    print(max(L) + ans)

Submission status: Accepted

Solution code:
import functools
import sys

sys.setrecursionlimit(1000000)

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

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


sol = dp(0, N // 2)

print(sol)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
k = n//2
d = dict()
d[(-2,0)] = 0
for i in range(n):
    nxt = dict()
    discard = []
    for (prev, cnt), score in d.items():
        if i-prev == 1:
            continue
        if cnt == k:
            continue
        nprev = i
        ncnt = cnt+1
        nscore = score+a[i]
        tmp = (nprev, ncnt)
        if tmp not in nxt or nxt[tmp] < nscore:
            nxt[tmp] = nscore
        r = n-1-i
        if cnt + (r+1)//2 < k:
            discard.append((prev, cnt))
    for key, value in nxt.items():
        d[key] = value
    for key in discard:
        d.pop(key)
ans = -float("inf")
for key, value in d.items():
    if key[1] == k:
        ans = max(ans, value)
print(ans)

Submission status: Accepted

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())
A = lmi()


# dp = [[-INF]*3 for _ in range(N)]
def solve2():
    """

6
1 2 3 4 5 6
>> 12
6
2 1 3 4 5 6
>> 12
    :return:
    """
    assert N % 2 == 0
    even = [0]
    odd = [0]
    for v in range(N):
        if v % 2 == 0:
            even.append(even[-1] + A[v])
        else:
            odd.append(odd[-1] + A[v])

    # print(even)
    # print(odd)
    ans = 0
    for i in range(len(even)):
        ans = max(ans, even[i] + odd[-1] - odd[i])
    print(ans)


def solve():
    # dp[N][ignored]
    dp = [[-INF] * 3 for _ in range(N // 2 + 1)]
    dp[0][0] = 0
    dp[0][1] = 0
    dp[0][2] = 0

    for v in range(N):
        for ignore_count in range(3):
            if ignore_count == 0:
                flag = (v < N - 1 and v % 2 == 0)
                dp_slice = v // 2
            elif ignore_count == 1:
                flag = (v % 2 == 1)
                dp_slice = v // 2
            else:  # ignore_count == 2:
                flag = (v > 1 and v % 2 == 0)
                dp_slice = v // 2 - 1
            if flag:
                dp[dp_slice + 1][ignore_count] = max(dp[dp_slice][ignore_count] + A[v], dp[dp_slice + 1][ignore_count])
                if ignore_count != 2:
                    dp[dp_slice + 1][ignore_count + 1] = max(dp[dp_slice + 1][ignore_count],
                                                             dp[dp_slice + 1][ignore_count + 1])
                # if ignore_count==0:
                #     dp[dp_slice + 1][2] = max(dp[dp_slice + 1][ignore_count],
                #                                              dp[dp_slice + 1][2])

                # if ignore_count:
                #     dp[dp_slice + 1][ignore_count] = dp[dp_slice][ignore_count - 1]
    if N % 2 == 1:
        print(max(dp[-1]))
    else:
        print(max(dp[-1][:2]))


if N % 2 == 1:
    solve()
else:
    solve()

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n = ni()
a = nl()
dp = [[0]*3 for _ in range(n+5)]
t = n%2
for i in range(n):
    dp[i][0] = dp[i-2][0] + a[i]
    dp[i][1] = max(dp[i-2][1], dp[i-3][0]) + a[i]
    if t:
        dp[i][2] = max(dp[i-2][2], dp[i-3][1], dp[i-4][0]) + a[i]
if t:
    print(max(dp[n-3][0], dp[n-2][1], dp[n-1][2]))
else:
    print(max(dp[n-2][0], dp[n-1][1]))

Submission status: Accepted

Solution code:
n = int(input())
a = [int(num) for num in input().split()]
dp = [[0,0,0] for _ in range(n//2+1)]

#dp[0] = [a[0],a[1],a[2]]

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
inf = 10**18
if n%2 == 0:
    dp = [[-inf]*2 for _ in range(n+2)]
    dp[-2][0] = 0
    for i in range(n):
        for j in range(2):
            for k in range(2):
                if j-k>=0:
                    dp[i][j] = max(dp[i][j], dp[i-k-2][j-k]+a[i])
    print(max(max(dp[n-1]), max(dp[n-2][:1])))
else:
    dp = [[-inf]*3 for _ in range(n+2)]
    dp[-2][0] = 0
    for i in range(n):
        for j in range(3):
            for k in range(3):
                if j-k>=0:
                    dp[i][j] = max(dp[i][j], dp[i-k-2][j-k]+a[i])
    print(max(max(dp[n-1][1:]), max(dp[n-2][:2]), max(dp[n-3][:1])))

Submission status: Accepted

Solution code:
from collections import *
import sys
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N = ni()
A = nl()
if N%2 == 0:
    v1 = sum(A[::2])
    v2 = sum(A[1::2])
    M = max(v1, v2)
    l = 0
    for i in range(0, N, 2):
        v2 -= A[i+1]
        l += A[i]
        M = max(l + v2, M)
    print(M)
else:
    INF = 10**18
    DP = [[[-INF]*N for _ in range(3)] for _ in range(2)]
    DP[1][0][0] = A[0]
    DP[0][1][0] = 0
    for i in range(1, N):
        DP[1][0][i] = A[i] + DP[0][0][i-1]
        DP[1][1][i] = A[i] + DP[0][1][i-1]
        DP[1][2][i] = A[i] + DP[0][2][i-1]
        DP[0][0][i] = DP[1][0][i-1]
        DP[0][1][i] = max(DP[0][0][i-1], DP[1][1][i-1])
        DP[0][2][i] = max(DP[0][1][i-1], DP[1][2][i-1])

    print(max(DP[0][1][N-1], DP[1][1][N-1], DP[1][2][N-1]))

Submission status: Accepted

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

INF = 10 ** 17

start = []
start.append((0, l[0]))
start.append((0,max(l[0],l[1])))

for i in range(2, N):
    if i % 2 == 0:
        left = [start[-1][1], start[-2][0] + l[i]]
        right = [start[-2][1] + l[i]]
    else:
        left = [start[-1][0], start[-2][0] + l[i]]
        right = [start[-1][1], start[-2][1] + l[i]]
    start.append((max(left),max(right)))

if N % 2:
    print(start[-1][0])
else:
    print(start[-1][1])

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()

if n % 2 == 0:
    pre = [0]
    for i in range(0, n, 2):
        pre.append(pre[-1] + a[i])
    suf = [0]
    b = a[::-1]
    for i in range(0, n, 2):
        suf.append(suf[-1] + b[i])
    ans = -99999999999999999
    for i in range(len(pre)):
        ans = max(ans, pre[i] + suf[-1-i])
    print(ans)
else:
    pre = [0]
    for i in range(0, n, 2):
        pre.append(pre[-1] + a[i])
    # pre2 = [0]
    # for i in range(1, n, 2):
    #     pre2.append(pre2[-1] + a[i])
    ans = -999999999999999999
    mx = 0
    for i in range(1, n, 2):
        ans = max(ans, mx + pre[-1] - pre[i//2+1])
        mx = max(mx + a[i], pre[i//2+1])
    ans = max(ans, mx)
    print(ans)

Submission status: Runtime Error

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

inf = float('inf')

# 累積和
if n % 2 == 0:
  	while True:
      pass
    l_even = [0]
    l_odd = [0]
    for i in range(n):
        if i % 2 == 0:
            l_even.append(l_even[-1] + a[i])
        else:
            l_odd.append(l_odd[-1] + a[i])
    ans = -inf
    for i in range(n // 2 + 1):
        if ans < l_even[i] + l_odd[-1] - l_odd[i]:
            ans = l_even[i] + l_odd[-1] - l_odd[i]
    print(ans)
    exit()

# dp[i] = i回ずらしを使った時の最大値
# 1個ずつdpを更新
# i = 0, 1, 2
dp = [a[0], a[1], a[2]]
for i in range(2, n, 2):
    try:
        dp[2] = max([dp[2] + a[i+2], dp[1] + a[i+2]])
    except:
        pass
    try:
        dp[1] = max([dp[1] + a[i+1], dp[0] + a[i+1]])
    except:
        pass
    dp[0] += a[i]

print(max(dp))

Submission status: Runtime Error

Solution code:
#![allow(unused_imports, non_snake_case)]
use proconio::{
    input, fastout,
    marker::{Chars, Bytes, Usize1}
};

macro_rules! max {($ a : expr $ (, ) * ) => {{$ a } } ; ($ a : expr , $ b : expr $ (, ) * ) => {{std :: cmp :: max ($ a , $ b ) } } ; ($ a : expr , $ ($ rest : expr ) ,+ $ (, ) * ) => {{std :: cmp :: max ($ a , max ! ($ ($ rest ) ,+ ) ) } } ; }

#[fastout]
fn main() {
    input! {
        n: usize,
        a: [usize; n]
    }
    let mut dp = vec![vec![0; 3]; n+4];
    for i in 0..n{
        dp[i + 4][0] = dp[i + 2][0] + a[i];
        dp[i + 4][1] = max!(dp[i+2][1], dp[i+1][0]) + a[i];
        if n & 1 > 0 {
            dp[i + 4][2] = max!(dp[i + 2][2], dp[i + 1][1], dp[i][0]) + a[i];
        }
    }
    if n & 1 > 0 {
        println!("{}", max!(dp[n+1][0], dp[n+2][1], dp[n+3][2]));
    } else {
        println!("{}", max!(dp[n+2][0], dp[n+3][1]));
    }
}

Submission status: Runtime Error

Solution code:
import itertools

n=int(input())
a=list(map(int,input().split()))
odd=[]
even=[]
for i in range(n):
  if i%2==0:
    odd+=[i]
  else:
    even+=[i]
    
if n%2==0:
  print(max(sum(odd),sum(even)))

else:
  ans=sum(odd)-min(odd)
  for i in range(n//2+1):

Submission status: Runtime Error

Solution code:
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


INF=10**20
def main():
    N=ii()
    A=list(mi())

    sel_count = N//2
    X = []
    for i,a in enumerate(A):
        X.append((-1*a,i))

    heapq.heapify(X)
    i = 0
    # selected = []
    ans = 0
    ng_index = set()
    while X and i < sel_count:
        current_max, j = heapq.heappop(X)
        current_max *= -1

        if j in ng_index: continue
        ans += current_max
        
        ng_index.add(j-1)
        ng_index.add(j)
        ng_index.add(j+1)

        i += 1
    
    assert i == sel_count
    print(ans)

    



if __name__ == "__main__":
    main()