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


main()

Submission status: Accepted

Solution code:
N = int(input())
A = tuple(map(int,input().split()))
from collections import defaultdict
dp_non = defaultdict(lambda: -2**60)
dp_take = defaultdict(lambda: -2**60)
dp_non[(0,0)] = 0
for i,x in enumerate(A,1):
    j = (i-1)//2
    for n in (j,j+1):
        dp_non[(i,n)] = max(dp_non[(i-1,n)],dp_take[(i-1,n)])
        dp_take[(i,n)] = dp_non[(i-1,n-1)]+x
print(max(dp_non[N,N//2],dp_take[(N,N//2)]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
MINF = float('-inf')
As = (map(int, input().split()))

dp = [[[0 for ___ in range(2)] for __ in range(2)] for _ in range(N+3)]

if N % 2 == 0:
    for i, a in enumerate(As):
        if i % 2 == 0:
            dp[i][0][0] = max(dp[i-2][1][1], dp[i-1][1][1])
            dp[i][0][1] = MINF
            dp[i][1][0] = MINF
            dp[i][1][1] = dp[i-2][1][1] + a
        else:
            dp[i][0][0] = MINF
            dp[i][0][1] = MINF
            dp[i][1][0] = dp[i-1][1][1]
            dp[i][1][1] = max(dp[i-3][1][1], dp[i-2][1][1]) + a
else:
    for i, a in enumerate(As):
        if i % 2 == 0:
            dp[i][0][0] = max(dp[i-1][1][0], dp[i-1][1][1])
            dp[i][0][1] = dp[i-1][0][0] + a
            dp[i][1][0] = MINF
            dp[i][1][1] = dp[i-1][1][0] + a
        else:
            dp[i][0][0] = max(dp[i-1][0][0], dp[i-1][0][1])
            dp[i][0][1] = MINF
            dp[i][1][0] = dp[i-1][1][1]
            dp[i][1][1] = dp[i-1][0][0] + a
print(max(dp[N-1][0][0], dp[N-1][0][1], dp[N-1][1][0], dp[N-1][1][1]))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N%2==0:
    dp=[[-float("inf") for _ in range(2)] for _ in range(N+10)]
    if N==2:
        print(max(A[0],A[1]))
    else:
        for i in range(N):
            if i==0:
                dp[i][0]=A[0]
            elif i==1:
                dp[i][1]=A[1]
            elif i==2:
                dp[i][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]))
else:
    #print(A[0],A[1])
    dp=[[-float("inf") for _ in range(3)] for _ in range(N+10)]
    if N==3:
        print(max(A[0],A[1],A[2]))
    else:
        for i in range(N):
            if i<4:
                if i==0:
                    dp[i][0]=A[0]
                if i==1:
                    dp[i][1]=A[1]
                if i==2:
                    dp[i][2]=A[2]
                    dp[i][0]=A[0]+A[2]
                if i==3:
                    dp[i][1]=max(dp[1][1]+A[3],dp[0][0]+A[3])
            else:
                for j in range(3):
                    if j==0:#ここでも2こずつ規則よく飛ばすと決めた
                        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])
                    else:
                        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])
        print(max(dp[N-1]))

Submission status: Accepted

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

if N % 2 == 0: #偶数のとき
    B = [0] * (N // 2 + 1)
    W = [0] * (N // 2 + 1)
    for i in range(N // 2):
        B[i + 1] = B[i] + A[2 * i]
    for i in range(N // 2 - 1, -1, -1):
        W[i] = W[i + 1] + A[2 * i + 1]

    # print (B)
    # print (W)

    ans = -10 ** 16
    for i in range(N // 2 + 1):
        ans = max(ans, B[i] + W[i])

    print (ans)
    exit()

DP0 = [[-10 ** 16] * 2 for _ in range(N + 1)]
DP1 = [[-10 ** 16] * 2 for _ in range(N + 1)]
DP2 = [[-10 ** 16] * 2 for _ in range(N + 1)]

DP0[N][0] = 0 #右端の外側を0に設定してスタート

for i in range(N - 1, -1, -1):
    a = A[i]
    
    DP0[i][0] = DP0[i + 1][1]
    DP0[i][1] = DP0[i + 1][0] + a

    DP1[i][0] = max(DP1[i + 1][1], DP0[i + 1][0])
    DP1[i][1] = DP1[i + 1][0] + a

    DP2[i][0] = max(DP2[i + 1][1], DP1[i + 1][0])
    DP2[i][1] = DP2[i + 1][0] + a
    
if N % 2 == 1:
    print (max(DP1[0][0], DP2[0][1]))
else:
    print (max(DP0[0][0], DP1[0][1]))

# for i in DP0:
#     print (i)

# for i in DP1:
#     print (i)

# for j in DP2:
#     print (j)

Submission status: Accepted

Solution code:

if __name__ == "__main__":
    n = int(input())
    nums = [int(s) for s in input().split()]
    odds = [0]        
    for num in nums[::2]:
        odds.append(num + odds[-1])
    
    res = [0]
    for i, num in enumerate(nums[1::2]):
        res.append(max(res[-1]+num, odds[i+1]))
    
    if n % 2 == 0:
        print(res[-1])
    else:
        ans = float('-inf')
        for i, r in enumerate(res):
            ans = max(ans, res[i] + odds[-1] - odds[i+1])
        print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

MOD = 1000000007

def smax(a,b):
    if a>b:
        return a
    else:
        return b

def smin(a,b):
    if a<b:
        return a
    else:
        return b

def main():
    N = int(readline())
    A = list(map(int,readline().split()))
    if N%2==0:
        A.append(0)
        DP = [[[-10**27]*2 for j in range(2)] for i in range(N+2)]
        DP[0][0][0] = 0
        for i in range(N+1):
            DP[i+1][0][0] = DP[i][0][1]
            DP[i+1][1][0] = smax(DP[i][0][0],DP[i][1][1])
            DP[i+1][0][1] = DP[i][0][0]+A[i]
            DP[i+1][1][1] = DP[i][1][0]+A[i]
            #print(DP[i+1][1][0])
        print(DP[N+1][1][0])

    else:
        A.append(0)
        DP = [[[-10**27]*2 for j in range(3)] for i in range(N+2)]
        DP[0][0][0] = 0
        for i in range(N+1):
            DP[i+1][0][0] = DP[i][0][1]
            DP[i+1][1][0] = smax(DP[i][0][0],DP[i][1][1])
            DP[i+1][2][0] = smax(DP[i][1][0],DP[i][2][1])
            DP[i+1][0][1] = DP[i][0][0]+A[i]
            DP[i+1][1][1] = DP[i][1][0]+A[i]
            DP[i+1][2][1] = DP[i][2][0]+A[i]
            #print(DP[i+1][1][0])
        print(DP[N+1][2][0])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

if n % 2 == 0:
    prefix = [0] * n
    suffix = [0] * n
    for i in range(0, n):
        prefix[i] += nums[i]
        if i - 2 >= 0:
            prefix[i] += prefix[i - 2]

    for i in range(n-1, -1, -1):
        suffix[i] += nums[i]
        if i + 2 < n:
            suffix[i] += suffix[i + 2]
    ans = max(prefix[-1], prefix[-2])

    for i in range(n):
        if i % 2 == 0 and  i + 2 < n:
            ans = max(ans, prefix[i] + suffix[i + 2])
        if i % 2 == 0 and  i + 3 < n:
            ans = max(ans, prefix[i] + suffix[i + 3])
        if i % 2 == 1 and i + 2 < n:
            ans = max(ans, prefix[i] + suffix[i + 2])
    print(ans)
else:
    dp = [[0] * n for i in range(3)] # -1, 0, +1
    # dp[delta][num], inclusive
    dp[2][0] = nums[0]
    dp[0][1] = 0
    dp[1][1] = max(nums[0], nums[1])
    dp[2][1] = 0
    dp[0][2] = 0
    dp[1][2] = max(nums[:3])
    dp[2][2] = nums[0] + nums[2]
    if n == 3:
        print(max(nums))
        exit()
    dp[0][3] = max(nums[:4]) # only choose one
    dp[1][3] = max(nums[0] + nums[3], nums[0] + nums[2], nums[1] + nums[3])
    dp[2][3] = 0
    dp[0][4] = max(nums[:5])
    dp[1][4] = max([nums[i] + nums[j] for i in range(5) for j in range(i+2, 5)])
    dp[2][4] = nums[0] + nums[2] + nums[4]

    for i in range(5, n):
        if (i + 1) % 2 == 0: # even
            dp[0][i] = max(dp[1][i - 1], dp[0][i - 2] + nums[i])
            dp[1][i] = max(dp[2][i - 1], dp[1][i - 2] + nums[i])  # 0
        else:
            # odd
            dp[0][i] = max(dp[0][i - 1], nums[i] + dp[0][i - 2])
            dp[1][i] = max(dp[1][i - 2] + nums[i], dp[1][i - 1], dp[2][i - 2])
            dp[2][i] = dp[2][i - 2] + nums[i] # ok
    print(max(dp[1][-1], dp[2][-3], dp[1][-2]))

Submission status: Accepted

Solution code:
# dpでいけそう
n = int(input())
a = list(map(int, input().split()))
INF = 10**16

ans = -INF

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n<=3:print(max(a));exit()
if n&1:
  dp=[3*[-(10**20)]for _ in range(n)]
  dp[0][0]=a[0]
  for i in range(1,n):
    if i%2==0:
      dp[i][0]=dp[i-2][0]+a[i]
      if i>=3:dp[i][2]=max(dp[i-2][2]+a[i],dp[i-3][1]+a[i])
      else:dp[i][2]=a[i]
    else:
      if i>=3:dp[i][1]=max(dp[i-2][1]+a[i],dp[i-3][0]+a[i])
      else:dp[i][1]=a[i]
  print(max(dp[-1][2],dp[-2][1],dp[-3][0]))
else:
  b=[a[0]]
  c=[a[1]]
  for i in range(2,n):
    if i%2==0:b.append(b[-1]+a[i])
    else:c.append(c[-1]+a[i])
  ans=max(b[-1],c[-1])
  for i in range(n//2-1):
    ans=max(ans,b[i]+c[-1]-c[i])
  print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a0, a1, a2, b0, b1, b2 = 0, 0, 0, 0, 0, 0
    for i, a in enumerate(A):
        a0, a1, a2, b0, b1, b2 = (
                b0,
                max(b1, a0),
                max(b2, a1),
                a0 + a,
                a1 + a if i >= 1 else a1,
                a2 + a if i >= 2 else a2)

    if N & 1:
        return max(b2, a1)
    else:
        return max(b1, a0)


print(main())

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()

dp = [0]*n
b = a[0]

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

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

print(dp[-1])

Submission status: Accepted

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

m = 2+n%2
dp = [[-10**18]*m for i in range(n+2)]
dp[0][0] = 0
for i in range(n):
    for j in range(m):
        if i%2 == j%2:
            x = a[i]
        else:
            x = 0
        if dp[i+1][j] < dp[i][j] + x:
            dp[i+1][j] = dp[i][j] + x
        if j+1 < m and dp[i+1][j+1] < dp[i][j]:
            dp[i+1][j+1] = dp[i][j]
print(max(dp[n][m-2], dp[n][m-1]))

Submission status: Accepted

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

dp = [0]*N

cum = A[0]
for i in range(N):
    if i == 0:
        dp[i] = 0
        continue
    if i == 1:
        dp[i] = max(A[0],A[1])
        continue
    if i%2==0: #奇数の時
        cum += A[i]
        dp[i] = max(dp[i-1],dp[i-2]+A[i])

    if i%2==1: #偶数の時
        dp[i] = max(dp[i-2]+A[i],cum)

ans = dp[-1]


print(ans)
#print(*ans, sep='\n')

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
c = 0
if N%2 == 0:
    for i in range(N//2):
        c += A[2*i+1]
    cm = c
    # print(c)
    for i in range(N//2):
        # print(2*i,2*i+1)
        c += A[2*i]-A[2*i+1]
        cm = max(c,cm)
    print(cm)
else:
    dp = [[0]*(3) for _ in range(N//2)]
    # print(dp)
    # 初期化
    dp[0][0] = A[0]
    dp[0][1] = A[1]
    dp[0][2] = A[2]
    for i in range(0,N//2-1):
        dp[i+1][0] = dp[i][0] + A[2*i+2]
        dp[i+1][1] = max(dp[i][0] + A[2*i+3], dp[i][1] + A[2*i+3])
        dp[i+1][2] = max(dp[i][0] + A[2*i+4], dp[i][1] + A[2*i+4], dp[i][2] + A[2*i+4])
    # print(dp)
    print(max(dp[N//2-1][0],dp[N//2-1][1],dp[N//2-1][2]))

Submission status: Accepted

Solution code:
from math import gcd

############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input().rstrip()))
def inlt():
    return(list(map(int,input().rstrip().split())))
def insr():
    s = input().rstrip()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().rstrip().split()))
################################################################
n = inp()
nums = [0] + inlt()
dp = [0 for i in range(n + 1)]
s = [0 for i in range(n + 1)]
s[1] = nums[1]
for i in range(3,n,2):
    s[i] = s[i - 2] + nums[i]
if n == 1:
    print(nums[0])
elif n == 2:
    print(max(nums[1],nums[2]))
elif n == 3:
    print(max(nums[3],nums[1],nums[2]))
elif n == 4:
    print(max(nums[1] + nums[3],nums[1] + nums[4],nums[2] + nums[4]))
else:
    dp[1] = nums[1]
    dp[2] = max(nums[1],nums[2])
    dp[3] = max(nums[3],nums[1],nums[2])
    dp[4] = max(nums[1] + nums[3],nums[1] + nums[4],nums[2] + nums[4])
    for i in range(5,n + 1):
        if i % 2 == 0:
            dp[i] = max(dp[i - 2] + nums[i], s[i - 1]) #if n % 2 == 0 take sum else dp[i - 1]
        else:
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
    print(dp[n])
#print('No')
#print()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

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

if N==2:
    print(max(0,A[0],A[1]))
    exit()
if N==3:
    print(max(0,A[0],A[1],A[2]))
    exit()

dp=[[-10**18 for i in range(N)] for j in range(3)]
dp[0][0]=A[0]
dp[1][1]=A[1]
dp[2][2]=A[2]

for n in range(3):
    for index in range(N):
        if dp[n][index]!=-1:
            if n!=2 and index+3<N:
                dp[n+1][index+3]=max(dp[n+1][index+3],dp[n][index]+A[index+3])
            if n==0 and index+4<N:
                dp[n+2][index+4]=max(dp[n+2][index+4],dp[n][index]+A[index+4])
            if index+2<N:
                dp[n][index+2]=max(dp[n][index+2],dp[n][index]+A[index+2])

a=(dp[0][-1])
b=(dp[1][-1])
c=(dp[2][-1])

print(max(a,b,c))

Submission status: Accepted

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


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


a = a[::-1]
ruiseki0 = [0] * (n + 10) 
for i in range(n):
    ruiseki0[i + 1] = ruiseki0[i]
    if i % 2 == 0:
        ruiseki0[i + 1] += a[i]

r = [0] * (n + 1)
for i in range(n + 1):
    r[i] = ruiseki0[i]
    if i % 2 == 0:
        if i == 0:
            r[i] = 0
        else:
            r[i] = max(r[i - 2] + a[i - 1], r[i])
   
ans = - 10 ** 20
for i in range(n):
    if n - i - 2 < 0:
        break
    if n % 2 == 0 and i % 2 == 0:
        continue
    ans = max(ans, l[i] + r[n - i - 2])
    
if n % 2 == 0:
    ans1 = 0
    ans2 = 0
    for i in range(n):
        if i % 2 == 0:
            ans1 += a[i]
        else:
            ans2 += a[i]
    ans = max(ans1, ans2, ans)
if n % 2 == 1:
    ans = max(ans, sum(a)- ruiseki0[n])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
c = 0
if N%2 == 0:
    dp = [[0,0] for _ 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+2]
        dp[i+1][1] = max(dp[i][0] + A[2*i+3], dp[i][1] + A[2*i+3])
    # print(dp)
    print(max(dp[N//2-1][0],dp[N//2-1][1]))
else:
    dp = [[0,0,0] for _ in range(N//2)]
    # print(dp)
    # 初期化
    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+2]
        dp[i+1][1] = max(dp[i][0] + A[2*i+3], dp[i][1] + A[2*i+3])
        dp[i+1][2] = max(dp[i][0] + A[2*i+4], dp[i][1] + A[2*i+4], dp[i][2] + A[2*i+4])
    # print(dp)
    print(max(dp[N//2-1][0],dp[N//2-1][1],dp[N//2-1][2]))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
A = LI()


if N%2 == 0:
    d = defaultdict(lambda:defaultdict(lambda:-float('inf')))
    d[0][1] = A[0]
    d[1][1] = max(A[0],A[1])
    for i in range(2,N):
        if i%2 == 0:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
        else:
            for j in [(i+1)//2]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
    print(d[N-1][N//2])
else:
    d = defaultdict(lambda:defaultdict(lambda:-float('inf')))
    d[0][1] = A[0]
    d[1][1] = max(A[0],A[1])
    for i in range(2,N):
        if i%2 == 0:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
        else:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
    a1 = d[N-1][N//2]
    n = 0
    for i in range(2,N,2):
        n += A[i]
    print(max(n,a1))

Submission status: Accepted

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

dp=[[0]*(N+1) for i in range(3)]

dp[0][1]=-float("inf")
dp[2][1]=A[1]
dp[0][2]=0
dp[1][2]=max(A[1],A[2])
dp[2][2]=-float("inf")

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

print(dp[1][N])

Submission status: Accepted

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

if N % 2 == 0:#Nが偶数
  inf = float("inf")
  DP = [[-inf for i in range(2)] for i in range(N)]
  #print(DP)
  DP[0][0] = A[0]
  DP[1][1] = A[1]
  for i in range(2, N):
    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 - 2][0], DP[N - 1][1]))
  
else:#Nが奇数         
  #print(N)
  inf = float("inf")
  DP = [[-inf for i in range(3)] for i in range(N)]
  #print(DP)
  DP[0][0] = A[0]
  DP[1][1] = A[1]
  DP[2][2] = A[2]
  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 - 2][1], DP[i - 3][0]) + A[i]
    DP[i][2] = max(DP[i - 2][2], DP[i - 3][1]) + A[i]
  print(max(DP[N - 2][1], DP[N - 1][2]))

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

#処理内容
def main():
	N = int(input())
	A = getlist()
	A += [-INF] * 10
	if N % 2 == 0:
		DP0 = [-INF] * (N + 10)
		DP1 = [-INF] * (N + 10)
		DP0[0] = A[0]
		DP1[1] = A[1]
		for i in range(N):
			DP0[i + 2] = max(DP0[i] + A[i + 2] , DP0[i + 2])
			DP1[i + 3] = max(DP0[i] + A[i + 3] , DP1[i + 3])

			DP1[i + 2] = max(DP1[i] + A[i + 2] , DP1[i + 2])

		ans = max(DP0[N - 2], DP1[N - 1])

		print(ans)


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

			DP1[i + 2] = max(DP1[i] + A[i + 2] , DP1[i + 2])
			DP2[i + 3] = max(DP1[i] + A[i + 3] , DP2[i + 3])
			
			DP2[i + 2] = max(DP2[i] + A[i + 2] , DP2[i + 2])

		ans = max(DP0[N - 3], DP1[N - 2], DP2[N - 1])

		print(ans)



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 < 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()))
a0 = [0] * (n//2+1)
a1 = [0] * (n//2+1)
for i in range(n//2):
    a0[i+1] = a0[i] + a[i*2]
if n% 2 != 0:
    a0.append(a0[-1] + a[-1])

max_even = [0] * (n//2+1)
for i in range(n//2):
    max_even[i+1] = max(max_even[i]+a[2*i+1], a0[i+1])

ans = -1e9*n
if n%2 == 0:
    ans = max_even[-1]
else:
    for i in range(0,n//2+1):
        ans = max(ans, max_even[i] + a0[-1] - a0[i+1])
print(ans)

Submission status: Accepted

Solution code:
#!python3

INF = -(10 ** 17)

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


def main():
    if N % 2 == 0:
        dp = [[INF] * 2 for _ in range(N)]
        dp[0][0] = A[0]
        dp[1][1] = A[1]
        for i in range(2, N):
            dp[i][0] = dp[i - 2][0] + A[i]
            if i > 2:
                dp[i][1] = max(dp[i - 2][1] + A[i], dp[i - 3][0] + A[i])
        
        ans = max(dp[-1][1], dp[-2][0])
        print(ans)
    else:
        dp = [[INF] * 3 for _ 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]
        for i in range(3, N):
            dp[i][0] = dp[i - 2][0] + A[i]
            dp[i][1] = max(dp[i - 2][1] + A[i], dp[i - 3][0] + A[i])
            if i > 3:
                a = dp[i - 2][2] + A[i]
                b = dp[i - 3][1] + A[i]
                c = dp[i - 4][0] + A[i]
                dp[i][2] = max(a, b, c)
        
        ans = max(dp[-1][2], dp[-2][1], dp[-3][0])
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    A = read_list()
    dp = [[-10 ** 20 for _ in range(2)] for _ in range(N // 2 + 5)] 

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    A=list(map(int,input().split()))
    if n==3 or n==2:
        return max(A)
    DP=[[None]*3 for _ 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]=max(A[0],A[1])+A[3]
    #print(DP)
    for i in range(4,n):
        a=A[i]
        if i%2==0:
            DP[i][0]=DP[i-2][0]+a
            DP[i][2]=max(DP[i-2][2]+a,DP[i-3][1]+a,DP[i-4][0]+a)
        if i%2!=0:
            DP[i][1]=max(DP[i-2][1]+a,DP[i-3][0]+a)
    if n%2==1:
        ans=max(DP[-1][2],DP[-2][1],DP[-3][0])
        return ans
    ans=max(DP[-1][1],DP[-2][0])
    return ans
    
if __name__=='__main__':
    print(main())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
if n % 2 == 0:
  b = []
  for i in range(n//2):
    ans += a[2*i]
    b.append(a[2*i+1] - a[2*i])
  #print(b)
  for i in range(1,n//2)[::-1]:
    b[i-1] += b[i]
  #print(b)
  b.append(0)
  print(ans + max(b))
else:
  b = []
  c = []
  for i in range(n//2):
    ans += a[2*i]
    b.append(a[2*i+1] - a[2*i])
    c.append(a[2*i+2] - a[2*i+1])
  for i in range(1,n//2)[::-1]:
    b[i-1] += b[i]
    c[i-1] += c[i]
  #print(b)
  #print(c)
  d = c[:]
  d[-1] = max(d[-1],0)
  for i in range(1,n//2)[::-1]:
    d[i-1] = max(d[i-1],d[i],0)
  #print(d)
  e = []
  for i in range(n//2):
    e.append(b[i]+d[i])
  #print(ans)
  e.append(0)
  print(ans + max(e))