Problem:


Score : 600 points

Problem Statement

Given is an integer sequence A_1, ..., A_N of length N.

We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.

Find the maximum possible sum of the chosen elements.

Here \lfloor x \rfloor denotes the greatest integer not greater than x.

Constraints

2 \leq N \leq 2\times 10^5

|A_i|\leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the maximum possible sum of the chosen elements.

Sample Input 1

6
1 2 3 4 5 6

Sample Output 1

12

Choosing 2, 4, and 6 makes the sum 12, which is the maximum possible value.

Sample Input 2

5
-1000 -100 -10 0 10

Sample Output 2

0

Choosing -10 and 10 makes the sum 0, which is the maximum possible value.

Sample Input 3

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5000000000

Watch out for overflow.

Sample Input 4

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

Sample Output 4

295



Sample input:
6
1 2 3 4 5 6


Sample output:
12

Submission status: Accepted

Solution code:
import sys

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

# dp = [[0 for i in range((n//2)+1)] for j in range(n)]

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(len(dp)):
#     print(dp[i])

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

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

# for i in range(len(dp)):
#     print(dp[i])

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

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:
n=int(input())
arr=list(map(int,input().split()))
if n<=3:
  print(max(arr))
  exit()
lim=n%2+2
dp=[[0]*lim for _ in range(n+1)]
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])
  if lim==3:
    dp[i+1][2]=max(dp[i-1][2]+arr[i],dp[i-2][1]+arr[i],dp[i-3][0]+arr[i])
print(max(dp[-1][:lim]))

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][1] = max(dp[i][1]+a[i+2],dp[i-1][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()


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
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 = [0] * N
    dp[1] = max(a[0], a[1])
    c = a[0]

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

    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

le, lo, re, ro = [0], [0], [0], [0]

for i in range(n):
    if i % 2 == 0:
        le.append(le[-1] + a[i])
    else:
        lo.append(lo[-1] + a[i])

for i in range(n-1, -1, -1):
    if i % 2 == 0:
        re.append(re[-1] + a[i])
    else:
        ro.append(ro[-1] + a[i])

le_o = [0]
for i in range(len(lo)-1):
    le_o.append(max(0, le_o[-1] + a[2*i+1] - a[2*i]))


if n % 2 == 0:
    n //= 2
    ans = lo[n]
    for i in range(0, n + 1):
        ans = max(ans, le[i] + ro[n-i])

    print(ans)

else:
    n //= 2
    ans = le[n]
    for i in range(0, n+1):
        ans = max(ans, le[i] + ro[n-i])
        ans = max(ans, lo[i] + re[n-i])
        ans = max(ans, le[i] + re[n-i] + le_o[i])

    print(ans)

Submission status: Accepted

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

dp = [0] * (n+1)
dp[2] = max(A[0], A[1])
s = A[0]

for i, a in enumerate(A, 1):
    if i <= 2:
        continue
    if i%2:  # 奇数
        dp[i] = max(dp[i-1], a+dp[i-2])
        s += a
    else:  # 偶数
        dp[i] = max(a+dp[i-2], s)


print(dp[-1])

Submission status: Accepted

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

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

if i % 2 == 0:
    print(B[N-1][0])
else:
    print(B[N-1][1])

Submission status: Accepted

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

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

print(dp[-1])

Submission status: Accepted

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


def solve(N: int, A: "List[int]"):
    dp = [[0,0] for _ in range(N+1)]
    dp[2] = [A[0],A[1]]
    
    for i in range(2,N):
        if (i+1)%2 ==0:
            dp[i+1][0] = dp[i-1][0]+A[i-1]
        else:
            dp[i+1][0] = max(dp[i])

        dp[i+1][1] = max(dp[i-1])+A[i]

    print(max(dp[N]))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict

    inf = 10 ** 15

    N = int(input())
    *a, = map(int, input().split())

    it = iter(a)

    dp = [defaultdict(lambda: -inf) for _ in range(N + 1)]
    dp[0][0] = 0
    dp[1][0] = 0
    dp[1][1] = next(it)
    for i, x in enumerate(it, 2):
        mi = (i - 1) // 2
        ma = (i + 1) // 2
        for taken_count in range(mi, ma + 1):
            dp[i][taken_count] = max(
                dp[i - 1][taken_count],
                dp[i - 2][taken_count - 1] + x
            )

    ans = dp[N][N // 2]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    inf = -10**16
    if n%2:
        dp0 = [0]*n
        dp1 = [0]*n
        sumk = a[0]
        dp0[1] = inf
        dp1[1] = max([a[0], a[1]])
        if n > 2:
            dp0[2] = 0
            dp1[2] = max([a[2], dp1[1]])
            sumk += a[2]
        if n > 3:
            dp0[3] = max([dp1[2], a[3]])
            dp1[3] = max([a[0]+a[2], a[0]+a[3], a[1]+a[3]])
        for i in range(4, n):
            if i%2 == 0:
                dp0[i] = max([dp0[i-1], dp0[i-2]+a[i]])
                dp1[i] = max([dp1[i-1], dp1[i-2]+a[i]])
                sumk += a[i]
            else:
                dp0[i] = max([dp1[i-1], dp0[i-2]+a[i]])
                dp1[i] = max([dp1[i-2]+a[i], sumk])
        ans = dp1[n-1]
    else:
        key = sum(a[::2])
        ans = key
        for i in range(n-1, 0, -2):
            key += a[i]
            key -= a[i-1]
            if ans < key:
                ans = key
    print(ans)
            
    
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
def solve(pick, idx):

    if pick == 0: return 0
    if idx >= n: return -float('inf')
    if (pick, idx) in dp: return dp[pick, idx]
    if n-idx+2 < pick*2: return -float('inf')
    total = max(A[idx] + solve(pick-1, idx+2), solve(pick, idx+1))

    dp[(pick, idx)] = total
    return total

n = int(input())
A = list(map(int, input().split()))
dp = {}
pick = n//2

print(solve(pick, 0))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
inf = 10 ** 16
if N % 2:
  dp = [[-inf] * 3 for _ in range(N + 2)]
  dp[0][0] = 0
  dp[1][1] = 0
  dp[2][2] = 0
  if N > 4: dp[4][2] = a[0]
  for i in range(N):
    for j in range(3):
      if dp[i][j] == -inf: continue
      if i + 2 <= N + 1: dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + a[i])
      if i + 3 <= N + 1 and (j < 2): dp[i + 3][j + 1] = max(dp[i + 3][j + 1], dp[i][j] + a[i])
      if i + 4 <= N + 1 and (j == 0): dp[i + 4][j + 1] = max(dp[i + 4][j + 1], dp[i][j] + a[i])
  print(max(dp[-1][-1], dp[-2][-2], dp[-3][-3]))
  #print(dp)
else:
  dp = [[-inf] * 2 for _ in range(N + 2)]
  dp[0][0] = 0
  dp[1][1] = 0
  for i in range(N):
    for j in range(2):
      if dp[i][j] == -inf: continue
      if i + 2 <= N + 1: dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + a[i])
      if i + 3 <= N + 1 and (j < 1): dp[i + 3][j + 1] = max(dp[i + 3][j + 1], dp[i][j] + a[i])
  print(max(dp[-1][-1], dp[-2][-2]))
  #print(dp)

Submission status: Accepted

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

dp = [0] * (N + 1)
dp[2] = max(A[0], A[1])
s = A[0]
for i, a in enumerate(A, 1):
  if i <= 2:
    continue
  if i%2: # 奇数
    dp[i] = max(dp[i-1], a+dp[i-2])
    s += a
  else: # 偶数
    dp[i] = max(a+dp[i-2], s)

print(dp[-1])

Submission status: Accepted

Solution code:
N=int(input())

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

# まず、Nが3以下のときはAの最大値を返して終了
if N<=3:
  print(max(A))
  exit(0)

# 通常は1つ先まで進むが、
# Nが奇数の場合は2マス
# Nが偶数の場合は1マス
# どこかで余計に進むことができる。この余計に進んだマス数を保持してDP

if N&1:
  # Nが奇数の場合は最大2マス飛ばす権利がある
  dp=[[-((10**9) * (10**5))-1]*3 for i in range(N)]

  dp[0][0] = A[0] # 最初のマス
  dp[1][1] = A[1] # 1マス使う権利を行使
  dp[2][2] = A[2] # 2マス使う権利を行使
  for i in range(N):
    if i+2<N:
      # 通常の2マス進み
      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:
      # 1マス飛ばしパターン
      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:
      # 2マス飛ばしパターン
      if dp[i+4][2] < dp[i][0] + A[i+4]:
        dp[i+4][2] = dp[i][0] + A[i+4]
  
  # 以下の3パターンを比較する
  # 2マスの権利を使わずに最後2マス残す
  # 1マスの権利を残して最後1マス残す
  # 権利なしで最後のマス
  ans = max(dp[N-3][0],dp[N-2][1],dp[N-1][2])
  print(ans)
  
else:
  # Nが偶数の場合は最大1マス飛ばす権利がある
  # Nが奇数の場合は最大2マス飛ばす権利がある
  dp=[[-((10**9) * (10**5))-1]*2 for i in range(N)]

  dp[0][0] = A[0] # 最初のマス
  dp[1][1] = A[1] # 1マス使う権利を行使
  for i in range(N):
    if i+2<N:
      # 通常の2マス進み
      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:
      # 1マス飛ばしパターン
      if dp[i+3][1] < dp[i][0] + A[i+3]:
        dp[i+3][1] = dp[i][0] + A[i+3]
  
  # 以下の2パターンを比較する
  # 1マスの権利を残して最後1マス残す
  # 権利なしで最後のマス
  ans = max(dp[N-2][0],dp[N-1][1])
  print(ans)

Submission status: Accepted

Solution code:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# import itertools
# from operator import attrgetter, itemgetter
# import math

# from numba import jit
# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = [0] + list(map(int, readline().split()))

    if n == 2:
        print(max(a[1],a[2]))
        sys.exit()

    dp = [[0] * 2 for _ in range(n + 1)]

    # 普通に選ぶ場合
    dp[1][0] = 0
    dp[2][0] = max(a[1], a[2])
    dp[3][0] = max(a[1], a[2], a[3])

    # 1個多く選ぶ場合（奇数個のみ）
    dp[1][1] = a[1]
    dp[3][1] = a[1] + a[3]

    i = 4

    while i < n + 1:
        cur1 = a[i]

        # 偶数だよ
        dp[i][0] = max(dp[i - 1][1], dp[i - 2][0] + cur1)

        if i == n:
            break

        i += 1
        cur2 = a[i]

        # 奇数だよ
        dp[i][0] = max(dp[i - 2][0] + cur2, dp[i - 3][0] + cur2, dp[i - 1][0], dp[i - 2][1])
        dp[i][1] = dp[i - 2][1] + cur2

        i += 1

    print(dp[n][0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    if n % 2 == 0:
        dp = [[-10**18]*2, [-10**18]*2]
        dp[0][0] = 0
        for i in range(n):
            dp2 = [[-10**18]*2, [-10**18]*2]
            # 使う場合
            dp2[1][0] = max(dp2[1][0], dp[0][0]+a[i])
            dp2[1][1] = max(dp2[1][1], dp[0][1]+a[i])
            # 使わない場合
            dp2[0][1] = max(dp2[0][1], dp[0][0])
            # 更新
            dp2[0][0] = max(dp2[0][0], dp[1][0])
            dp2[0][1] = max(dp2[0][1], dp[1][1])
            dp = dp2
        print(max(dp[1][1], dp[0][0]))
        return
    dp = [[-10**18]*3, [-10**18]*3]
    dp[0][0] = 0
    for i in range(n):
        # 使う場合
        dp2 = [[-10**18]*3, [-10**18]*3]
        dp2[1][0] = max(dp2[1][0], dp[0][0]+a[i])
        dp2[1][1] = max(dp2[1][1], dp[0][1]+a[i])
        dp2[1][2] = max(dp2[1][2], dp[0][2]+a[i])
        # 使わない場合
        dp2[0][1] = max(dp2[0][1], dp[0][0])
        dp2[0][2] = max(dp2[0][2], dp[0][1])
        # 更新
        dp2[0][0] = max(dp2[0][0], dp[1][0])
        dp2[0][1] = max(dp2[0][1], dp[1][1])
        dp2[0][2] = max(dp2[0][2], dp[1][2])
        dp = dp2
    print(max(dp[1][2], dp[0][1]))


main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
##################################
# University of Wisconsin-Madison
# Author: Yaqi Zhang
##################################

# standard library
import sys
from functools import lru_cache

sys.setrecursionlimit(10**9)

Input = lambda: sys.stdin.readline().rstrip()
IntRead = lambda: int(Input())
LineRead = lambda: list(map(int, Input().split()))

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
# 奇数の時と偶数の時、奇数の場合は真ん中を選ぶかどうか
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
    if index >= N:
        return -INF
    if N - index + 1 < 2 * n:
        return -INF
    if N - index - 2 > 2 * n:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N==2:
    print(max(A))
elif N==3:
    print(max(A))
else:
    if N%2==1:
        dp=[[0 for i in range(0,3)] for i in range(0,N)]
        dp[0][2]=A[0]
        dp[0][1]=-float('inf')
        dp[0][0]=-float('inf')
        dp[1][2]=-float('inf')
        dp[1][1]=A[0]
        dp[1][0]=-float('inf')

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

        test1=dp[N-1][0]

        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=-float('inf')
        dp[0][0]=0
        dp[1][1]=A[1]
        dp[1][0]=-float('inf')

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

        test2=dp[N-1][0]

        A=A[::-1]
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=-float('inf')
        dp[0][0]=0
        dp[1][1]=A[1]
        dp[1][0]=-float('inf')

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

        test3=dp[N-1][0]

        test4=sum(A[i] for i in range(0,N) if i%2==1)

        print(max(test1,test2,test3,test4))

    if N%2==0:
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=A[0]
        dp[0][0]=-float('inf')
        dp[1][1]=-float('inf')
        dp[1][0]=A[0]

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

        test1=dp[N-1][0]

        test3=sum(A[i] for i in range(0,N) if i%2==0)
        test4=sum(A[i] for i in range(0,N) if i%2==1)

        print(max(test1,test3,test4))

Submission status: Accepted

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
if n%2==0:
  dp=[[0 for i in range(2)] for j 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]
      dp[i][1]=dp[i-2][1]+a[i]
    else:
      dp[i][0]=dp[i-2][0]+a[i]
      dp[i][1]=max(dp[i-2][1],dp[i-3][0])+a[i]
  print(max(dp[n-1][1],dp[n-2][0]))

else:
  dp=[[0 for i in range(3)] for j 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]
      dp[i][1]=dp[i-2][1]+a[i]
    else:
      dp[i][0]=dp[i-2][0]+a[i]
      dp[i][1]=max(dp[i-2][1],dp[i-3][0])+a[i]
      dp[i][2]=max(dp[i-2][2],dp[i-3][1],dp[i-4][0])+a[i]
  print(max(dp[n-1][2],dp[n-2][1],dp[n-3][0]))

Submission status: Accepted

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


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


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


main()

Submission status: Accepted

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

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

a_cs = [0] * (n + 1)
a_cs[-2] = a[-1]
for i in reversed(range(n - 1)):
    a_cs[i] = a[i] + a_cs[i + 2]
# print(a_cs)

d = {}


def func(i):
    if i == n:
        return 0
    if i == n - 1:
        return a[-1]
    if i in d:
        return d[i]

    m = n - i
    if m % 2 == 0:
        ans0 = a[i] + func(i + 2)
        ans1 = a_cs[i + 1]
        ans = max(ans0, ans1)
    else:
        ans0 = a[i + 0] + func(i + 2)
        ans1 = a[i + 1] + func(i + 3)
        ans2 = a_cs[i + 2]
        ans = max(ans0, ans1, ans2)

    d[i] = ans
    return ans


ans = func(0)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = list(map(int,input().split()))
import numpy as np
get_DP  = [[-np.inf for i in range(3)] for j in range(N)]
pass_DP = [[-np.inf for i in range(3)] for j in range(N)]
for i in range(N):
    # 常にとるやつ
    get_DP[i][0] = (pass_DP[i-1][0] if i>0 else 0) + S[i] 
    pass_DP[i][0] = get_DP[i-1][0]
    if i>0:
        get_DP[i][1] = (pass_DP[i-1][1] if i!=1 else 0) + S[i]
        pass_DP[i][1] = max(pass_DP[i-1][0], get_DP[i-1][1])
    if i>1:
        get_DP[i][2] = (pass_DP[i-1][2] if i!=2 else 0) + S[i]
        pass_DP[i][2] = max(pass_DP[i-1][1], get_DP[i-1][2])

    
print(max(get_DP[-1]+pass_DP[-1][:1+N%2]))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

# standard library
import sys
sys.setrecursionlimit(10**9)

from functools import lru_cache

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
    if index >= N:
        return -INF
    if N - index < 2 * n - 1:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)

Submission status: Accepted

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

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

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

print(dp[N - 1])

Submission status: Accepted

Solution code:
n = int(input())

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

def num_left(pos):
	if pos % 2 == 0:
		return (n - pos) // 2 + 1
	else:
		return (n - pos - 1) // 2 + 1

d = [{} for i in range(n)]
for i in range(n):

	if i < 2:
		d[i][0] = 0
		d[i][1] = a[i]

	else:			
		left = num_left(i + 2)
		#print("i = ", i, left)
		j = i - 2
		while j >= 0:
			max_count = max(d[j].keys())
			
			if max_count + left + 1	 < n // 2: 
				break

			else: 
				for count, v in d[j].items():
					#print(count, v)
					if count + left + 1 >= n // 2:
						if count + 1 in d[i]:
							d[i][count + 1] = max(d[i][count + 1], v + a[i])
						else:
							d[i][count + 1] = v + a[i]							
			j -= 1

		if 1 + left >= n // 2:
			d[i][0] = 0

best = None
for i in range(n):
	for count, result in d[i].items():
		if count == n // 2:
			if best is None:
				best = result
			else:
				best = max(best, result)

#print(d)
print(best)

Submission status: Accepted

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

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

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

else:
    dp = [[0, 0, 0] for i in range(N)]
    dp[0] = [A[0], 0, 0]

    for i in range(2, N, 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][1] + A[i], dp[i - 2][2] + A[i])

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

Submission status: Accepted

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

if  N % 2 == 0:
    M =  N // 2
    even_A = [A[i* 2] for i in range(M)]
    odd_A = [A[i* 2 + 1] for i in range(M)]
    even_sum = []
    _sum = 0
    for a in even_A:
        _sum += a
        even_sum.append(_sum)
    odd_sum = []
    _sum = 0
    for a in odd_A:
        _sum += a
        odd_sum.append(_sum)
    ans = max(odd_sum[-1], even_sum[-1])
    for i in range(M):
            x = even_sum[i] + odd_sum[-1] - odd_sum[i]
            ans = max(ans, x)
    print(ans)
    exit()
M =  N // 2
# evenが元一つ多い
even_A = [A[i* 2] for i in range(M+1)]
odd_A = [A[i* 2 + 1] for i in range(M)]
even_sum = []
_sum = 0
for a in even_A:
    _sum += a
    even_sum.append(_sum)
odd_sum = []
_sum = 0
for a in odd_A:
    _sum += a
    odd_sum.append(_sum)
# 全て奇数
all_even = even_sum[-1] - min(even_A)
diff_odd_even = [odd_sum[k] - even_sum[k+1] for k in range(M)]
diff_max_odd_even = []
diff_max = diff_odd_even[-1]
for k in range(M):
    diff_max = max(diff_max, diff_odd_even[-k-1])
    diff_max_odd_even.append(diff_max)
diff_max_odd_even.reverse()

ans = all_even
for i in range(M):
        x = even_sum[i] + odd_sum[-1] - odd_sum[i]
        y = odd_sum[i] + even_sum[-1] - even_sum[i+1]
        z = even_sum[i] + - odd_sum[i] + even_sum[-1] + diff_max_odd_even[i]
        ans = max(ans, x, y, z)
print(ans)

Submission status: Accepted

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