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

Submission status: Accepted

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

def main():
    n=int(input())
    a=list(map(int,input().split()))
    #print(a)
    
    if n<4:
        print(max(a))
        sys.exit()

    if n%2:
        #dp[位置][個数]
        dp=[[0,0,0]for i in range(n-2)]
        dp[0]=a[:3]
        for i in range(2,n-1,2):
            dp[i][0]=dp[i-2][0]+a[i]
            dp[i][1]=max(dp[i-2][0],dp[i-2][1])+a[i+1]
            dp[i][2]=max(dp[i-2][0],dp[i-2][1],dp[i-2][2])+a[i+2]
        #print(dp)
        print(max(dp[-1]))

    else:
        #dp[位置][個数]
        dp=[[0,0]for i in range(n-1)]
        dp[0]=a[:2]
        for i in range(2,n-1,2):
            dp[i][0]=dp[i-2][0]+a[i]
            dp[i][1]=max(dp[i-2][0],dp[i-2][1])+a[i+1]
        #print(dp)
        print(max(dp[-1]))
main()

Submission status: Accepted

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

Submission status: Accepted

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

if n // 2 == 1:
    print(max(a))
    exit()
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: Accepted

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

if N<=3:
  print(max(A))
  exit(0)
  
INF = 10**(9+6)
if N % 2:
  # when N is odd, 2 blocks are skippable
  dp = [[-INF]*3 for i in range(N)]
  
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  dp[2][2] = A[2]
  
  for i in range(N):
    if i+2 < N:
      for j in range(3):
        if dp[i+2][j] < dp[i][j] + A[i+2]:
          dp[i+2][j] = dp[i][j] + A[i+2]
    if i+3 < N:
      for j in range(2):
        if dp[i+3][j+1] < dp[i][j] + A[i+3]:
          dp[i+3][j+1] = dp[i][j] + A[i+3]
    if i+4 < N:
      if dp[i+4][2] < dp[i][0] + A[i+4]:
        dp[i+4][2] = dp[i][0] + A[i+4]
  print(max(dp[-3][0],dp[-2][1],dp[-1][2]))
  
else:
  # when N is even, 1 block is skippable
  dp = [[-INF]*2 for i in range(N)]
  
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  
  for i in range(N):
    if i+2 < N:
      for j in range(2):
        if dp[i+2][j] < dp[i][j] + A[i+2]:
          dp[i+2][j] = dp[i][j] + A[i+2]
    if i+3 < N:
      if dp[i+3][1] < dp[i][0] + A[i+3]:
        dp[i+3][1] = dp[i][0] + A[i+3]
  print(max(dp[-2][0],dp[-1][1]))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict

INF = 10 ** 18

N, *A = map(int, read().split())
dp_not = defaultdict(lambda: -INF)
dp_take = defaultdict(lambda: -INF)
dp_not[(0, 0)] = 0

for i, x in enumerate(A, 1):
    j = (i - 1) // 2
    for n in (j, j + 1):
        dp_not[(i, n)] = max(dp_not[(i - 1, n)], dp_take[(i - 1, n)])
        dp_take[(i, n)] = dp_not[(i - 1, n - 1)] + x

print(max(dp_not[(N, N // 2)], dp_take[(N, N // 2)]))

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:
N = int(input())
A = list(map(int, input().split()))

dp = [{} for __ in range(N+1)]

dp[0][0] = 0
dp[1][0] = 0
dp[1][1] = A[0]

for i in range(2, N+1):
    for j in range((i-1)//2, (i+1)//2+1):
        app = (dp[i-2][j-1] if j-1 in dp[i-2] else -float('inf')) + A[i-1]
        napp = dp[i-1][j] if j in dp[i-1] else -float('inf')
        dp[i][j] = max(app, napp)

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

Submission status: Accepted

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

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

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

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

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

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

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
minf=-10000000000000
x=[[0,0,0] for i in range(n)]
x[0]=[0,0,a[0]]
for i in range(n-1):
    if i%2==0:
        x[i+1]=[max(x[i][0],x[i][1]),x[i][2],x[i][0]+a[i+1]]
    else:
        x[i+1]=[max(x[i][1],x[i][2]),x[i][0]+a[i+1],x[i][1]+a[i+1]]
print(max(x[-1][1],x[-1][2]) if n%2==0 else max(x[-1][0],x[-1][1]))

Submission status: Accepted

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

pick_DP = [-float('INF')] * (n//2 + 2)
unpick_DP = [-float('INF')] * (n//2 + 2)
pick_DP[0] = 0
unpick_DP[0] = 0

for i, a in enumerate(A, 1):
    mini = (i-1)//2 - 1
    if mini <= 0:
        mini = 1
    maxi = (i+1)//2

    for num in range(maxi, mini-1, -1):
        if unpick_DP[num] < pick_DP[num]:
            unpick_DP[num] = pick_DP[num]
        pick_DP[num] = max(unpick_DP[num-1] + a, pick_DP[num])

print(max(pick_DP[n//2], unpick_DP[n//2]))

Submission status: Accepted

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

pick_DP = [-float('INF')] * n
unpick_DP = [-float('INF')] * n
pick_DP[0] = 0
unpick_DP[0] = 0

for i, a in enumerate(A, 1):
    mini = (i-1)//2 - 1
    if mini <= 0:
        mini = 1
    maxi = (i+1)//2

    temp = []
    for num in range(mini, maxi+1):
        temp.append(pick_DP[num])
        pick_DP[num] = max(unpick_DP[num-1] + a, pick_DP[num])

    for num, pre_pick in enumerate(temp, mini):
        if unpick_DP[num] < pre_pick:
            unpick_DP[num] = pre_pick

print(max(pick_DP[n//2], unpick_DP[n//2]))

Submission status: Accepted

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


if __name__ == '__main__':

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

    dp = [0] * N
    dp[1] = max(A[0], A[1])
    c = A[0]

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

    print(dp[-1])

Submission status: Accepted

Solution code:
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    odds = [0] * ((n + 1) // 2 + 1)
    for i, v in enumerate(a[::2]):
        odds[i+1] = odds[i] + v
    if n % 2 == 0:
        evens = [0] * (n // 2 + 1)
        for i, v in enumerate(a[1::2]):
            evens[i+1] = evens[i] + v
        ans = -float('inf')
        for i in range(n // 2 + 1):
            ans = max(ans, odds[i] + evens[-1] - evens[i])
        print(ans)
        return
    ans = odds[-1] - odds[1]
    dp = [float('inf')] * n
    dp[0] = a[0]
    dp[1] = a[1]
    ans = max(ans, max(a[:2]) + odds[-1] - odds[2])
    for i in range(2, n):
        if i % 2 == 0:
            dp[i] = dp[i-2] + a[i]
        else:
            dp[i] = max(dp[i-2], dp[i-3]) + a[i]
            ans = max(ans, max(dp[i-1], dp[i]) + odds[-1] - odds[i//2+2])
    print(ans)

main()

Submission status: Accepted

Solution code:
n = int(input())
nums = list(map(int,input().split()))
if n == 2:
    print(max(nums[0],nums[1]))
else:
    temp =[0]
    for i in range(n):
        if i%2 == 0:
            temp += [temp[-1]+nums[i]]
    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] = temp[i//2]
        else:
            dp[i][0] = max(dp[i-2]) + nums[i]
            dp[i][1] = temp[(i-1)//2] + nums[i-1]
            dp[i][2] = -float("inf")
    print(max(dp[n-1]))

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
if n<=3:
    print(max(a))
    exit()

lacc = [0]*n
racc = [0]*n
lacc[0] = a[0]
lacc[1] = a[1]
racc[n-1] = a[n-1]
racc[n-2] = a[n-2]
for i in range(2,n):
    if i%2==0:
        lacc[i] = lacc[i-2]+a[i]
    else:
        lacc[i] = max(lacc[i-3],lacc[i-2])+a[i]
if n%2==0:
    print(max(lacc[n-2],lacc[n-1]))
    exit()
for i in range(n-3,-1,-1):
    if (n-1-i)%2==0:
        racc[i] = racc[i+2]+a[i]
    else:
        racc[i] = max(racc[i+3],racc[i+2])+a[i]
mx = max(racc[2],lacc[n-3])
for i in range(1,n-2):
    if i%2==0:
        mx = max(mx, max(lacc[i-2],lacc[i-1])+racc[i+2])
    else:
        mx = max(mx, max(racc[i+2],racc[i+3])+lacc[i-1])
print(mx)

Submission status: Accepted

Solution code:
def main():
    N=int(input())
    A=[int(_) for _ in input().split()]
    dp=[[0,0,0] for _ in range(N//2+1)]
    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:
            dp[i+1][2]=max(dp[i][2],dp[i][1],dp[i][0])+A[i*2+2]
    if N%2:
        print(max(dp[-1]))
    else:
        print(max(dp[-1][:2]))

main()

Submission status: Accepted

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

def main():
    n = int(input())
    a = list(map(int,input().split()))
    if n%2 == 0:
        ans1 = 0
        ans2 = 0
        for i in range(n):
            if i%2 == 0:
                ans1 += a[i]
            else:
                ans2 += a[i]
        ans = max(ans1,ans2)

        cuml = [0] * (n + 1)
        cumr = [0] * (n + 1)

        for i in range(n):
            if i == 0:
                cuml[i + 1] = a[i]
            else:
                cuml[i + 1] = cuml[i - 1] + a[i]
        
        for i in range(n - 1,-1,-1):
            if i == n - 1:
                cumr[i] = a[i]
            else:
                cumr[i] = cumr[i + 2] + a[i]
        
        for i in range(1,n - 2,2):
                ans = max(ans,cuml[i] + cumr[i + 2])
    
    else:
        cuml = [0] * (n + 1)
        cumr = [0] * (n + 1)
        cumr2 = [0] * (n + 1)

        for i in range(n):
            if i == 0:
                cuml[i + 1] = a[i]
            else:
                cuml[i + 1] = cuml[i - 1] + a[i]
        
        for i in range(n - 1,-1,-1):
            if i == n - 1:
                cumr[i] = a[i]
                cumr2[i] = a[i]
            else:
                cumr[i] = cumr[i + 2] + a[i]
                if i%2 == 1:
                    if i == n - 2:
                        continue
                    if i == n - 4:
                        cumr2[i] = cumr2[i + 3] + a[i]
                    else:
                        cumr2[i] = max(cumr2[i + 2],cumr[i + 3]) + a[i]

        cumr.append(0)
        ans = -INF
        for i in range(n):
            ans = max(ans,cuml[i] + cumr[i + 2])
            if i <= n - 6 and i%2 == 1:
                ans = max(ans,cuml[i] + cumr2[i + 2])
            if i <= n - 4 and i%2 == 1:
                ans = max(ans,cuml[i] + cumr[i + 3])
    
    print(ans)

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
dp=[[0]*n for _ in range(3)]
for i in range(n):
	if i%2:
		dp[1][i]=max(dp[2][i-3]+a[i],dp[1][i-2]+a[i])
	elif i>1:
		dp[0][i]=max(dp[0][i-2]+a[i],dp[1][i-3]+a[i],dp[2][i-4]+a[i])
		dp[2][i]=dp[2][i-2]+a[i]
	else:
		dp[2][i]=dp[2][i-2]+a[i]
print(max(dp[2][-3],dp[1][-2],dp[0][-1]) if n%2 else max(dp[1][-1],dp[2][-2]))

Submission status: Accepted

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

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

INF = 10**18
limit = 4
S = (2*limit+3)
dpb = [-INF]*S
dpw = [-INF]*S
dpw[0] = 0
for i in range(N):
    a = A[i]
    dpb2 = [-INF]*S
    dpw2 = [-INF]*S
    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: Accepted

Solution code:

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

if n == 2 or n == 3:
    print(max(a_list))
elif 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 == 1 and i >= n-2:
                pass
            elif j == 1:
                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: Accepted

Solution code:
input()
aa = list(map(int, input().split()))
state = {(0,False)}
skipmax = len(aa)%2 + 1
state_all = {(i, True) for i in range(skipmax+1)}.union({(j, False) for j in range(skipmax+1)})
dp_0 = {a:None for a in state_all }
dp_0[(0,False)] = 0
skipcount = 0

def getmax(a, b):
    if a is None:
        return b
    if b is None:
        return a
    return max(a,b)

for i,a in enumerate(aa):
    dp_1 = {}
    for s in state_all:
        if s[1] & (dp_0[(s[0], False)] is not None):
            dp_1[s] = dp_0[(s[0], False)] + a
            continue
        dp_1[s] = getmax(dp_0[(s[0], True)], dp_0.get((s[0]-1, False), None))
    dp_0 = dp_1.copy()
if len(aa)%2:
    print(getmax(dp_0[(2,True)], dp_0[(1,False)]))
else:
    print(getmax(dp_0[(1,True)], dp_0[(0,False)]))

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 18

dp = defaultdict(lambda: -INF)
dp[(0, 0, 0)] = 0

for i, e in enumerate(a, 1):
    for j in range((i - 1) // 2, (i + 1) // 2 + 1):
        dp[(i, j, 0)] = max(dp[(i-1, j, 0)], dp[(i-1, j, 1)])
        dp[(i, j, 1)] = dp[(i-1, j-1, 0)] + e

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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

B = [{} for _ in range(N+1)]


for i in range(1,N+1):
  if i == 1:
    B[1][0] = 0
    B[1][1] = A[0]
  elif i == 2:
    B[2][1] = max(A[0],A[1])
    if N % 2 == 1:
      B[2][0] = 0
  else:
    if N % 2 == 0:
      for j in range(math.ceil((i-1)/2),(i+1)//2+1):
        m1 = B[i-2][j-1]+A[i-1] if j-1 in B[i-2] else -float('inf')
        m2 = B[i-1][j] if j in B[i-1] else -float('inf')
        B[i][j] = max(m1,m2)
    else:
      for j in range(math.ceil((i-2)/2),(i+1)//2+1):
        m1 = B[i-2][j-1]+A[i-1] if j-1 in B[i-2] else -float('inf')
        m2 = B[i-1][j] if j in B[i-1] else -float('inf')
        B[i][j] = max(m1,m2)
      

print(B[N][N//2])

Submission status: Accepted

Solution code:
n = int(input())
a = [int(ai) for ai in input().split()]
if n % 2 == 0:
    s = [0,0]
    for i in range(n // 2):
        s = [max(s[q] for q in range(p+1)) + a[i*2+p] for p in range(2)]
    print(max(s))
else:
    s = [0,0,0]
    for i in range(n // 2):
        s = [max(s[q] for q in range(p+1)) + a[i*2+p] for p in range(3)]
    print(max(s))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
a=[int(j) for j in input().split()]
p=[0]*n
d=[0]*n
for i in range(n):
    p[i]=a[i]+p[i-2]
    if (i&1):
        d[i]=max(p[i-1],a[i]+d[i-2])
    else:
        d[i]=max(d[i-1],a[i]+d[i-2])
print(d[-1])

Submission status: Accepted

Solution code:
N = int(input())
A = [0, 0]+list(map(int, input().split()))+[0, 0]
skip = N-2*(N//2)+1
dp = [[-10**18]*(skip+1) for _ in range(N+4)]

for i in range(2):
    for j in range(skip+1):
        dp[i][j] = 0

for i in range(2, N+4):
    for j in range(skip+1):
        dp[i][j] = max(dp[i][j], dp[i-2][j]+A[i])
        
        if i>=3 and j+1<=skip:
            dp[i][j+1] = max(dp[i][j+1], dp[i-3][j]+A[i])
        
        if i>=4 and j+2<=skip:
            dp[i][j+2] = max(dp[i][j+2], dp[i-4][j]+A[i])

print(dp[N+3][skip])

Submission status: Accepted

Solution code:
n=int(input());l=list(map(int,input().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&1else d[i-1],l[i]+d[i-2])
print(d[-1])

Submission status: Accepted

Solution code:
n=int(input());l=list(map(int,input().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: Accepted

Solution code:
n=int(input());l=list(map(int,input().split()));p=[0]*n;d=[0]*n;p[0]=l[0]
for i in range(1,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: Accepted

Solution code:
n=int(input());l=list(map(int,input().split()));p=[0]*n;d=[0]*n;p[0]=l[0]
for i in range(1,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]if i>1else 0))
print(d[-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

if N%2==0:
    dp = [[0]*2 for _ in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    
    for i in range(2, N):
        if i==2:
            dp[i][0] = dp[i-2][0]+A[i]
        else:
            dp[i][0] = dp[i-2][0]+A[i]
            dp[i][1] = max(dp[i-3][0]+A[i], dp[i-2][1]+A[i])
    
    print(max(dp[N-2][0], dp[N-1][1]))
else:
    dp = [[0]*3 for _ in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    
    for i in range(2, N):
        if i==2:
            dp[i][0] = dp[i-2][0]+A[i]
        elif i==3:
            dp[i][0] = dp[i-2][0]+A[i]
            dp[i][1] = max(dp[i-2][1]+A[i], dp[i-3][0]+A[i])
        else:
            dp[i][0] = dp[i-2][0]+A[i]
            dp[i][1] = max(dp[i-3][0]+A[i], dp[i-2][1]+A[i])
            dp[i][2] = max(dp[i-4][0]+A[i], dp[i-3][1]+A[i], dp[i-2][2]+A[i])
    
    print(max(dp[N-3][0], dp[N-2][1], dp[N-1][2]))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)

def solve(n,a):
    wa=0
    for i in range(n):
        if(i%2==0):
            wa+=a[i]
    kotae=wa
    for i in range(n//2):
        wa+=a[(n//2-i-1)*2+1]
        wa-=a[(n//2-i-1)*2]
        if(wa>kotae):
            kotae=wa
    return kotae

def dfs(n,a,k):
    global zen
    zen.append([n,k])
    if(k==1):
        return max(a)
    ari=a[n-1]+dfs(n-2,a[:n-2],k-1)
    if(n==k*2-1):
        return ari
    nasi=dfs(n-1,a[:n-1],k)
    return max(ari,nasi)

n=int(input())

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

if(n%2==0):
    print(solve(n,a))
else:
    data=[[a[0],a[0]],[max(a[:2]),max(a[:2])]]
    #data.append([max(a[:3]),sum(a[:3])-min(a[:3])])
    data.append([max(a[:3]),a[0]+a[2]])
    for i in range(3,n):
        if(i%2==1):
            ari=a[i]+data[i-2][0]
            nasi=data[i-1][1]
            saiyo=max(ari,nasi)
            data.append([saiyo,saiyo])
        else:
            ooi=a[i]+data[i-2][1]
            nasi=data[i-1][1]
            ari=a[i]+data[i-2][0]
            sukunai=max(ari,nasi)
            data.append([sukunai,ooi])
    print(data[n-1][0])

Submission status: Accepted

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

dp = [{} for _ in range(N + 2)]
dp[0][0] = 0
dp[-1][0] = 0

for i in range(1, N + 1):
    f = (i - 1) // 2
    t = (i + 1) // 2
    for j in range(f, t + 1):
        var1 = dp[i - 2][j - 1] + A[i - 1] if j - 1 in dp[i - 2] else -float('inf')
        var2 = dp[i - 1][j] if j in dp[i - 1] else -float('inf')
        dp[i][j] = max(var1, var2)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [{} for _ in range(N+1)]
INF = -float('inf')
for i in range(1,N+1):
    mid = i//2
    dp[i][mid-2],dp[i][mid-1],dp[i][mid],dp[i][mid+1],dp[i][mid+2]=INF,INF,INF,INF,INF
dp[1][1] = A[0]
dp[2][1] = max(A[1],dp[1][1])
dp[1][0],dp[2][0]=0,0

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

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

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


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

    @lru_cache(None)
    def f(i, j):
        if i < 0 or j < 0:
            return -INF
        if i == 0:
            return -INF
        if abs(j - i // 2 - 1) >= 2:
            return -INF
        if j == 0:
            return 0
        if j == 1:
            return max(A[:i])
        return max(A[i - 1] + f(i - 2, j - 1), f(i - 1, j))

    print(f(N, math.floor(N / 2)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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

if n == 1 or n == 2 or n == 3:
    print(max(A))
    sys.exit()

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(4, n):
    for j in range(2):
        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])

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