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

# dp[(i, x, flg)] := i番目までみてx個選んでいる時の最大値。flgは最後の１つをとったかどうか。
dp = defaultdict(lambda: -float('inf'))
dp[(0, 0, 0)] = 0

for i, a in enumerate(A, start=1):
    for x in range((i - 1) // 2, (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:
def main():
    from functools import lru_cache
    import sys

    sys.setrecursionlimit(10 ** 7)

    inf = 2 * 10 ** 14 + 1

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

    @lru_cache(maxsize=None)
    def recursion(cur, need):
        """
        cur: pickableなindex
        """
        if cur >= N:
            if need == 0:
                return 0
            else:
                return -inf

        rest = N - cur
        if (rest + 1) // 2 < need:
            return -inf

        return max(
            a[cur] + recursion(cur + 2, need - 1),
            recursion(cur + 1, need)
        )

    ans = recursion(0, N // 2)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

# dp[(i, x, flg)] := i番目までみてx個選んでいる時の最大値。flgは最後の１つをとったかどうか。
dp = defaultdict(lambda: -float('inf'))
dp[(0, 0, 0)] = 0

for i, a in enumerate(A, start=1):
    j = i // 2
    for x in range(j - 1, j + 2):
        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:
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:
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 20

dp = [{} for i in range(n + 1)]
dp[0][0] = 0

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

Submission status: Accepted

Solution code:

# -*- coding: utf-8 -*-

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

k=0
k1=As[0]
g=0
for i in range(2,N+1):
    if i%2==1:
        k=max(k+As[i-1],g)
        k1=k1+As[i-1]
    if i%2==0:
        g=max(k1,g+As[i-1])
    #print(k,k1,g)

ans=g if N%2==0 else k
print(ans)

Submission status: Accepted

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

if N%2==0:
  dp=[]
  for i in range(2):
    array=[0]*N
    dp.append(array)
    
  #init
  dp[0][0]=alist[0]
  dp[1][1]=alist[1]
  for i in range(2,N):
    dp[0][i]=dp[0][i-2]+alist[i]
    dp[1][i]=max(dp[1][i-2]+alist[i],dp[0][i-3]+alist[i])
    
  print(max(dp[0][-2],dp[1][-1]))
else:
  dp=[]
  for i in range(3):
    array=[0]*N
    dp.append(array)

  #init
  dp[0][0]=alist[0]
  dp[0][2]=alist[0]+alist[2]
  dp[1][1]=alist[1]
  dp[2][2]=alist[2]
  for i in range(3,N):
    dp[0][i]=dp[0][i-2]+alist[i]
    dp[1][i]=max(dp[1][i-2]+alist[i],dp[0][i-3]+alist[i])
    dp[2][i]=max(dp[2][i-2]+alist[i],dp[1][i-3]+alist[i],dp[0][i-4]+alist[i])

  #dp[0][-1] is NG
  print(max(dp[0][-3],dp[1][-2],dp[2][-1]))

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import defaultdict

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

INF = 10**18
dp_not = defaultdict(lambda : -INF)
dp_take = defaultdict(lambda: -INF)
dp_not[(0,0)] = 0

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

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [[-1 * pow(10, 15)] * 3 for _ in range(N)]
    if N == 2:
        return max(A)
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for i in range(N):
        if i < 2:
            continue
        dp[i][0] = dp[i-2][0] + A[i]
        if i < 3:
            continue
        dp[i][1] = max(dp[i-3][0], dp[i-2][1]) + A[i]
        if i < 4:
            continue
        dp[i][2] = max(dp[i-4][0], dp[i-3][1], dp[i-2][2]) + A[i]
    if N % 2 == 0:
        return max(dp[-1][1], dp[-2][0])
    else:
        return max(dp[-1][2], dp[-2][1], dp[-3][0])
print(main())

Submission status: Accepted

Solution code:
# coding: utf-8

N=int(input())
A=list(map(int,input().split()))
INF=10**18

dp=[[-INF for i in range(2)] for j in range(N+1)]
dp[0][0]=0
dp[1][0]=0
dp[2][0]=0
dp[1][1]=A[0]
dp[2][1]=A[1]

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

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n = int(input())
A = get_nums_l()

# スキップできる回数
p = 1 if n%2==0 else 2
# log(p)

# dp[i][j][k] i==1なら次取れる スキップ回数をj回残してk個目まで見たときの最大和
dp = [ [ [0]*(n+1) for _ in range(p+1) ] for _ in range(2) ]

dp[0][0][0] = -999999999999999999
dp[0][1][0] = -999999999999999999
dp[1][0][0] = -999999999999999999
if p == 2:
    dp[0][2][0] = -999999999999999999
    dp[1][1][0] = -999999999999999999

# log(dp)

for k in range(n):
    dp[0][0][k+1] = dp[1][0][k] + A[k]
    dp[0][1][k+1] = dp[1][1][k] + A[k]
    dp[1][0][k+1] = max(dp[1][1][k], dp[0][0][k])
    dp[1][1][k+1] = dp[0][1][k]

    if p == 2:
        dp[0][2][k+1] = dp[1][2][k] + A[k]
        dp[1][2][k+1] = dp[0][2][k]
        #dp[1][0][k+1] = max(dp[1][0][k+1], dp[1][1][k])
        dp[1][1][k+1] = max(dp[1][1][k+1], dp[1][2][k])

# for a in dp:
#     for b in a:
#         log(b)


ans = [dp[0][0][n], dp[0][1][n], dp[1][0][n], dp[1][1][n]]
if p == 2:
    # ans.append(dp[0][2][n])
    ans.append(dp[1][2][n])
print(max(ans))

Submission status: Accepted

Solution code:
import sys

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

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

main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

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

dp = np.full((N, 3), 0, dtype=int)

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

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

print(ans)

Submission status: Accepted

Solution code:
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:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# F - Select Half

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

# memo[i][m] a[0:i+1]からm個選ぶときの最大値
memo = [{} for i in range(n)]
memo[0] = {0: 0, 1: a[0]}
memo[1] = {1: max(a[:2])}

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

print(memo[-1][n // 2])

Submission status: Accepted

Solution code:
# F - Select Half

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

l = [0] * n # a[0]〜a[i]からfloor((i+1)/2)個選ぶときの最大値
u = [0] * n # a[0]〜a[i]からceil((i+1)/2)個選ぶときの最大値

l[0] = 0
u[0] = a[0]
u[1] = max(a[:2])
l[1] = u[1]

# 0 1 2 3 4 5 6 7 8 9 10 i
# . . . . . . . . . . .
# 1 1 2 2 3 3 4 4 5 5 6  u[i]
# 0   1   2   3   4   5  l[i]

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

print(l[-1])

Submission status: Accepted

Solution code:
import sys,math,copy,queue,itertools,bisect
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
MOD = 10**9 + 7
INF = 10**15

N = NI()
A = LI()
ans = 0
if N % 2 == 0:
    for i in range(1,N,2):
        ans += A[i]
    x = ans
    for i in range(0,N,2):
        x = x + A[i] - A[i+1]
        ans = max(ans,x)
else:
    dp = [0 for _ in range(3)]
    for i in range(N):
        ai = A[i]
        if i % 2 == 0:
            dp[1] = max(dp[0],dp[1])
            dp[0] = dp[0] + ai
        if i % 2 == 1:
            dp[2] = max(dp[1],dp[2])
            dp[1] += ai
        if i % 2 == 0 and i > 0:
            dp[2] += ai
    ans = max(dp[1],dp[2])
print (ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    A = list(map(int, rl().split()))
    
    dp = [0] * N
    dp[1] = max(A[:2])
    odd = A[0]
    
    for i in range(2, N):
        if i % 2 == 0:
            odd += A[i]
            dp[i] = max(dp[i - 2] + A[i], dp[i - 1])
        else:
            dp[i] = max(dp[i - 2] + A[i], odd)
    print(dp[-1])


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

def main():
    mod=10**9+7
    inf=10**20
    N=I()
    A=LI()
    """左から見ていく，i個を見たときに，
    i//2 ±1の範囲なので，状態は3N通り
    """
    
    p1=[-inf]*N
    zero=[-inf]*N
    n1=[-inf]*N
    
    p1[0]=A[0]
    zero[0]=0
    zero[1]=max(A[0],A[1])
    n1[1]=0
    
    for i in range(2,N):
        #偶奇で遷移の仕方に変化
        if i%2==0:
            p1[i]=max(p1[i-2]+A[i],p1[i-1])#2つ前の状態から取る or 1つ前の状態から取らない
            zero[i]=max(zero[i-2]+A[i],zero[i-1])
            n1[i]=max(n1[i-2]+A[i],n1[i-1])
        else:
            p1[i]=p1[i-2]+A[i]
            zero[i]=max(zero[i-2]+A[i],p1[i-1])
            n1[i]=max(n1[i-2]+A[i],zero[i-1])
            
    """        
    print(p1)
    print(zero)
    print(n1)"""
    
    print(zero[-1])
    
    
        
        
        

main()

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int,input().split()))
dp = [[-float("INF")]*(3) for i in range(n+1)]
dp[0][0] = 0
dp[1][-1] = 0
dp[1][1] = l[0]
for i in range(1,n):  
    dp[i+1][-1] = max(dp[i][0],dp[i-1][-1]+l[i])
    dp[i+1][0] = max(dp[i][1],dp[i-1][0]+l[i])
    dp[i+1][1] = dp[i-1][1]+l[i]
    
print(max(dp[-1][0],dp[-1][-1]))

Submission status: Accepted

Solution code:
n = int(input())
def main():
    import sys
    input = sys.stdin.readline
    l = list(map(int,input().split()))
    dp = [[-float("INF")]*(3) for i in range(n+1)]
    dp[0][0] = 0
    dp[1][-1] = 0
    dp[1][1] = l[0]
    for i in range(1,n):
        
        dp[i+1][-1] = max(dp[i][0],dp[i-1][-1]+l[i])
        dp[i+1][0] = max(dp[i][1],dp[i-1][0]+l[i])
        dp[i+1][1] = dp[i-1][1]+l[i]
    print(max(dp[-1][0],dp[-1][-1]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
INF = 10**18

dp0 = [-INF] * (N + 2)
dp1 = [-INF] * (N + 2)
dp2 = [-INF] * (N + 2)
dp0[0] = 0
dp0[1] = 0
dp1[0] = 0
dp1[1] = 0

for i, a in enumerate(A, start=2):
    dp0[i] = dp0[i - 2] + a
    dp1[i] = max(dp1[i - 2] + a, dp0[i - 1])
    dp2[i] = max(dp2[i - 2] + a, dp1[i - 1], dp0[i - 2])

if N % 2 == 1:
    print(dp2[-1])
else:
    print(max(dp1[-1], dp0[-1]))

Submission status: Accepted

Solution code:
n = int(input())
*A, = map(int, input().split())
inf = 10**18
# DP[i][0]=i番目まででi//2個選んだ最大値
# DP[i][1]=i番目まででi//2+1個選んだ最大値
DP = [[-inf]*2 for i in range(n)]
DP[0][0] = 0
DP[0][1] = A[0]
DP[1][0] = 0
DP[1][1] = max(A[0], A[1])
for i in range(2, n):
    if i % 2 == 0:
        DP[i][0] = max(DP[i-2][0]+A[i], DP[i-1][1])
        DP[i][1] = DP[i-2][1]+A[i]
    else:
        DP[i][0] = max(DP[i-2][0]+A[i], DP[i-1][0])
        DP[i][1] = max(DP[i-2][1]+A[i], DP[i-1][1])
if n % 2 == 0:
    print(DP[n-1][1])
else:
    print(DP[n-1][0])

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
    '''index以降、n個選ぶ最大値を返す'''
    if index >= N: 
        return -INF
    if N - index < 2 * n - 1:  # 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==1:
    dp=[[0 for j in range(3)] for i in range(n//2)]
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    dp[0][2]=a[2]
    for i in range(n//2-1):
        dp[i+1][0]=(dp[i][0]+a[2*(i+1)])
        dp[i+1][1]=max(dp[i][0],dp[i][1])+a[2*(i+1)+1]
        dp[i+1][2]=max(dp[i])+a[2*(i+1)+2]
    print(max(dp[-1]))
if n%2==0:
    dp=[[0 for j in range(2)] for i in range(n//2)]
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    for i in range(n//2-1):
        dp[i+1][0]=(dp[i][0]+a[2*(i+1)])
        dp[i+1][1]=max(dp[i][0],dp[i][1])+a[2*(i+1)+1]
        #dp[i+1][2]=max(dp[i])+a[2*(i+2)+2]
    print(max(dp[-1]))

Submission status: Accepted

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
dp0 = 0
dp1 = 0
dp2 = 0
for i in range(1,n+1):
  ai = a[i-1]
  if i%2:
    dp1 = max(dp0,dp1)
    dp0 += ai
  if i%2 == 0:
    dp2 = max(dp1,dp2)
    dp1 += ai
  if i >= 3 and i%2:
    dp2 += ai
if n%2 == 0:
  print(max(dp0,dp1))
else:
  print(max(dp1,dp2))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

def main():
    N=int(input())
    A=list(map(int,input().split()))
    dp=[[-INF]*3 for _ in range(N+10)]
    dp[0][0]=0
    for i in range(N+1):
        for j in range(3):
            if j+1<3:
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j])
            if i<N:
                dp[i+2][j]=max(dp[i+2][j],dp[i][j]+A[i])
    if N%2:
        print(dp[N+1][2])
    else:
        print(dp[N+1][1])
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


n = 0
a = []

def format_input(filename = None):
	global n
	global a
	if filename == None:
		n = int(input())
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 2 * 10**5)
		a = [rng(-1 * 10**9, 10**9) for i in range(n)]
		print(n)
		print(' '.join(list(map(str, a))))

def get_answer():
	odd = [0]
	even = [0]
	for i in range(n // 2):
		odd.append(odd[-1] + a[2*i])
		even.append(even[-1] + a[2*i+1])
	if n % 2 == 1:
		odd.append(odd[-1] + a[-1])

	answer = -1 * 10**9 * n
	if n % 2 == 0:
		for i in range(n // 2 + 1):
			answer = max(answer, odd[i] - even[i] + even[-1])
	else:
		even_range = [even[0] - odd[1]]
		for i in range(n // 2):
			add = a[2*i+1] - a[2*i+2]
			min = - a[2*i] + add
			even_range.append(max(even_range[-1] + add, min))
		answer = odd[-1] + max(even_range)
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int,input().split()))
ans = -1000000000000000
dp = [{} for _ in range(n)]
dp[0][1] = s[0]
dp[1][1] = s[1]
if n >= 3:
    dp[2][1] = s[2]
for i in range(n):
    for x in dp[i].keys():
        y = dp[i][x]
        if x == n//2:
            ans = max(ans,y)
        else:
            if (n-(i+2)+1)//2 >= n//2-(x+1) and i+2 <= n-1:
                if x+1 in dp[i+2].keys():
                    dp[i+2][x+1] = max(dp[i+2][x+1],dp[i][x] + s[i+2])
                else:
                    dp[i+2][x+1] = dp[i][x] + s[i+2]
            if (n-(i+3)+1)//2 >= n//2-(x+1) and i+3 <= n-1:
                if x+1 in dp[i+3].keys():
                    dp[i+3][x+1] = max(dp[i+3][x+1],dp[i][x] + s[i+3])
                else:
                    dp[i+3][x+1] = dp[i][x] + s[i+3]
            if (n-(i+4)+1)//2 >= n//2-(x+1) and i+4 <= n-1:
                if x+1 in dp[i+4].keys():
                    dp[i+4][x+1] = max(dp[i+4][x+1],dp[i][x]+s[i+4])
                else:
                    dp[i+4][x+1] = dp[i][x]+s[i+4]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *
 
sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

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

dp = [{} for _ in range(N + 1)]
dp[0] = {0: 0}
dp[1] = {0: 0, 1: A[0]}

for i in range(2, N + 1):
    for j in range(max(0, i // 2 - 2), min(N, i // 2 + 2) + 1):
        candidates = []
        if j - 1 in dp[i - 2]:
            candidates.append(dp[i - 2][j - 1] + A[i - 1])
        if j in dp[i - 1]:
            candidates.append(dp[i - 1][j])
        if len(candidates) > 0:
            dp[i][j] = max(candidates)

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

n,*a = [int(i) for i in read().split()]

from itertools import accumulate
if n%2==0:
    a1 = list(accumulate([0]+a[::2]))
    a2 = list(accumulate([0]+a[n-1::-2]))[::-1]
    #print(a1,a2)
    print(max(x+y for x,y in zip(a1,a2)))
#elif n==3: print(max(a))
else:
    dp0 = [0]*(n+9)
    dp1 = [0]*(n+9)
    dp2 = [0]*(n+9)
    for i in range(n):
        if i%2==0:
            dp0[i] = dp0[i-2]+a[i]
            if i >= 2:
                dp2[i] = max(dp2[i-2],dp1[i-3],dp0[i-4]) + a[i]
        else:
            dp1[i] = max(dp1[i-2],dp0[i-3]) + a[i]
    #print(dp0)
    #print(dp1)
    #print(dp2)
    print(max(dp2[n-1],dp1[n-2],dp0[n-3]))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    A = list(map(int,input().split()))

    if n & 1 == 0:
        res = -INF
        score = sum(A[::2])
        res = max(res, score)
        for i in range(n-1,-1,-1):
            if i & 1:
                score += A[i]
            else:
                score -= A[i]
                res = max(res, score)
        print(res)
        return

    front_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(1, n, 2):
        choose, not_choose = max(choose, not_choose) + A[i], not_choose + A[i-1]
        front_dp[i] = max(choose, not_choose)

    back_dp = [None] * n
    choose = -INF
    not_choose = 0
    for i in range(n-2, -1, -2):
        choose, not_choose = max(choose, not_choose) + A[i], not_choose + A[i+1]
        back_dp[i] = max(choose, not_choose)

    res = -INF
    for i in range(1, n, 2):
        if i + 2 < n:
            res = max(res, front_dp[i] + back_dp[i+2])

    res = max(res, front_dp[-2])
    res = max(res, back_dp[1])

    print(res)
resolve()

Submission status: Accepted

Solution code:
N = int(input()) + 2
X = [0, 0] + list(map(int, input().split()))
dp = [[0, 0] for _ in range(N)]
for i in range(2, N):
    if i%2:
        dp[i][1] = max(dp[i-2][1] + X[i], dp[i-1][1])
        dp[i][0] = max(dp[i-2][0] + X[i], dp[i-1][0])
    else:
        dp[i][1] = dp[i-2][1] + X[i]
        if i!=2:
            dp[i][0] = max(dp[i-2][0] + X[i], dp[i-1][1])
#print(dp)
if N%2:
    print(dp[-1][0])
else:
    print(dp[-1][1])

Submission status: Accepted

Solution code:
N = int(input())
A = [0]+list(map(int, input().split(" ")))

dp_list = [{0, 0}, {0: 0, 1: A[1]}, {0: 0, 1: A[1] if A[1] > A[2] else A[2]}]

for i in range(3, N+1):
    b = (i-1)//2
    f = (i+1)//2
    dp_list.append({})
    for j in range(b, f+1):
        if j in dp_list[i-1]:
            dp_list[i][j] = dp_list[i-2][j-1]+A[i] if dp_list[i -
                                                              2][j-1]+A[i] > dp_list[i-1][j] else dp_list[i-1][j]
        else:
            dp_list[i][j] = dp_list[i-2][j-1]+A[i]

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

dp0 = list2d(N+1, 4, -INF)
dp1 = list2d(N+1, 4, -INF)
dp0[0][2] = 0
for i, a in enumerate(A):
    for j in range(4):
        if j != 0:
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp0[i][j])
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp1[i][j])
        if j != 3:
            dp1[i+1][j+1] = max(dp1[i+1][j+1], dp0[i][j] + a)
if N % 2 == 0:
    ans = max(dp0[N][2], dp1[N][2])
else:
    ans = max(dp0[N][1], dp1[N][1])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
totalChooseNum = N // 2
dp = {0 : 0}
for i in range(0, N):
    ai = A[i]
    canChooseNum = (N - i + 1) // 2
    mustChooseNum = max(totalChooseNum - canChooseNum, 0)
    next = {}
    for j in range(mustChooseNum, N):
        if j > 0 and (2 * (j - 1)) in dp:
            next[2 * j + 1] = dp[2 * (j - 1)] + ai
        if 2 * j in dp:
            if 2 * j + 1 in dp:
                next[2 * j] = max(dp[2 * j] , dp[2 * j + 1])
            else:
                next[2 * j] = dp[2 * j]
        elif 2 * j + 1 in dp:
            next[2 * j] = dp[2 * j + 1]
        else:
            break
    dp = next
result = max(dp[totalChooseNum * 2] , dp[totalChooseNum * 2 + 1])
print(result)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    if not n&1:
        dp = a[:2]
        for i in range(2,n)[::2]:
            nd = [-float("inf")]*2
            nd[0] = dp[0]+a[i]
            nd[1] = max(dp)+a[i+1]
            dp = [j for j in nd]
        print(max(dp))
        return
    dp = a[:3]
    dp[0] = a[0]
    dp[1] = a[1]
    dp[2] = a[2]
    for i in range(2,n-1)[::2]:
        nd = [-float("inf")]*3
        nd[0] = dp[0]+a[i]
        nd[1] = max(dp[0],dp[1])+a[i+1]
        nd[2] = max(dp)+a[i+2]
        dp = [j for j in nd]
    print(max(dp))
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# ABC162F - Select Half

import sys
input = sys.stdin.buffer.readline

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

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

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

main()