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()]

# dp(直前の値を取っている)(最大個数取っている)
dp00 = -10**9
dp01 = 0
dp10 = -10**9
dp11 = 0

for i in range(n):
    if i % 2 == 0:
        dp10 = dp00 + a[i]
        dp00 = max(dp01, dp11)
        dp11 = dp01 + a[i]
    else:
        dp01 = dp11
        dp11 = dp00 + a[i]
        dp00 = max(dp00, dp10)
        if i == 3:
            dp10 = a[i]

if n % 2 == 0:
    print(max(dp01, dp11))
else:
    print(max(dp00, dp10))

Submission status: Accepted

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

# dp(直前の値を取っている)(最大個数取っている)
dp00 = 0
dp01 = -10**15
dp10 = -10**15
dp11 = a[0]

for i in range(1, n):
    if i % 2 != 0:
        dp01 = dp11
        dp11 = dp00 + a[i]
        dp00 = max(dp00, dp10)
        if i == 3:
            dp10 = a[i]
    else:
        dp10 = dp00 + a[i]
        dp00 = max(dp01, dp11)
        dp11 = dp01 + a[i]

if n % 2 == 0:
    print(max(dp01, dp11))
else:
    print(max(dp00, dp10))

Submission status: Accepted

Solution code:
n=int(input())
arr=list(map(int,input().split()))
acum1=[0]
acum2=[0]
for i in range(n):
  if i%2==0:
    acum1.append(acum1[-1]+arr[i])
    acum2.append(acum2[-1]+0)
  else:
    acum1.append(acum1[-1]+0)
    acum2.append(acum2[-1]+arr[i])
if n%2==0:
  ans=max(acum1[n-1]-acum1[0],acum2[n]-acum2[1])
  for i in range(1,n+1,2):
    if i+3>n:
      continue
    tmp=(acum1[i]-acum1[0])+(acum2[n]-acum2[i+2])
    ans=max(ans,tmp)
else:
  ans=max(acum1[n-2]-acum1[0],acum2[n-1]-acum2[1],acum1[n]-acum1[2])
  for i in range(1,n+1,2):
    if i+3>n-1:
      continue
    tmp=(acum1[i]-acum1[0])+(acum2[n-1]-acum2[i+2])
    ans=max(ans,tmp)
  for i in range(2,n+1,2):
    if i+3>n:
      continue
    tmp=(acum2[i]-acum2[1])+(acum1[n]-acum1[i+2])
    ans=max(ans,tmp)
  for i in range(1,n+1,2):
    if i+4>n:
      continue
    tmp=(acum1[i]-acum1[0])+(acum1[n]-acum1[i+3])
    ans=max(ans,tmp)
  acummax=[-10**18]
  for i in range(1,n+1):
    if i+2>n:
      acummax.append(-10**18)
    else:
      if i%2==0:
        acummax.append(acum2[i]+acum1[n]-acum1[i+2])
      else:
        acummax.append(-10**18)
  for i in range(n-1,-1,-1):
    acummax[i]=max(acummax[i],acummax[i+1])
  for i in range(1,n+1,2):
    if i+6>n:
      continue
    tmp=(acum1[i]-acum1[0]-acum2[i+2])+acummax[i+3]
    ans=max(ans,tmp)
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()

DP = [[- 10 ** 10] * 3 for _ in range(N)]

DP[0][0] = A[0]
DP[1][0] = A[1]
DP[2][0] = A[0] + A[2]
DP[2][1] = A[2]

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys

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

if N == 2:
    print(max(A))
    sys.exit()

dp = [0,max(A[:3]),A[0]+A[2]]
tmp1 = dp[:]
tmp2 = [0,max(A[:2]),0]
flag1 = False
flag2 = True if A[0] < A[2] and A[1] < A[2] else False
flag3 = False

for i in range(3,N):
    b = A[i]
    if i%2 == 0:
        dp[0] = max(tmp2[0],tmp1[0]+b)
        flag1 = True if tmp2[0] < tmp1[0]+b else False
        if flag3:
            dp[1] = max(tmp2[1],tmp1[1]+b)
            flag2 = True if tmp2[1] < tmp1[1]+b else False 
        else:
            dp[1] = max(tmp2[1],tmp2[0]+b,tmp1[1]+b)
            flag2 = True if tmp2[1] < tmp2[0]+b or tmp2[1] < tmp1[1]+b else False 
        dp[2] += A[i]
        tmp1 = dp[:]
    else:
        if flag1:
            dp[0] = max(tmp1[1],tmp2[0]+b)
            flag3 = True if tmp1[1] < tmp2[0]+b else False
        else:
            dp[0] = max(tmp1[1],tmp1[0]+b,tmp2[0]+b)
            flag3 = True if tmp1[1] < tmp1[0]+b or tmp1[1] < tmp2[0]+b else False
        if flag2:
            dp[1] = max(tmp1[2],tmp2[1]+b)
        else:
            dp[1] = max(tmp1[2],tmp1[1]+b,tmp2[1]+b)
        tmp2 = dp[:]
        
print (dp[1])

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
dp=[defaultdict(lambda:-float('inf'))for _ in range(n)]
for i in range(n):dp[i][0]=0
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i][j]=max(dp[i-2][j],dp[i-2][j-1]+a,dp[i-1][j])
print(dp[-1][n//2])

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
dp=[defaultdict(lambda:-float('inf'))for _ in range(n)]
for i in range(n):dp[i][0]=0
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i][j]=max(dp[i-2][j],dp[i-2][j-1]+a,dp[i-1][j])
print(dp[-1][n//2])

Submission status: Accepted

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

dp = [[0]*3]*N

dp[0][0] = 0  # ((i+1)-1)/2
dp[0][1] = 0 # (i+1)/2
dp[0][2] = A[0]  # ((i+1)+1)/2

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

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

Submission status: Accepted

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

if n==2:
    print(max(a[0],a[1]))
    exit()
    
dp=[[-float('inf'),-float('inf'),-float('inf')] for i in range(n)]
# dp[i][0]:iまででまだ飛ばしてない
# dp[i][1]:一つ飛ばしてる
# dp[i][2]:２つ飛ばしてる
dp[0][0]=a[0]
dp[1][1]=a[1]
dp[2][2]=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-2][1]+a[i],dp[i-3][0]+a[i])
    if i>=4:
        dp[i][2]=max(dp[i-2][2]+a[i],dp[i-3][1]+a[i],dp[i-4][0]+a[i])

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:
def find_max(a):
    n = len(a)

    if n <= 3:
        return max(a)

    dp = [[-(1 << 64)] * (2 + n % 2) for _ in range(n)]

    for i in range(2 + n % 2):
        dp[i][i] = a[i]
        dp[i + 1][i] = a[i]

    for i in range(2, n):
        for j in range(2 + n % 2):
            for extra_space in range(j + 1):
                curr_sum = dp[i - (2 + extra_space)][j - extra_space] + a[i]
                if curr_sum > dp[i][j]:
                    dp[i][j] = curr_sum

    return dp[-1][1 + n % 2]


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

    print(find_max(a))


main()

Submission status: Accepted

Solution code:
import pprint
N=int(input())
A=list(map(int,input().split()))
if N%2==0:#偶数なら1回まで2こ飛ばしで無茶できる
    dp=[[-float("inf") for _ in range(2)] for _ in range(N+10)]#dpはj=0の時は無茶をしていない系列j=1の時は1回無茶をした系列である
    if N==2:#2の時は個別
        print(max(A[0],A[1]))
    else:#それ以外の時は
        for i in range(N):
            if i==0:            #i=0をとる時の任意の系列は無茶を確実にしていないのでdp[i][0]のみA[0]
                dp[0][0]=A[0]
            elif i==1:          #i=1をとる時の任意の系列は一回無茶をして取っているはずである、よってdp[i][1]のみA[1]
                dp[1][1]=A[1]
            elif i==2:          #i=2をとる時の任意の系列は一回も無茶せずに先頭からとっているのでdp[i][0]=A[0]+A[2]
                dp[2][0]=A[0]+A[2]
            else:                   #そのほかは再帰的に考える
                for j in range(2):
                    if j==0:                                                    #無茶しない系列を生成する時
                        dp[i][0]=max(dp[i][0],dp[i-2][0]+A[i])                  #そこまでの無茶しなかった系列に自らを足していけば良い
                    elif j==1:                                                  #一回無茶する系列を生成する時
                        dp[i][1]=max(dp[i][1],dp[i-2][1]+A[i],dp[i-3][0]+A[i])  #すでにある無茶した時の値(いらない？)と、前までの系列で無茶していて今回は無茶できないパターン、今回で無茶をするパターンのうち最大を用いて系列生成すれば良い
        print(max(dp[N-1][1],dp[N-2][0]))                                       #1回も飛ばさない時は後ろから二番目のdp値が相当することに注意
else:#奇数なら計2回まで無茶できる(2飛ばし×2、3飛ばし×1まで許容)
    #print(A[0],A[1])
    dp=[[-float("inf") for _ in range(3)] for _ in range(N+10)]#dpはj=0の時は無茶をしない系列j=1は1回無茶をした系列、j=2は2回無茶をしている系列
    if N==3:#N=3の時は個別
        print(max(A[0],A[1],A[2]))
    else:#それ以外の時は
        for i in range(N):
            if i<4:
                if i==0:                                        #i=0をとる任意の系列は無茶を確実にしていないのでdp[i][0]のみA[0]
                    dp[0][0]=A[0]
                if i==1:                                        #i=1をとる任意の系列は確実に1回無茶をしているのでdp[i][1]のみA[1]
                    dp[1][1]=A[1]
                if i==2:                                        #i=2をとる時は2回分の無茶をしてA[2]を得る時(dp[i][2]=A[2])および1かいも無茶せずに撮っている時(dp[i][0]=A[2]+A[0])
                    dp[2][2]=A[2]
                    dp[2][0]=A[0]+A[2]
                if i==3:                                        #i=3をとる時は1回目で無茶をしてそのあと無茶していないパターン(dp[1][1]+A[3])といきなり1回無茶をしたパターン(dp[0][0]+A[3])があるのでその最大を
                    dp[3][1]=max(dp[1][1]+A[3],dp[0][0]+A[3])
            else:                                                                               #そのほかは再帰的に
                for j in range(3):
                    if j==0:                                                                    #無茶してない系列を生成する時、
                        dp[i][0]=max(dp[i][0],dp[i-2][0]+A[i])                                  #そこまでの無茶しなかった系列に自らを足していけば良い
                    elif j==1:                                                                  #1回だけ無茶した系列を生成する時
                        dp[i][1]=max(dp[i][1],dp[i-2][1]+A[i],dp[i-3][0]+A[i])                  #すでにある1回無茶した時の値(いらない？)と、前までの系列で1回無茶していて今回は無茶しないパターン、今回で初めて無茶をするパターンのうち最大を用いて系列生成すれば良い
                    else:                                                                       #2回無茶した系列を生成する時
                        dp[i][2]=max(dp[i][2],dp[i-2][2]+A[i],dp[i-3][1]+A[i],dp[i-4][0]+A[i])  #すでにある2回無茶した時の値(いらない？)と、もう二回無茶していて無茶できないパターン、前までの系列で1回無茶していて今回も1回無茶するしないパターン、今回でいきなり2回無茶をするパターンのうち最大を用いて系列生成すれば良い
        print(max(dp[N-1][2],dp[N-2][1],dp[N-3][0]))                                            #1回も飛ばさない時は後ろから3番目が、1回だけ飛ばした時は後ろから2番目のdp値が相当することに注意

Submission status: Accepted

Solution code:
def f_select_half():
    # 参考: https://at274.hatenablog.com/entry/2020/04/14/002124
    from collections import defaultdict
    N = int(input())
    A = [int(i) for i in input().split()]

    # dp[(i, j, flag)]: A の i 番目の要素まで見たとき、j 個の要素を選んでいるときの和の最大値
    # flag == 1 のときは、i 番目の要素を採用したものとする
    # 初めて指した遷移前が影響してほしくないので、この値で初期化
    dp = defaultdict(lambda: -float('inf'))
    dp[(0, 0, 0)] = 0

    for k, a in enumerate(A, 1):
        j = k // 2
        for x in range(j - 1, j + 2):
            dp[(k, x, 0)] = max(dp[(k - 1, x, 0)], dp[k - 1, x, 1])
            # k-1 番目の要素を選んでいないときだけ、k 番目の要素を選べる
            dp[(k, x, 1)] = dp[(k - 1, x - 1, 0)] + a
    return max(dp[(N, N // 2, f)] for f in (0, 1))

print(f_select_half())

Submission status: Accepted

Solution code:
def get_next_unchosen(current , chooseNum):
    if (chooseNum , 0) in current or (chooseNum , 1) in current:
        if (chooseNum , 0) in current and (chooseNum ,1) in current:
            return max(current[(chooseNum, 0)] , current[(chooseNum, 1)])
        if (chooseNum , 0) in current:
            return current[(chooseNum , 0)]
        return current[(chooseNum,1)]
    return None


def calc_next_state(current, must_choose_num, a):
    next = {}
    current_unchosen_nums = [choose_num  for (choose_num, prev_chosen) in current.keys() if prev_chosen == 0 and choose_num >= must_choose_num - 1]
    for chooseNum in current_unchosen_nums:
        next[(chooseNum + 1, 1)] = current[(chooseNum , 0)] + a
    for chooseNum in range(must_choose_num, N):
        n = get_next_unchosen(current, chooseNum)
        if n is None:
            break
        else:
            next[(chooseNum , 0)] = n
    return next


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

totalChooseNum = N // 2
dp = {(0, 0) : 0}
for i in range(0, N):
    ai = A[i]
    canChooseNum = (N - i + 1) // 2
    mustChooseNum = max(totalChooseNum - canChooseNum, 0)
    dp = calc_next_state(dp, mustChooseNum, ai)

result = max(dp[(totalChooseNum, 0)] , dp[(totalChooseNum , 1)])
print(result)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
if n % 2 == 0 and n >= 4:
  dp = [[0, 0] for i 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):
    dp[i][0] = dp[i - 2][0] + a[i]
    dp[i][1] = max(dp[i - 3][0], dp[i - 2][1]) + a[i]
  print(max(dp[n - 2][0], dp[n - 1][1]))
elif n % 2 != 0 and n >= 5:
  dp = [[0, 0, 0] for i 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] = a[1] + a[3]
  dp[3][2] = a[0] + a[3]
  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]
    dp[i][2] = max(dp[i - 4][0], dp[i - 3][1], dp[i - 2][2]) + a[i]
  print(max(dp[n - 3][0], dp[n - 2][1], dp[n - 1][2]))
elif n == 2:
  print(max(a[0], a[1]))
else:
  print(max(a[0], a[1], a[2]))

Submission status: Accepted

Solution code:
C = -(10**15 + 7)


def main():
    from collections import defaultdict
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    dp = defaultdict(lambda: C)
    for i in range(N+1):
        dp[i, 0] = 0
        if i != 0:
            dp[(i, 1)] = max(dp[i-1, 1], A[i-1])
    for i in range(2, N+1):
        for j in range(i//2-1, (i+1)//2 + 1):
            if j < 0:
                continue
            # A_i(1-index)でj個選ばなければいけない
            dp[i, j] = max(dp[i, j], dp[i-2, j-1] + A[i-1],
                           dp[i-3, j-1] + A[i-1], dp[i-4, j-1] + A[i-1])
    print(max(dp[N, K], dp[N-1, K], dp[N-2, K]))
    # for i in range(N+1):
    #     for j in range(K+1):
    #         print("{:>4}".format(dp[i, j] if dp[i, j] != C else "C"),
    #               end=" " if j != K else "\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# aを偶数奇数の要素で振り分け
a1=[]
a2=[]

for i in range(n):
    if i%2==0:
        a1.append(a[i])
    else:
        a2.append(a[i])

# 累積和も作っておく
a3=list(itertools.accumulate(a1))
a4=list(itertools.accumulate(a2))


x1=sum(a1)
x2=sum(a2)


if n%2==0:
    ans=-float('inf')
    for i in range(n//2):
        ans=max(a3[i]+x2-a4[i],ans)
    print(max(ans,x1,x2))
else:
    # 奇数番目だけの要素を選んだ時の最大値
    ans1=sum(a1)-min(a1)
    # dp1[i]=奇数偶数奇数or偶数奇数と移動した時のi番目までのMAX
    dp1 = [-float('inf')] * (n // 2 + 1)
    dp1[0] = a1[0]
    # dp2[i]=奇数偶数or偶数のみと移動した時のi番目までのMAX
    dp2 = [-float('inf')] * (n // 2)
    dp2[0] = a2[0]
    for i in range(n // 2 - 1):
        dp2[i + 1] = max(a3[i] + a2[i + 1], dp2[i] + a2[i + 1])
        if i==0:
            dp1[i + 2] = dp2[i] + a1[i + 2]
        else:
            dp1[i + 2] = max(dp2[i] + a1[i + 2], dp1[i + 1] + a1[i + 2])
    print(max(dp1[-1], dp2[-1],ans1))

Submission status: Accepted

Solution code:
#f dp
n = int(input())
a = list(map(int, input().split()))
DIM, PER = 0, 1
MIN, MAJ = 0, 1
# pick from 0~i
# j = DIM or PER if i is odd, MIN or MAJ otherwise
dp = [[None, None] for _ in range(n)]
dp[0] = [0, a[0]]
dp[1] = [0, max(a[0], a[1])]
for i in range(2, n):
    if i % 2 == 0:
        dp[i][MIN] = max(dp[i - 2][MIN] + a[i], dp[i - 1][PER])
        dp[i][MAJ] = dp[i - 2][MAJ] + a[i]
    else:
        dp[i][DIM] = max(dp[i - 2][DIM] + a[i], dp[i - 1][MIN])
        dp[i][PER] = max(dp[i - 2][PER] + a[i], dp[i - 1][MAJ])
if n % 2 == 0:
    print(dp[n - 1][PER])
else:
    print(dp[n - 1][MIN])

Submission status: Accepted

Solution code:

#f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)

select_num = N//2
inf = -10e+100

Dp_f = [[inf] * (3) for _ in range(N+1)]
Dp_s = [[inf] * (3) for _ in range(N+1)]
# 3　次元はそれぞれStart~3つに該当

pre_margin = 0
for i in range(1,N+1):
    Start = (i-1)//2
    End = (i+1)//2
    
    cur_margin = Start
    
    for j in range(Start,End+1):
        Dp_f[i][j-cur_margin] = max(Dp_s[i-1][j-pre_margin], Dp_f[i-1][j-pre_margin])   
        # [0] in 3rd dimension  not chosen at last num
        # must be transfered from [i-1]
    for j in range(Start,End+1):
        if j-1 == 0:
            Dp_s[i][j-cur_margin] = 0 + A[i]
        else:
            Dp_s[i][j-cur_margin] = Dp_f[i-1][j-1-pre_margin]+A[i]
    
    pre_margin = cur_margin
print(max(Dp_f[-1][select_num - cur_margin], Dp_s[-1][select_num - cur_margin]))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
if N==2:
  print(max(A))
  exit() 
  
dp=[[0,0,0] 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>1:
    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]
  if i>3 :
    dp[i][2]=max(dp[i-4][0],dp[i-3][1],dp[i-2][2])+A[i]
if N%2==1:
  ans=max(dp[-1][2],dp[-2][1],dp[-3][0])
else:
  ans=max(dp[-1][1],dp[-2][0])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
if n <= 3:
  print(max(a))
  exit()

a = tuple(a)
dp = [[-10**15]*3 for i in range(n)]

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

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] * 5
    dp_not_use = [-IINF] * 5
    dp_not_use[0] = 0

    for k in range(N):
        dp_use_next = [-IINF] * 5
        dp_not_use_next = [-IINF] * 5
        for current_dif in range(-3,2):
            if current_dif-1 >= -3:
                dp_use_next[current_dif] = dp_not_use[current_dif - 1] + A[k]
            if current_dif+1 < 2:
                dp_not_use_next[current_dif] = max(dp_use[current_dif+1], dp_not_use[current_dif+1])
        dp_use = dp_use_next
        dp_not_use = dp_not_use_next

    dif = N//2 - (N-N//2)
    print(max(dp_use[dif], dp_not_use[dif]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
INF = 10**18
dp_use = [-INF] * 5
dp_not_use = [-INF] * 5
dp_not_use[0] = 0
 
for a in A:
    tmp_use = [-INF] * 5
    tmp_not_use = [-INF] * 5
    for current_dif in range(-3,2):
        if current_dif-1 >= -3:
            tmp_use[current_dif] = dp_not_use[current_dif - 1] + a
        if current_dif+1 < 2:
            tmp_not_use[current_dif] = max(dp_use[current_dif+1], dp_not_use[current_dif+1])
    dp_use = tmp_use
    dp_not_use = tmp_not_use
dif = n//2 - (n-n//2)
print(max(dp_use[dif], dp_not_use[dif]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
if n == 3:
    print(max(a))
    quit()
dp1 = [-inf]*(n+1) 
dp2 = [-inf]*(n+1)
dp3 = [-inf]*(n+1)
dp1[0] = 0
dp2[0] = 0
dp3[0] = 0
dp1[1] = a[0]
dp2[2] = a[1]
for i in range(3,n+1):
    dp1[i] = dp1[i-2] + a[i-1]
    dp2[i] = max(dp2[i-2],dp1[i-3]) + a[i-1]
    dp3[i] = max(dp3[i-2],dp2[i-3],dp1[i-4]) + a[i-1]
if n % 2:
    print(max(dp1[n-2], dp2[n], dp3[n]))
else:
    print(max(dp1[n-1], dp2[n]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
if n == 3:
    print(max(a))
    quit()
dp1 = [-inf]*(n+1) 
dp2 = [-inf]*(n+1)
dp3 = [-inf]*(n+1)
dp1[0] = 0
dp2[0] = 0
dp3[0] = 0
dp1[1] = a[0]
dp2[2] = a[1]
for i in range(3,n+1):
    dp1[i] = dp1[i-2] + a[i-1]
    dp2[i] = max(dp2[i-2],dp1[i-3]) + a[i-1]
    dp3[i] = max(dp3[i-2],dp2[i-3],dp1[i-4]) + a[i-1]
if n % 2:
    print(max(dp1[n-2], dp2[n], dp3[n]))
else:
    print(max(dp1[n-1],dp2[n]))

Submission status: Accepted

Solution code:
from collections import*
n,*a=map(int,open(0).read().split())
dp=[defaultdict(lambda:-10**18)for _ in range(n)]
for i in range(n):dp[i][0]=0
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i][j]=max(dp[i-2][j],dp[i-2][j-1]+a,dp[i-1][j])
print(dp[-1][n//2])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = list(map(int,input().split()))

dp = np.zeros((n+1,2), int)
dp[1],dp[2] = [0,a[0]], [0,max(a[0], a[1])]
for i in range(3,n+1):
  if(i%2 == 0):
    dp[i][0] = max(dp[i-1][0],dp[i-2][0]+a[i-1],dp[i-2][1])
    dp[i][1] = max(dp[i-1][1],dp[i-2][1]+a[i-1])
  else:
    dp[i][0] = max(dp[i-1][1],dp[i-2][1],dp[i-2][0]+a[i-1])
    dp[i][1] = dp[i-2][1]+a[i-1]
print(dp[n][(n+1)%2])

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
n = onem()
a = l()


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

    ans = sum(a[0::2])
    ans = max(ans,sum(a[1::2]))
    co = 0
    for i in range(0,n,2):
        if i+1 <= n-1:
            ans = max(ans,co+po[i+1])
        else:
            ans = max(ans,co)
        co += a[i]

    print(ans)

else:
    po = [a[i] for i in range(n)]
    mi = [-Max for i in range(n)]
    
    for i in range(n-3,-1,-1):
        po[i] += po[i+2]

    ans = sum(a[1::2])
    ans = max(ans,sum(a[0::2]) - a[-1])
    l1 = [-Max for i in range(n)]
    for i in range(n):
        if i != n-1:
            l1[i] = po[i+1]


    for i in range(n-1,-1,-1):
        if i == n-1:
            continue
        elif i == n-2:
            mi[i] = l1[i]
        else:
            mi[i] = max(mi[i+2]+a[i],l1[i])


    l1 = mi

        
    co = 0

    for i in range(0,n,2):
        if i + 2 <= n-1:
            ans = max(ans,co+l1[i+1],co+po[i+2])
        elif i+1 <= n-1:
            ans = max(ans,co+l1[i+1])
        else:
            ans = max(ans,co)
        
        co += a[i]
    co = 0
    for i in range(1,n,2):
        ans = max(ans,co+po[i+1])
        co += a[i]
    print(ans)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
n = onem()
a = l()


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

    ans = sum(a[0::2])
    ans = max(ans,sum(a[1::2]))
    co = 0
    for i in range(0,n,2):
        if i+1 <= n-1:
            ans = max(ans,co+po[i+1])
        else:
            ans = max(ans,co)
        co += a[i]

    print(ans)

else:
    po = [a[i] for i in range(n)]
    mi = [-Max for i in range(n)]
    
    for i in range(n-3,-1,-1):
        po[i] += po[i+2]

    ans = sum(a[1::2])
    ans = max(ans,sum(a[0::2]) - a[-1])
    #print(ans)
    l1 = [-Max for i in range(n)]
    for i in range(n):
        if i != n-1:
            l1[i] = po[i+1]

    """
    co = 0
    for i in range(0,n,2):
        if i != n-1:
            l1[i] = co + po[i+1]
        else:
            l1[i] = co
        co += a[i]
    co = 0
    for i in range(1,n,2):
        if i != n-1:
            l1[i] = co + po[i+1]
        else:
            l1[i] = co
        co += a[i]
    """

    for i in range(n-1,-1,-1):
        if i == n-1:
            continue
        elif i == n-2:
            mi[i] = l1[i]
        else:
            mi[i] = max(mi[i+2]+a[i],l1[i])


    l1 = mi


    """
    for i in range(n-1,-1,-1):
        if i <= n-3:
            mi[i] = min(mi[i+2],a[i])
        else:
            mi[i] = a[i]
    print(mi)
    """
    
    l2 = [-Max for i in range(n)]
    
    for i in range(n-1,-1,-1):
        l2[i] = po[i]
        
    #print(l1)
    #print(l2)
    co = 0

    for i in range(0,n,2):
        if i + 2 <= n-1:
            #print(ans,co+l1[i+1],co+l2[i+2])
            ans = max(ans,co+l1[i+1],co+l2[i+2])
        elif i+1 <= n-1:
            ans = max(ans,co+l1[i+1])
        else:
            ans = max(ans,co)
        
        co += a[i]
    co = 0
    #print(ans)
    for i in range(1,n,2):
        #print(ans,co+l1[i+1])
        ans = max(ans,co+po[i+1])
        #ans = max(ans,co+l1[i+1])
        co += a[i]
    #print("po:"+str(mi[1]))
    print(ans)