Problem:


Score : 600 points

Problem Statement

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

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

Find the maximum possible sum of the chosen elements.

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

Constraints

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

|A_i|\leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the maximum possible sum of the chosen elements.

Sample Input 1

6
1 2 3 4 5 6

Sample Output 1

12

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

Sample Input 2

5
-1000 -100 -10 0 10

Sample Output 2

0

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

Sample Input 3

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5000000000

Watch out for overflow.

Sample Input 4

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

Sample Output 4

295



Sample input:
6
1 2 3 4 5 6


Sample output:
12

Submission status: Accepted

Solution code:
N = int(input())

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

S = [0]*N
S[0] = A[0]
S[1] = A[1]

for i in range(2,N):
    S[i] = S[i-2] + A[i]

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

else:
    M = A[0]
    for i in range(1,N//2+1):
        M = min(M,A[2*i])

    mss = - M
    s = - A[0]
    for i in range(N//2):
        s += A[2*i+1] - A[2*i+2]
        if s < 0:
            s = - A[2*i+2]
        elif mss < s:
            mss = s
        #print(i,mss)
    
    mss2 = - M
    t = - A[-1]
    for i in range(1,N//2+1):
        t += A[-2*i] - A[-2*i-1]
        if t < 0:
            t = - A[-2*i-1]
        elif mss2 < t:
            mss2 = t
    
    p = S[-2]
    for i in range(1,N):
        if i % 2 == 1:
            p = max(p,S[i]+S[-1]-S[i+1])
    
    print(max(S[-1]+mss,S[-1]+mss2,p))

###
#print(S)
#print(M)
###

Submission status: Accepted

Solution code:
n = int(input())
a = [int(c) for c in input().split()]
m = 0
t0 = [-1]*n # 最初使える、i以降
t1 = [-1]*n # 使えない
t2 = [-1]*n # 使わないといけない
t0[-1] = a[-1]
t1[-1] = 0
t2[-1] = a[-1]
tmp = 0
for i in range(-1, -n-1, -2):
    tmp += a[i]
    t2[i] = tmp
tmp = 0
for i in range(-2, -n-1, -2):
    tmp += a[i]
    t2[i] = tmp

    
for i in range(-2, -n-1, -1):
    if i%2==0:
        m= a[i]+t1[i+1]
        m = max(m, t2[i+1])
        t0[i] = m
        t1[i] = t0[i+1]
#         t2[i] = a[i] + t1[i+1]
    else:
        m= a[i]+t1[i+1]
        m = max(m, t0[i+1])
        t0[i] = m
        t1[i] = t0[i+1]
#         t2[i] = a[i] + t1[i+1]
        
print(t0[0])

Submission status: Accepted

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

if N%2==0:
    S = [0]*N
    s = 0
    for i in range(0, N, 2):
        s += A[i]
        S[i] = s

    ans = s = sum(A[1:N:2])
    for t in range(1, N, 2):
        s -= A[t]
        ans = max(ans, S[t-1]+s)
    print(ans)

else:
    S = [0]*N
    s = 0
    p = 0
    for t in range(2, N, 2):
        p += A[t-2]
        S[t] = max(S[t-2]+A[t-1], p)
    
    ans = s = sum(A[2:N:2])
    for t in range(2, N, 2):
        s -= A[t]
        ans = max(ans, S[t]+s)
    print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate,chain
from itertools import combinations

from random import randrange


def solve(A):
    N = len(A)
    oddacc = tuple(chain((0,),accumulate(A[1::2])))
    evenacc = tuple(chain((0,),accumulate(A[::2])))
    if N%2==0:
        return max(evenacc[i]+oddacc[-1]-oddacc[i] for i in range(N//2+1))

    # one 3 space
    res = max(evenacc[-1]-A[i*2] for i in range(N//2+1))
    # two 2 space
    def it():
        m = 0

        for i in reversed(range(N//2)):
            m = max(m+A[i*2+1], A[i*2+1]+evenacc[-1]-evenacc[i+2])
            yield m+evenacc[i]
    res = max(max(it()), res)
    return res

def naive(A):
    def it():
        for indices in combinations(range(len(A)), r=len(A)//2):
            if all(i+1!=j for i,j in zip(indices,indices[1:])):
                yield (sum(A[i] for i in indices), indices)

    return max(it())

if __name__ == '__main__':
    N = map(int,input().split())
    A = tuple(map(int,input().split()))
    print(solve(A))


    # for _ in range(10000):
    #     A = [randrange(1000)-500 for _ in range(6)]

    #     a = solve(A)
    #     b,ind = naive(A)
    #     if a!=b:
    #         print(ind)
    #         print(A)
    #         print(a,b)
    #         break

Submission status: Accepted

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

dp = [[0] * 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:2])
for i in range(2, N-1):
    if i%2 == 0:
        dp[i][0] = max(dp[i-1][1], dp[i-2][0] + A[i])
        dp[i][1] = dp[i-2][1] + A[i]
    else:
        dp[i][0] = max(dp[i-1][0], dp[i-2][0] + A[i])
        dp[i][1] = max(dp[i-1][1], dp[i-2][1] + A[i])
#print(dp)

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

Submission status: Accepted

Solution code:

N = int(input())

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

if N % 2 == 0:

    e = 0
    o = 0
    

    for i in range(N):

        if i % 2 == 0:
            e += A[i]
        else:
            o += A[i]

    el = [0]
    ol = [0]

    for i in range(N):

        if i % 2 == 0:
            el.append(el[-1] + A[i])
        else:
            ol.append(ol[-1] + A[i])

    eri = [0]
    ori = [0]

    for i in range(N-1,-1,-1):

        if i % 2 == 0:
            eri.append(eri[-1] + A[i])
        else:
            ori.append(ori[-1] + A[i])

    ans = max(e,o)


    for i in range(N//2+1):
        ans = max(ans,el[i]+ori[N//2-i])
    print (ans)

else:

    el = [0]
    ol = [0]

    for i in range(N):

        if i % 2 == 0:
            el.append(el[-1] + A[i])
        else:
            ol.append(ol[-1] + A[i])

    eri = [0]
    ori = [0]

    for i in range(N-1,-1,-1):

        if i % 2 == 0:
            eri.append(eri[-1] + A[i])
        else:
            ori.append(ori[-1] + A[i])

    ans = float("-inf")



    LS = [0]
    LSM = [0]
    for i in range(0,N-1,2):

        LS.append(LS[-1] + A[i] - A[i+1])
        LSM.append(max(LSM[-1],LS[-1]))

    RS = [0]
    RSM = [0]
    for i in range(N-1,0,-2):

        RS.append(RS[-1] + A[i] - A[i-1])
        RSM.append(max(RSM[-1],RS[-1]))

    EOE = float("-inf")
    for i in range(N//2+1):
        EOE = max(EOE , LSM[i] + RSM[N//2-i])

    
    for i in range(N):

        if i <= N//2:

            ans = max(ans , el[i]+ori[N//2-i] , ol[i]+eri[N//2-i] , el[i]+eri[N//2-i] , ol[-1] + EOE)

    print (ans)

Submission status: Accepted

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

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

ans = -float("inf")
if n % 2 == 0:
    D = [[0,0] for i in range(n//2)]
    D[0][0] = A[0]
    D[0][1] = A[1]
    for i in range(1, n//2):
        D[i][0] = D[i-1][0] + A[i*2]
        D[i][1] = max(D[i-1][0],D[i-1][1]) + A[i*2+1]
    print(max(D[-1]))

else:

    

    D = [[0,0] for i in range(n//2)]
    D[0][0] = A[0]
    D[0][1] = A[1]
    for i in range(1, n//2):
        D[i][0] = D[i-1][0] + A[i*2]
        D[i][1] = max(D[i-1][0],D[i-1][1]) + A[i*2+1]


    S = [0] * n
    S[0] = A[0]
    S[1] = A[1]
    for i in range(2, n):
        S[i] = A[i] + S[i-2]

    # print(S)
    

    for i in range(0, n, 2):
        le = max(D[i//2-1]) if i>0 else 0
        ri = S[-1] - S[i]
        # print(i,le,ri, le+ri)
        ans = max(ans, le+ri)

    A = A[::-1]

    D = [[0,0] for i in range(n//2)]
    D[0][0] = A[0]
    D[0][1] = A[1]
    for i in range(1, n//2):
        D[i][0] = D[i-1][0] + A[i*2]
        D[i][1] = max(D[i-1][0],D[i-1][1]) + A[i*2+1]
    # print(D[-1])

    S = [0] * n
    S[0] = A[0]
    S[1] = A[1]
    for i in range(2, n):
        S[i] = A[i] + S[i-2]
    

    for i in range(0, n, 2):
        le = max(D[i//2-1]) if i>0 else 0
        ri = S[-1] - S[i]
        # print(i,le,ri, le+ri)
        ans = max(ans, le+ri)

    print(ans)

Submission status: Accepted

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

if N % 2 == 0:
    dp = [[(-1)*10**15]*2 for _ in range(N)]
    dp[0][0] = A[0]
    dp[0][1] = 0
    dp[1][0] = A[0] + A[1]
    dp[1][1] = max(A[0], A[1])
    for i in range(N-2):
        dp[i+2][0] = max(dp[i+2][0], dp[i][0] + A[i+2])
        dp[i+2][1] = max(dp[i+2][1], dp[i][1] + A[i+2])
        dp[i+1][1] = max(dp[i+1][1], dp[i][0])
    dp[N-1][1] = max(dp[N-1][1], dp[N-2][0])
    print(dp[N-1][1])
else:
    dp = [[(-1)*10**15]*3 for _ in range(N)]
    dp[0][0] = A[0]
    dp[0][1] = 0
    dp[0][2] = 0
    dp[1][0] = A[0] + A[1]
    dp[1][1] = max(A[0], A[1])
    dp[1][2] = 0
    for i in range(N-2):
        dp[i+2][0] = max(dp[i+2][0], dp[i][0] + A[i+2])
        dp[i+2][1] = max(dp[i+2][1], dp[i][1] + A[i+2])
        dp[i+1][1] = max(dp[i+1][1], dp[i][0])
        dp[i+1][2] = max(dp[i+1][2], dp[i][1])
        dp[i+2][2] = max(dp[i+2][2], dp[i][2] + A[i+2], dp[i][0])
    dp[N-1][1] = max(dp[N-1][1], dp[N-2][0])
    dp[N-1][2] = max(dp[N-1][2], dp[N-2][1])
    print(dp[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()]

#dp[i][done][extra]
if N % 2 == 0 :
  extra = 2
else :
  extra = 3
  
N += 1
A = A + [-float('inf')]
  
dp = [[[-float('inf')] * extra for _ in range(2)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N) :
  a = A[i]
  for j in range(2) :
    for k in range(extra) :
      # 取る場合
      if j == 0 :
        dp[i+1][1][k] = max(dp[i+1][1][k], dp[i][j][k] + a)
      # 取らない場合
      if j == 1 :
        dp[i+1][0][k] = max(dp[i+1][0][k], dp[i][j][k])
      if j == 0 and k != extra - 1 :
        dp[i+1][0][k + 1] = max(dp[i+1][0][k + 1], dp[i][j][k])

# for dp_ in dp :
  # print(dp_)

print(max(dp[-1][0][-1], dp[-1][1][-1]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))

answer = [max(A[0],A[1])]

list_sum = A[::2]
for i in range(1,len(list_sum)):
  list_sum[i] += list_sum[i-1]

for i in range(2,N):
  if i==2:
    answer.append(max(A[0],A[1],A[2]))
  elif i%2==0:
    answer.append(max(answer[-1], answer[-2]+A[i]))
  else:
    answer.append(max(answer[-2]+A[i], list_sum[(i-1)//2]))

print(answer[-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:
#!/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]
            dp[i+1][1] = max(dp[i-1])+A[i]
        else:
            dp[i+1][1] = max(dp[i-1])+A[i]
            dp[i+1][0] = dp[i][1]

    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 solve(n, a_list):
    if n % 2 == 0:
        res_a = [0] * (n // 2 + 1)
        res_b = [0] * (n // 2 + 1)
        for i in range(0, n // 2):
            res_a[i + 1] = res_a[i] + a_list[i * 2]
        for i in range(n // 2 - 1, -1, -1):
            res_b[i] = res_b[i + 1] + a_list[i * 2 + 1]
        return max([res_a[i] + res_b[i] for i in range(n // 2 + 1)])
    else:
        # type a
        dp = [[0] * 3 for _ in range(n)]
        dp[0][0] = a_list[0]
        dp[1][1] = a_list[1]
        dp[2][2] = a_list[2]
        for i in range(n):
            if i % 2 == 0:
                if i >= 2:
                    dp[i][0] = dp[i - 2][0] + a_list[i]
                    dp[i][1] = dp[i - 1][1]
                if i >= 3:
                    dp[i][2] = max(dp[i - 3][1] + a_list[i], dp[i - 2][2] + a_list[i])
            else:
                if i >= 3:
                    dp[i][1] = max(dp[i - 2][1] + a_list[i], dp[i - 3][0] + a_list[i])
                dp[i][0] = dp[i - 1][0]
                dp[i][2] = dp[i - 1][2]
        res_a = max(dp[-1])
        # print(dp)

        # type b
        even = [a_list[i] for i in range(0, n, 2)]
        res_b = sum(even) - min(even)

        return max(res_a, res_b)


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(6, [1, 2, 3, 4, 5, 6]) == 12
    assert solve(5, [-1000, -100, -10, 0, 10]) == 0
    assert solve(10, [1000000000] * 10) == 5000000000


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n = n_in()

A = l_in()

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




if n%2 == 0:
    res = sum(A[::2])
    dp = [[0,0] for _ in range(n)]
    #dp[i][k]は k回スキップして，i番目を使う確定した時の最大

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

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

    print(max(res, dp[n-1][1]))
    exit()

res = sum(A[::2])-A[-1]
dp = [[0,0] for _ in range(n)]
#dp[i][k]は k回スキップして，i番目を使う確定した時の最大

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

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

#print(dp)    
res = max(res, dp[n-2][1])

dp = [[0,0,0] for _ in range(n)]
#dp[i][k]は k回スキップして，i番目を使う確定した時の最大

dp[0][0] = A[0]
dp[1][1] = A[1]
dp[2][2] = A[2]
dp[2][0] = A[0]+A[2]
dp[3][1] = max(A[0],A[1])+A[3]

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

#print(dp)    
print(max(res, dp[n-1][2]))

Submission status: Accepted

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

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

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

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

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import os

import itertools
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def test(N, A):
    ret = -INF
    for choices in itertools.combinations(range(N), N // 2):
        ok = True
        for i, j in zip(choices, choices[1:]):
            if abs(i - j) == 1:
                ok = False
                break
        if ok:
            s = 0
            for i in choices:
                s += A[i]
            ret = max(ret, s)
    print(ret)


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
N = len(A)

cnt = 2 if N % 2 == 1 else 1
# dp[i][j]: iまでみて、j個とばしたときの総和の最大値
dp = [[-INF] * (cnt + 1) for _ in range(N + 2)]
for i in range(cnt + 1):
    dp[i][i] = 0
for i in range(N):
    for j in range(cnt + 1):
        for k in range(cnt + 1):
            if i + 2 + k < len(dp) and j + k < len(dp[0]):
                dp[i + 2 + k][j + k] = max(dp[i + 2 + k][j + k], dp[i][j] + A[i])
print(dp[-1][-1])

# test(N, A)

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:
import numpy as np

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


A = np.array([0, 0] + A)

cum_0 = A[::2].cumsum()
cum_1 = A[1::2].cumsum()


ans = -float("inf")

if N % 2:
    cum_10 = cum_1.copy()
    cum_10 -= cum_0[1:]
    cum_01 = cum_0[:-1].copy()
    cum_01 -= cum_1

    cum_max_01 = np.zeros_like(cum_01)
    for i in range(1, len(cum_max_01)):
        cum_max_01[i] = max(cum_max_01[i - 1], cum_01[i])

    ans = (cum_max_01 + cum_10).max()
    ans += cum_0[-1]
else:
    for i in range(0, N // 2 + 1):
        tmp = cum_0[i] + (cum_1[-1] - cum_1[i])
        ans = max(ans, tmp)
print(ans)

pass

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9
inf = 10**20


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))
    if N == 2 or N == 3:
        print(max(A))
        exit()

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

if n % 2 == 0:
    b = [0] * n
    for i in range(n):
        if i // 2 == 0:
            b[i] = a[i]
        else:
            if i % 2 == 0:
                b[i] = b[i - 2] + a[i]
            else:
                b[i] = max(b[i - 3], b[i - 2]) + a[i]
    print(max(b[-1], b[-2]))
else:
    b = []
    for i in range(2):
        temp = [0] * n
        b.append(temp)
    for i in range(n):
        if i // 2 == 0:
            b[0][i] = a[i]
        else:
            if i % 2 == 1:
                b[0][i] = max(b[0][i - 3], b[0][i - 2]) + a[i]
            else:
                b[0][i] = b[0][i - 2] + a[i]
                if i == 2:
                    b[1][i] = b[1][i - 2] + a[i]
                else:
                    b[1][i] = max(b[0][i - 4], b[0][i - 3], b[1][i - 2]) + a[i]
    print(max(b[1][-1], b[0][-2], b[0][-3]))

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	n = int(input())
	al = list(IN())
	if n == 2 or n == 3:
		return max(al)
	
	if n % 2 == 0:
		cc = [[0]*n,[0]*n]
		cc[0][0]=al[0]
		cc[1][1]=al[1]
		for i in range(2,n):
			if i%2==0:
				cc[0][i]=cc[0][i-2]+al[i]
			else:
				cc[1][i]=max(cc[1][i-2],cc[0][i-3])+al[i]
		return max(cc[0][-2], cc[1][-1])
		
	else:
		cc = [[0]*n,[0]*n, [0]*n]
		cc[0][0]=al[0]
		cc[1][1]=al[1]
		cc[0][2]=al[2]+al[0]
		cc[2][2]=al[2]
		for i in range(3, n):
			if i % 2 ==1:
				cc[1][i]=max(cc[1][i-2],cc[0][i-3])+al[i]
			else:
				cc[0][i]=cc[0][i-2]+al[i]
				cc[2][i]=max(cc[0][i-4],cc[1][i-3],cc[2][i-2])+al[i]
		return max(cc[0][-3],cc[1][-2],cc[2][-1])
				
	
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
al = []
g = []
k = []
g0 = 0
k0 = 0
for i in range(n):
    if i % 2 == 0:
        k0 += a[i]
        k.append(k0)
    else:
        g0 += a[i]
        g.append(g0)
if n % 2 == 0:
    al.append(g[n//2-1])
    al.append(k[n//2-1])
    for i in range(n):
        if i % 2 == 0 and i < n-2:
            now = i//2
            al.append(k[now]+g[-1]-g[now])
else:
    #print(g,k)
    al.append(g[-1])
    d = a[1]
    for i in range(n):
        if i % 2 == 0:
            al.append(k[-1]-a[i])
        else:
            now = (i-1)//2
            if i > 1 and i < n-2:
                #print(d,g[-1]-g[now],k[-1]-k[now+1],g[now-1],k[now-1],a[i])
                al.append(max(g[-1]-g[now],k[-1]-k[now+1])+max(d,k[now-1])+a[i])
                d = max(d+a[i],k[now-1]+a[i])
            elif i == 1:
                al.append(a[i]+max(g[-1]-g[now],k[-1]-k[now+1]))
                d = max(a[i],a[0])
            else:
                al.append(a[i] + max(d,k[now-1]))
#print(al)
print(max(al))

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 = 0
#     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:
INF = 10 ** 15

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

INF = 10 ** 15
dp = [[-INF] * (N//2) for _ in range(3)]
dp[0][0] = As[0]
dp[1][0] = As[1]
dp[2][0] = As[2]

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

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

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
INF = 10**18
dp_use = [-INF] * 5
dp_not_use = [-INF] * 5
dp_not_use[0] = 0

for a in A:
    tmp_use = [-INF] * 5
    tmp_not_use = [-INF] * 5
    for current_dif in range(-3,2):
        if current_dif-1 >= -3:
            tmp_use[current_dif] = dp_not_use[current_dif - 1] + a
        if current_dif+1 < 2:
            tmp_not_use[current_dif] = max(dp_use[current_dif+1], dp_not_use[current_dif+1])
    dp_use = tmp_use
    dp_not_use = tmp_not_use
dif = n//2 - (n-n//2)
print(max(dp_use[dif], dp_not_use[dif]))

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    A=list(map(int,input().split()))
    A_=[0]*n
    for i in range(n):
        if i%2==0:
            A_[i]=A[i]
        else:
            A_[i]==0
    for i in range(n-1):
        A_[i+1]+=A_[i]
    dp=[0]*n
    dp[1]=max(A[0],A[1])
    for i in range(2,n):
        if i%2==0:
            dp[i]=max(dp[i-2]+A[i],dp[i-1])
        else:
            dp[i]=max(dp[i-2]+A[i],A_[i-1])
    print(dp[n-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
if N % 2 == 0:
    NINF = -(10 ** 16)
    dp = [[NINF for j in range(2)] for i in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    for i in range(N):
        if i - 2 >= 0:
            if dp[i - 2][0] != NINF:
                dp[i][0] = dp[i - 2][0] + A[i]
            if dp[i - 2][1] != NINF:
                dp[i][1] = dp[i - 2][1] + A[i]
        if i - 3 >= 0:
            dp[i][1] = max(dp[i][1], dp[i - 3][0] + A[i])

    res = max(dp[N - 1][1], dp[N - 2][0])
else:
    NINF = -(10 ** 16)
    dp = [[NINF for j in range(3)] for i in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for i in range(N):
        if i - 2 >= 0:
            if dp[i - 2][0] != NINF:
                dp[i][0] = dp[i - 2][0] + A[i]
            if dp[i - 2][1] != NINF:
                dp[i][1] = dp[i - 2][1] + A[i]
            if dp[i - 2][2] != NINF:
                dp[i][2] = dp[i - 2][2] + A[i]
        if i - 3 >= 0:
            dp[i][1] = max(dp[i][1], dp[i - 3][0] + A[i])
            dp[i][2] = max(dp[i][2], dp[i - 3][1] + A[i])
        if i - 4 >= 0:
            dp[i][2] = max(dp[i][2], dp[i - 4][0] + A[i])

    res = max(dp[N - 1][2], dp[N - 2][1], dp[N - 3][0])

print(res)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import deque
q=deque([(-1,0,-2,0)])
ans=-10**18
for i,a in enumerate(A):
    d={}
    while q and q[0][0]<i:
        j,n,r,x=q.popleft()
        if r<-1:
            if n==N//2-1:
                ans=max(ans,x+a)
            elif n not in d:
                d[n]=x
            elif d[n]<x:
                d[n]=x
        if (j+1)//2<=n:
            q.append((i,n,r-1,x))
    for n,x in d.items():
        q.append((i,n+1,-1,x+a))
print(ans)

Submission status: Accepted

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


if n==2:
    print(max(a))
    sys.exit()

a0=[a[0],a[0]]
a1=[0,a[1]]
a2=[0,0,a[2]]
for i in range(2,n):
    if i%2==0:
        a0.append(a0[i-2]+a[i])
        a1.append(a1[i-1])
        if i>=4: a2.append(max(a2[i-2],a1[i-3],a0[i-4])+a[i])
    else:
        a0.append(a0[i-1])
        a1.append(max(a1[i-2],a0[i-3])+a[i])
        a2.append(a2[i-1])

if n%2==1: print(max(a0[n-1],a1[n-1],a2[n-1]))
else: print(max(a0[n-1],a1[n-1]))

Submission status: Accepted

Solution code:
import os

import itertools
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def test(N, A):
    ret = -INF
    for choices in itertools.combinations(range(N), N // 2):
        ok = True
        for i, j in zip(choices, choices[1:]):
            if abs(i - j) == 1:
                ok = False
                break
        if ok:
            s = 0
            for i in choices:
                s += A[i]
            ret = max(ret, s)
    print(ret)


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
N = len(A)

if N % 2 == 0:
    cum0 = list(itertools.accumulate([0] + A[::2]))
    cum1 = list(itertools.accumulate([0] + A[1::2]))
    ans = -INF
    for i in range(len(cum0)):
        s = cum1[-1] - cum1[i] + cum0[i]
        ans = max(s, ans)
    print(ans)
    exit()

cnt = 2 if N % 2 == 1 else 1
# dp[i][j]: iまでみて、j個とばしたときの総和の最大値
dp = [[-INF] * (cnt + 1) for _ in range(N + 2)]
for i in range(cnt + 1):
    dp[i][i] = 0
for i in range(N):
    for j in range(cnt + 1):
        for k in range(cnt + 1):
            if i + 2 + k < len(dp) and j + k < len(dp[0]):
                dp[i + 2 + k][j + k] = max(dp[i + 2 + k][j + k], dp[i][j] + A[i])
print(dp[-1][-1])

# test(N, A)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline
    from collections import Counter

    import random

    n = int(input())
    aa = list(map(int, input().split()))
    if n%2 == 0:
        dp = [[0]*n for _ in range(2)]
        dp[0][0] = aa[0]
        dp[1][1] = aa[1] if aa[1]>aa[0] else aa[0]
        for i in range(2, n, 2):
            aa_i = aa[i]
            dp[0][i] = dp[0][i-2]+ aa_i

            aa_i_p_1 = aa[i+1]
            dp_i_1 = dp[1][i-1]
            next = (dp_i_1+aa_i_p_1) if (dp_i_1+aa_i_p_1 > dp[0][i]) else dp[0][i]
            dp[1][i+1] = next
        print(dp[1][n-1])

    else:
        dp = [[0]*n for _ in range(3)]
        dp[0][0] = aa[0]
        dp[1][1] = aa[1] if aa[1]>aa[0] else aa[0]
        for i in range(2, n, 2):
            aa_i = aa[i]
            dp[0][i] = dp[0][i-2]+ aa_i
            dp_i_2 = dp[2][i-2]
            dp[2][i] = dp_i_2+aa_i if dp_i_2+aa_i > dp[1][i-1] else dp[1][i-1]

            if i == n-1:
                break
            aa_i_p_1 = aa[i+1]
            dp_i_1 = dp[1][i-1]
            dp[1][i+1] = dp_i_1+aa_i_p_1 if dp_i_1+aa_i_p_1 > dp[0][i] else dp[0][i]
        print(dp[2][n-1])

Submission status: Accepted

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

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

left = [0] * (n+1)
right = [0] * (n+1)

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

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

ans = left[-1]
for i in range(0,n-1 ):
    ans = max(ans, left[i] + right[i+2])

if(n%2==0):
    print(left[-1])
else:
    print(ans)