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 = [int(x) for x in input().split()]

sm_e = []
sm_o = []

e = 0
o = 0

for i in range(n):
    if i % 2 == 0:
        e += a[i]
        sm_e.append(e)
    else:
        o += a[i]
        sm_o.append(o)

tot_e = sm_e[-1]
tot_o = sm_o[-1]

m = len(sm_o)

if n % 2 == 0:
    ans = max(tot_e, tot_o)
    for i in range(m):
        ans = max(ans, sm_e[i] + tot_o - sm_o[i])
    # for i in range(m-1):
    #     ans = max(ans, sm_o[i] + tot_e - sm_e[i+1])
    print(ans)
    exit()

ans = tot_o

for i in range(m):
    ans = max(ans, sm_e[i]+tot_o-sm_o[i])


l = [0]*m
for i in range(m):
    l[i] = sm_e[i]-sm_o[i]

val = l[0]
tmp = 0

for i in range(m-1):
    ans = max(ans, sm_o[i] + tot_e - sm_e[i+1])
    if i != 0:
        if val < l[i]:
            val = l[i]
    ans = max(ans, sm_o[i] + tot_e - sm_e[i+1] + val)

for i in range(n):
    if i % 2 == 0:
        ans = max(ans, tot_e - a[i])

print(ans)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
inf=float("inf")
DP=[[-inf]*4 for _ in range(n+1)]
DP[0][2]=0
for i,a in enumerate(A):
  if (i+1)%2==0:
    DP[i+1][0]=DP[i][3]+a
    if i>=1:
      DP[i+1][0]=max(DP[i+1][0],DP[i-1][2]+a)
    DP[i+1][2]=DP[i][0]
    DP[i+1][3]=max(DP[i][1],DP[i][3])
    if i>=1:
      DP[i+1][3]=max(DP[i+1][3],DP[i-1][2])
  else:
    DP[i+1][0]=DP[i][2]+a
    DP[i+1][1]=DP[i][3]+a
    DP[i+1][3]=max(DP[i][0],DP[i][2])
if n%2==0:
  print(max(DP[n][0],DP[n][2]))
else:
  print(max(DP[n][1],DP[n][3]))

Submission status: Accepted

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

DP=[[-10**16 for i in range(N)]for j in range(3)]

DP[1][0]=0
DP[2][0]=0
DP[2][1]=0
DP[0][0]=A[0]
DP[1][1]=A[1]
if N>=3:
    DP[2][2]=A[2]

for i in range(2,N):
    DP[0][i]=DP[0][i-2]+A[i]
    DP[1][i]=DP[1][i-2]+A[i]
    DP[2][i]=DP[2][i-2]+A[i]
    if i-3>=0:
        DP[1][i]=max(DP[1][i],DP[0][i-3]+A[i])
        DP[2][i]=max(DP[2][i],DP[1][i-3]+A[i])
    if i-4>=0:
        DP[2][i]=max(DP[2][i],DP[0][i-4]+A[i])

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
k = 1+N%2 # 余分なxを入れる個数
INF = 10**18
# dp: i番目まで見たときに、j個の余分なxを入れた時の、和の最大値
dp = [[-INF for _ in range(4)] for _ in range(202020)]
dp[0][0] = 0
for i in range(N):
    for j in range(k+1):
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]) # xを一つ挿入する=>今見てる数字をスキップする
        now = dp[i][j]
        if (i+j)%2==0:
            now += A[i]
        dp[i+1][j] = max(dp[i+1][j], now)
print(dp[N][k])

Submission status: Accepted

Solution code:
from collections import defaultdict
INF = -1000000000000001

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

a = int(n/2)

dpa = defaultdict(lambda: -INF)
#dpa = [[0 for j in range(a+1)] for i in range(n+1)]

dpa[(0,0)] = 0
dpa[(1,0)] = 0
dpa[(1,1)] = l[0]
j = 1
for i in range(2,n+1):
	if i == j*2:
		dpa[(i,j)] = max(dpa[(i-2,j-1)]+l[i-1],dpa[(i-1,j)])
#		print(i,j,dpa[(i,j)])
	else:
		dpa[(i,j)] = max(dpa[(i-2,j-1)]+l[i-1],dpa[(i-1,j)])
#		print(i,j,dpa[(i,j)])
		if (i != n):
			j += 1
#			print(i,j,dpa[(i,j)])
#			print("   ",i-2,j-1,dpa[(i-2,j-1)],"")
			dpa[(i,j)] = dpa[(i-2,j-1)]+l[i-1]

#print(dpa)
print(dpa[n,a])

Submission status: Accepted

Solution code:
from math import inf


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

dp = [[-inf] * 3  for _ in range(n + 1)]
k = 1 + n % 2
dp[0][0] = 0
for i in range(n):
    for j in range(k + 1):
        if j < k:
            dp[i + 1][j + 1] = dp[i][j]
        now = dp[i][j]
        if (i + j) % 2 == 0:
            now += A[i]
        dp[i + 1][j] = max(dp[i + 1][j], now)
print(dp[n][k])

Submission status: Accepted

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

inf = 10 ** 18

dp = [[-inf] * 3  for _ in range(n + 1)]
k = 1 + n % 2
dp[0][0] = 0
for i in range(n):
    for j in range(k + 1):
        if j < k:
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
        now = dp[i][j]
        if (i + j) % 2 == 0:
            now += A[i]
        dp[i + 1][j] = max(dp[i + 1][j], now)
print(dp[n][k])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000000)
N = int(input())
import math
l = [int(x) for x in input().split()]
tobi = [0]*(math.ceil(N/2))
tobi[0] = l[0]
for i in range(1,math.ceil(N/2)):
    tobi[i] = tobi[i-1] + l[i*2]
from functools import lru_cache
@lru_cache(maxsize=1000000000)
def motomeru(x,y):
    if y == 0 or x == 0 or x == 1:
        return 0
    elif x % 2 == 0:
        return max(motomeru(x-2,y-1)+l[x-1],tobi[math.floor((x-1)/2)])
    else:
        return max(motomeru(x-2,y-1)+l[x-1],motomeru(x-1,y))
print(motomeru(N,N//2))

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
K = 1+N%2
dp = [[-10**18]*(K+1) for _ in range(N+1)]
dp[0][0] = 0

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

print(dp[N][K])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000000)
N = int(input())
import math
l = [int(x) for x in input().split()]
tobi = [0]*(math.ceil(N/2))
tobi[0] = l[0]
for i in range(1,math.ceil(N/2)):
    tobi[i] = tobi[i-1] + l[i*2]
from functools import lru_cache
@lru_cache(maxsize=1000000000)
def motomeru(x,y):
    if y == 0 or x == 0 or x == 1:
        return 0
    elif x % 2 == 0:
        return max(motomeru(x-2,y-1)+l[x-1],tobi[math.floor((x-1)/2)])
    else:
        return max(motomeru(x-2,y-1)+l[x-1],motomeru(x-1,y))
print(motomeru(N,N//2))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    m = N // 2
    dp = [defaultdict(lambda: -INF)] * 2
    dp[0][0] = 0
    for i, a in enumerate(A):
        ndp = [defaultdict(lambda: -INF)] * 2
        l = m - ((N-i) // 2)
        ndp[0] = dp[1]
        for k, v in dp[0].items():
            if k+1 >= l:
                ndp[1][k+1] = max(ndp[1][k+1], v+a)
            if k+2 >= l:
                ndp[0][k] = max(ndp[0][k], v)
        dp = ndp
    return max(dp[0][m], dp[1][m])


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N = ir()
    A = lr()
    dp = defaultdict(lambda: -float('inf'))
    dp[0, 0, 0] = 0
    for i in range(N):
        for j in range(max(i//2-1, 0), i//2+2):
            dp[i+1, j+1, 1] = dp[i, j, 0]+A[i]
            dp[i+1, j, 0] = max(dp[i, j, 0], dp[i, j, 1])
    # print(dp)
    print(max(dp[N, N//2, 1], dp[N, N//2, 0]))
resolve()

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
m=-10**15
#dp[i][j]=i番目までで、j回選ばない連続を使ったときの最大値
dp1=[[m,m,m] for i in range(n)] #最後を使うとき
dp0=[[m,m,m] for i in range(n)] #最後を使わないとき
dp1[0][0]=A[0]
dp0[0][1]=0 #最初選ばないときはj=1にする
for i in range(1,n):
    for j in range(3):
        dp1[i][j]=max(dp1[i][j],dp0[i-1][j]+A[i])
        dp0[i][j]=max(dp0[i][j],dp1[i-1][j])
        if j!=2:
            dp0[i][j+1]=max(dp0[i][j+1],dp0[i-1][j])
if n%2==0:
    print(max(dp1[n-1][1],dp0[n-1][0]))
else:
    print(max(dp1[n-1][2],dp0[n-1][1]))

Submission status: Accepted

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

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

print(max(dp))

Submission status: Accepted

Solution code:
INF = float("inf")
n = int(input())
a = list(map(int, input().split())) + ([0]*5)
s = 2 + n % 2 
dp = [[-INF] * s for _ in range(n+5)]
for i in range(s): dp[i][i] = a[i]

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

print(max([dp[n-i][s-i] for i in range(1, s+1)]))

Submission status: Accepted

Solution code:
N_all=int(input())
A=list(map(int,input().split()))
f_inf=-float("inf")
odds_or_even=N_all%2+2
dp=[[f_inf for x in range(N_all+1)] for x in range(odds_or_even)]
dp[0][0]=0

for i in range(N_all):
  dp[0][i+1]=dp[0][i]+A[i]*((i+1)%2)
for j in range(1,odds_or_even):
  for i in range(N_all):
    dp[j][i+1]=max(dp[j][i]+A[i]*((i+j+1)%2),dp[j-1][i])
        
print(dp[odds_or_even-1][N_all])

Submission status: Accepted

Solution code:
def examA():
    N = SI()
    ans = "No"
    for s in N:
        if s=="7":
            ans = "Yes"
    print(ans)
    return

def examB():
    N = I()
    ans = 0
    for i in range(1,N+1):
        if i%3==0:
            continue
        if i%5==0:
            continue
        ans += i
    print(ans)
    return

def examC():
    def gcd(x, y):
        if y == 0:
            return x
        while (y != 0):
            x, y = y, x % y
        return x
    K = I()
    ans = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            cur = gcd(i,j)
            for k in range(1,K+1):
                ans += gcd(cur,k)
    print(ans)
    return

def examD():
    N = I()
    S = SI()
    R = [0]*(N+1)
    G = [0]*(N+1)
    B = [0]*(N+1)
    for i in range(N):
        s = S[i]
        R[i+1] += R[i]
        G[i+1] += G[i]
        B[i+1] += B[i]
        if s=="R":
            R[i+1] += 1
        elif s=="G":
            G[i+1] += 1
        elif s=="B":
            B[i+1] += 1
    ans = 0
    for l in range(N):
        Ls = S[l]
        for r in range(l+3,N):
            Rs = S[r]
            if (Ls=="R" and Rs=="B") or (Ls=="B" and Rs=="R"):
                ans += G[r] - G[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="G":
                        ans -= 1
            elif (Ls=="R" and Rs=="G") or (Ls=="G" and Rs=="R"):
                ans += B[r] - B[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="B":
                        ans -= 1
            elif (Ls=="G" and Rs=="B") or (Ls=="B" and Rs=="G"):
                ans += R[r] - R[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="R":
                        ans -= 1
    print(ans)
    return

def examE():
    N, K = LI()

    ans = 0
    print(ans)
    return

def examF():
    N = I()
    A = LI()

    if N%2==0:
        O = [0] * N
        E = [0] * N
        for i in range(N):
            O[i] += O[i - 1]
            E[i] += E[i - 1]
            if i % 2 == 0:
                O[i] += A[i]
            else:
                E[i] += A[i]
        #print(O,E)
        ans = max(O[-1],E[-1])
        print(ans)
        return

    def dfs(n,k):
        if (n+2)//2 <k:
            return -inf
        if k == 0:
            return 0
        if n==0:
            if k==1:
                return A[0]
            return -inf
        if n==1:
            if k==1:
                return max(A[0],A[1])
            return -inf
        res = max(A[n]+dfs(n-2,k-1),dfs(n-1,k))
        return res

    ans = dfs(N-1,N//2)
    #print(dfs(4,2))
    print(ans)
    return

def examF2():
    N = I()
    A = LI()

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

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF2()

"""
27
18 18 19 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49
"""

Submission status: Accepted

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

is_odd = True

if n % 2 == 0:
    is_odd = False

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

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

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

Submission status: Accepted

Solution code:
# 写経AC
from collections import defaultdict

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

# dp[(i, x, flag)]:= i番目まででx個選んでいる時の最大値
# flag: i番目をとるフラグ
dp = defaultdict(lambda: -float("inf"))

# 初期条件
dp[(0, 0, 0)] = 0

# 貰うDP
for i, a in enumerate(A, 1):
    # i番目までで選ぶ個数
    for x in range((i // 2) - 1, (i + 1) // 2 + 1):
        dp[(i, x, 0)] = max(dp[(i - 1, x, 0)], dp[(i - 1, x, 1)])
        dp[(i, x, 1)] = dp[(i - 1, x - 1, 0)] + a

print(max(dp[(N, N // 2, 0)], dp[(N, N // 2, 1)]))

Submission status: Accepted

Solution code:
# 写経AC
from collections import defaultdict

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

# dp[(i, x, flag)]:= i番目まででx個選んでいる時の最大値
# flag: i番目をとるフラグ
dp = defaultdict(lambda: -float("inf"))

# 初期条件
dp[(0, 0, 0)] = 0

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

print(max(dp[(N, N // 2, 0)], dp[(N, N // 2, 1)]))

Submission status: Accepted

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

def main():
    pass
    N, *A = map(int, open(0).read().split())
    a = dict(enumerate(A, 1))
    dp = collections.defaultdict(lambda: -float("inf"))
    dp[0, 0] = 0 
    dp[1, 0] = 0 
    dp[1, 1] = a[1]
    for i in range(2, N + 1):
        jj = range(max(i // 2 - 1, 1), (i + 1) // 2 + 1)
        for j in jj:
            x = dp[i - 2, j - 1] + a[i]
            y = dp[i - 1, j]
            dp[i, j] = max(x, y)
    print(dp[N, N // 2])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

        dp[i, j] = max(x, y)
        debug([i - 2, j - 1])
        debug([i - 1, j])
        debug([i, j])
        debug(dp[i, j])
print(dp[N, N // 2])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

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

    if c == 0:
        return 0

    if idx <= 0 or idx < 2 * c - 1:
        return float('-inf')

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

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

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

def main():

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


main()

Submission status: Accepted

Solution code:
# coding: utf-8
#import numpy as np
inf = float('inf')

def main():
    # input
    N = int(input())
    A = [0] + list(map(int, input().split()))
#    N = 2*10**5-1
#    A = [0] + np.random.randint(-10**9, 10**9, 2*10**5-1).tolist()

    dp1 = [-inf] * (N+1)
    dp2 = [-inf] * (N+1)
    dp1[1] = 0
    dp2[1] = 0
    dp1[2] = A[1]
    dp2[2] = A[2]
    for i in range(3, N+1):
        if i%2 == 0:
            dp1[i] = dp1[i-2] + A[i-1]
            dp2[i] = max(dp2[i-2] + A[i], dp1[i-2] + A[i])
        else:
            dp1[i] = max(dp2[i-1], dp1[i-2]+A[i-1])
            dp2[i] = max(dp2[i-2] + A[i], dp1[i-2] + A[i])

    if N % 2 == 0:
        ans = max([dp1[N], dp2[N]])
    else:
        ans = max(dp1[-2:] + dp2[-2:])

    # print(DP0)
    # print(DP1)
    # print(DP2)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
#import copy
#import numpy as np
#import itertools
#import collections
#from collections import deque
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

inf = float('inf')
#inf = pow(10, 10)

def main():
    # input
    N = int(readline())
    A = list(map(int, readline().split()))

    K = N//2
    DP0 = [-inf] * N
    DP1 = [-inf] * N
    DP2 = [-inf] * N

    DP2[0] = A[0]
    DP2[1] = max(A[0], A[1])
    DP1[:2] = [0] * 2
    DP0[:4] = [0] * 4
    for i in range(2, N):
        if i%2 == 0:
            DP2[i] = DP2[i-2] + A[i]
            DP1[i] = max(DP2[i-1], DP1[i-2] + A[i])
            DP0[i] = max(DP1[i-1], DP0[i-2] + A[i])
        else:
            DP2[i] = max(DP2[i-2] + A[i], DP2[i-1])
            DP1[i] = max(DP1[i-1], DP1[i-2] + A[i])
            DP0[i] = max(DP0[i-1], DP0[i-2] + A[i])

    if N%2 == 0:
        ans = DP2[N-1]
    else:
        ans = DP1[N-1]

    #print(DP0)
    #print(DP1)
    #print(DP2)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

else:
	dp = [[-10**20 for _ in range(3)] for _ in range(n)]
	dp[0][0] = a[0]
	dp[0][1] = 0
	dp[1][1] = a[1]
	dp[0][2] = 0
	dp[1][2] = 0
	dp[2][2] = a[2]

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict

INF = float("inf")


N, *A = map(int, open(0).read().split())

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

for i, a in enumerate(A, 1):
    j = (i - 1) // 2
    for n in [j, j + 1]:
        I[(i, n)] = a + O[(i - 1, n - 1)]
        O[(i, n)] = max(O[(i - 1, n)], I[(i - 1, n)])

print(max(I[(N, N // 2)], O[(N, N // 2)]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

dp = defaultdict(lambda: -10**18)
dp[(0,0,False)] = 0

for i in range(n):
    for j in range(i//2-1,i//2+2):
        dp[(i+1,j,False)] = max(
            dp[(i,j,False)],
            dp[(i,j,True)]
        )
        dp[(i+1,j,True)] = dp[(i,j-1,False)] + al[i]

print(max(
    dp[(n,n//2,False)],
    dp[(n,n//2,True)]
))

Submission status: Accepted

Solution code:
N = int(input())
num = list(map(int, input().split()))
dp_odd = [0, num[0]]
dp_even = max(num[0], num[1])
for i in range(2, N):
  if (i + 1) % 2 == 1:
    dp_odd = [max(dp_odd[0] + num[i], dp_even), dp_odd[1] + num[i]]
  else:
    dp_even = max(dp_even + num[i], dp_odd[1])

if N % 2 == 0:
  print(dp_even)
else:
  print(dp_odd[0])

Submission status: Accepted

Solution code:
import sys, math
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = [0] + list(map(int, input().split()))
    """
    dp[i][j] = (1からi番目の数のうちどの２個も連続しないようにj個選んだ時の和の最大)
    と置くらしい。何故その発想になるんだ？？
    最初は左右で分けて尺取りみたいなことをすれば行けると思ったが、左右の分け目を１つずらしたら
    最適解がガラッと変わって困った　→　じゃあDP、って感じなのかなあ

    このままだとO(N^2)なので状態数を減らす。
    １．j個は連続しないようにとるので、j <= (1 + i) // 2は確定。(iは1-indexedなことに注意)
    ２．残った(N - i)から連続しないように(N // 2 - j)個選ぶには、(N // 2 - j) <= (1 + N - i) // 2、
    　　すなわち(i - 3) // 2 <= jが必要。
    　　（j = 0,1,とか考えてもいいが、最終的にdp[N][N // 2]を求めるのにこれらは寄与しない）
    以上より、(i - 3) // 2 <= j <= (i + 1) // 2の範囲のみでdpすれば十分。

    肝心の遷移だが、A = [3, 1, 4, 1, 5, 9, 2]を例にとると
            i\j|  0  1  2   3   4       dp[5][1] = max(A[5], dp[4][1])
            ----------------------      dp[5][2] = max(A[5] + dp[3][1], dp[4][2])
              1|  0  3                  dp[5][3] = A[5] + dp[3][2]
              2|  0  3
              3|  0  4  7               dp[6][2] = max(A[6] + dp[4][1], dp[5][2])
              4|     4  7               dp[6][3] = max(A[6] + dp[4][2], dp[5][3])
              5|     5  9  12
              6|        9  12           のように、最後の数をとるか取らないかで場合分けすればよい。
              7|        9  12  14       ただしiが奇数の場合、dp[i][(i + 1) // 2]は必ずA[i]を
                                        加えざるを得ないため場合分けは起きないことに注意。
    """

    # iの偶奇でdp[i]をeven, oddに分割してメモリ削減
    odd = [0, A[1], 0]
    even = [0, max(A[1], A[2])]
    for i in range(3, N + 1):
        if i % 2 == 0:
            even[0] = max(A[i] + even[0], odd[1])
            even[1] = max(A[i] + even[1], odd[2])
        elif i > 3:
            odd[0] = max(A[i] + odd[0], even[0])
            odd[1] = max(A[i] + odd[1], even[1])
            odd[2] = A[i] + odd[2]
        else:
            odd[1] = max(A[1:4])
            odd[2] = A[1] + A[3]
    if N % 2 == 0:
        print(even[1])
    else:
        print(odd[1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3

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

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

ms[0][0] = 0
ms[0][1] = 0
ms[0][2] = a[0]

ms[1][0] = 0
ms[1][1] = max(a[0], a[1])

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


print(ms[n - 1][1])

Submission status: Accepted

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

DP_odd = [0, A[0]]
DP_even = [0, max(A[0], A[1])]

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

if N % 2 == 1:
    ans = DP_odd[0]
else:
    ans = DP_even[1]

print(ans)

Submission status: Accepted

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

DP_odd = [0, 0, A[0]]
DP_even = [0, max(A[0], A[1])]

if N >= 3:
    DP_odd = [DP_even[0], max(DP_odd[1] + A[2], DP_even[1]), DP_odd[2] + A[2]]

for i in range(3, N):
    if (i + 1) % 2 == 1:    
        DP_odd = [max(DP_odd[0] + A[i], DP_even[0]), max(DP_odd[1] + A[i], DP_even[1]), DP_odd[2] + A[i]]
    else:
        DP_even = [max(DP_even[0] + A[i], DP_odd[1]), max(DP_even[1] + A[i], DP_odd[2])]

if N % 2 == 1:
    ans = DP_odd[1]
else:
    ans = DP_even[1]

print(ans)

Submission status: Accepted

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


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


def S(): return input()


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


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


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


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


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


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


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


def make4(initial, L, M, N, O):
    return [[[[initial for i in range(O)]
                for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def make3(initial, L, M, N):
    return [[[initial for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


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

show_flg = False
# show_flg = True


def main():
    N = I()
    A = LI()
    dp_use = [-IINF] * 3
    dp_not_use = [-IINF] * 3
    dp_not_use[0] = 0

    for i in range(N):
        dp_use_next = [-IINF] * 3
        dp_not_use_next = [-IINF] * 3

        for j in range(3):
            if j - 1 >= 0:
                dp_not_use_next[j] = max(dp_use[j], dp_not_use[j-1])
            else:
                dp_not_use_next[j] = dp_use[j]
            dp_use_next[j] = dp_not_use[j] + A[i]

        # print('dp_use    ', *[a if a > -10**10 else '-IINF' for a in dp_use_next])
        # print('dp_not_use', *[a if a > -10**10 else '-IINF' for a in dp_not_use_next])
        dp_use = dp_use_next
        dp_not_use = dp_not_use_next

    if N % 2 == 0:
        print(max(dp_use[1], dp_not_use[0]))
    else:
        print(max(dp_use[2], dp_not_use[1]))


if __name__ == '__main__':
    main()