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: Wrong Answer

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

odd = sum(A[::2])
eve = sum(A[1::2])


if N % 2 == 0:
    print(max(odd, eve))
else:
    res = -float('inf')
    odd_l = 0
    eve_l = 0
    odd_r = odd - A[0]
    eve_r = eve - A[1]

    for i in range(N-1):
        if i % 2 == 0:
            tmp = eve_l + odd_r
        else:
            tmp = odd_l + eve_r
        res = max(res, tmp)

        if i < N-2:
            if i % 2 == 0:
                odd_l += A[i]
                odd_r -= A[i+2]
            else:
                eve_l += A[i]
                eve_r -= A[i+2]

    if N >= 5:
        for i in range((N-1)//2-1):
            tmp = odd - A[i*2+2]
            res = max(res, tmp)

    res = max(res, eve)

    print(res)

Submission status: Wrong Answer

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

odd_l = [0]
odd_l_tmp = 0
for i in range(N):
    if i % 2 == 0:
        odd_l_tmp += A[i]
        odd_l.append(odd_l_tmp)

odd_r = [0]
odd_r_tmp = 0
for i_inv in range(N):
    i = N - 1 - i_inv
    if i % 2 == 0:
        odd_r_tmp += A[i]
        odd_r.append(odd_r_tmp)

evn_l = [0]
evn_l_tmp = 0
for i in range(N):
    if i % 2 == 1:
        evn_l_tmp += A[i]
        evn_l.append(evn_l_tmp)
        
evn_r = [0]
evn_r_tmp = 0
for i_inv in range(N):
    i = N - 1 - i_inv
    if i % 2 == 1:
        evn_r_tmp += A[i]
        evn_r.append(evn_r_tmp)

ans = 0

# mixed
for i in range(1, N // 2):
    ans_tmp = odd_l[i] + evn_r[N // 2 - i]
    # print("# mix(OE)", i, odd_l[i], evn_r[N // 2 - 1 - i], ans_tmp)
    ans = max(ans, ans_tmp)
    if N % 2 > 0:
        ans_tmp = evn_l[i] + odd_r[N // 2 - i]
        # print("# mix(EO)", i, evn_l[i], odd_r[N // 2 - 1 - i], ans_tmp)
        ans = max(ans, ans_tmp)

# odd only
if N % 2 > 0:
    sum_tmp = odd_l[-1]
    for i in range(N):
        if i % 2 == 0:
            ans_tmp = sum_tmp - A[i]
            # print("# odd (sep)", i, sum_tmp, A[i], ans_tmp)
            ans = max(ans, ans_tmp)
else:
    ans_tmp = odd_r[-1]
    # print("# odd", ans_tmp)
    ans = max(ans, ans_tmp)
    

# evn only
ans_tmp = evn_r[-1]
# print("# evn", ans_tmp)
ans = max(ans, ans_tmp)

print(ans)

Submission status: Wrong Answer

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

B,C = [0],[0]
for i in range(N):
    if i%2==0:B.append(B[i//2]+A[i])
    else:C.append(C[i//2]+A[i])

if N%2==0:
    print(max(B[-1],C[-1]))
else:
    inf = float("inf")
    DP = [[-inf]*(N+1) for i in range(3)]
    A = [0]+A
    for i in range(1,N+1):
        if i%2==1:
            if i==1:DP[0][i] = A[i]
            else:DP[0][i] = DP[0][i-2]+A[i]
        if i>1:
            if i==2:DP[1][i] = A[i]
            else:DP[1][i] = max(DP[1][i-2],DP[0][i-3])+A[i]
        if i>2:
            if i==3:DP[2][i] = A[i]
            else:DP[2][i] = max(DP[2][i-2],DP[1][i-3],DP[0][i-4])+A[i]
    print(max(DP[0][N],DP[1][N-1],DP[2][N]))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = -float('inf')
b = 0
for i in range(0,N,2):
    b += A[i]
ans = max(ans,b)
b = 0
for i in range(1,N,2):
    b += A[i]
ans = max(ans,b)
print(ans)

Submission status: Wrong Answer

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

sm1 = []
sm2 = []
tmp1 = 0
tmp2 = 0
for i in range(n):
    if i % 2 == 0:
        tmp1 += a[i]
        sm1.append(tmp1)
    else:
        tmp2 += a[i]
        sm2.append(tmp2)

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

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

for i in range(len(sm2)):
    if i >= len(sm1)-2:
        continue
    ans = max(ans, sm2[i] + sm1[-1] - sm1[i+1])

for i in range(len(sm2)):
    ans = max(ans, sm1[i] + sm2[-1] - sm2[i])
        

# 111222111 pattern
if n%2 != 0 and n>=7:
    switch_better = [False]*len(sm2)

    for i in range(len(sm2)):
        switch_better[i] = sm1[i]-sm2[i]

    tmp = 0
    val = switch_better[0]

    for i in range(len(sm2)):
        if i >= len(sm2)-2:
            continue
        ans = max(ans, sm2[i] + sm1[-1] - sm1[i+1])
        
        if val < switch_better[i]:
            tmp = i
            val = switch_better[i]
        
        ans = max(ans, sm2[i]+sm1[-1]-sm1[i+1]-sm2[tmp]+sm1[tmp])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def main():
    N = int(input())
    A = list(map(int, input().split()))
    values = [[] for _ in range(2)]
    for i, val in enumerate(A):
        values[i%2].append(val)
    
    if N%2==0:
        print(max( sum(values[0]), sum(values[1]) ))
    else:

        if N == 3:
            max(A)
            exit()
        left = sum(values[0]) - values[0][N//2] - values[0][N//2-1] + max(A[2*(N//2-1):])
        right = sum(values[0]) - values[0][1] - values[0][0] + max(A[:3])
        
        if N == 5:
            print(max(left, right))
            exit()

        center = 0
        for i in range(1, N//2-1):
            center = max(center, sum(values[0]) - sum(values[0][i:i+2]) + max(A[2*i:2*i+3]))
        print(max(left, center, right))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
seisuretu =  sorted(list(map(int,input().split())), reverse = True)
print(seisuretu)
goukei = 0
for i in range(int(N/2)):
    goukei += seisuretu[2*i]

print(goukei)

Submission status: Wrong Answer

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[0]
dp[0][2]=0
dp[1][2]=max(A[0],A[1])
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: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

n = INT()
a = LIST()
s = sum(a)
debug('s', s)
if n % 2 == 1:
    arr1 = [0 for _ in range(n)]
    arr2 = [0 for _ in range(n)]
    arr1[0] = a[0]
    for i in range(1, n):
        if i % 2 == 0:
            arr1[i] = arr1[i - 1] + a[i]
            arr2[i] = arr2[i - 1]
        else:
            arr1[i] = arr1[i - 1]
            arr2[i] = arr2[i - 1] + a[i]
    arr3 = [0 for _ in range(n)]
    arr4 = [0 for _ in range(n)]
    arr3[-1] = a[-1]
    for i in reversed(range(n - 1)):
        if i % 2 == 0:
            arr3[i] = arr3[i + 1] + a[i]
            arr4[i] = arr4[i + 1]
        else:
            arr3[i] = arr3[i + 1]
            arr4[i] = arr4[i + 1] + a[i]
    debug(arr1)
    debug(arr2)
    debug(arr3)
    debug(arr4)
    ans = max(arr1[-1] - arr1[0], arr1[-3], arr2[-1])
    debug(ans)
    #ans = -inf
    for i in range(n - 3): #i番目を取る
        debug(arr1[i] + arr4[i + 3], arr1[i], arr4[i + 3])
        if i % 2 == 0:
            ans = max(ans, arr1[i] + arr4[i + 3])
            if i + 4 < n:
                ans = max(ans, arr1[i] + arr4[i + 4])
        else:
            ans = max(ans, arr2[i] + arr3[i + 3])
    #ans = max(ans, arr2[-1] - arr2[0])
    print(ans)
    
else:
    ans1 = 0
    for i in range(0, n, 2):
        ans1 += a[i]
    ans2 = s - ans1
    print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
if n%2==0:
    print(max(sum(l[::2]),sum(l[1::2])))
    exit()
rrec,rec=0,0
rrc,rc=0,0
z,q=[0]*n,[0]*n
rl=[0]*n
ll=[0]*n
for i in range(n):
    if (i%2):rec+=l[i]
    else:rc+=l[i]
    if (n-1-i)%2:rrec+=l[n-1-i]
    else:rrc+=l[n-1-i]
    rl[n-1-i]=max(rrec,rrc)
    z[n-1-i]=rrec;q[n-1-i]=rrc
    ll[i]=max(rec,rc)
ans=max(z[0],q[0]-l[0])
for i in range(n):
    if i==0:continue
    elif i==n-1:
        ans=max(ans,z[0],q[0]-l[0])
    else:
        ans=max(ans,ll[i-1]+rl[i+1])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = list(map(int,input().split()))
if n % 2 == 0:
  print(max(sum(lis[::2]),sum(lis[1::2])))
  exit()
if n == 3:
  print(max(lis))
  exit()
ans = sum(lis[1::2])
left = 0

right = sum(lis[1::2])
ans = max(ans,sum(lis[::2])-min(lis[0],lis[-1]))
for i in range(n//2):
  right -= lis[2 * i + 1]
  left += lis[2 * i]
  ans = max(ans,right + left)
left = sum(lis[1::2])
right = 0
for i in range(n//2):
  right += lis[-(2*i+1)]
  left -= lis[-(2 * i +2)]
  ans = max(ans,right + left)
print(ans)

Submission status: Wrong Answer

Solution code:
def examA():
    N = SI()
    ans = "No"
    for s in N:
        if s=="7":
            ans = "Yes"
    print(ans)
    return

def examB():
    N = I()
    ans = 0
    for i in range(1,N+1):
        if i%3==0:
            continue
        if i%5==0:
            continue
        ans += i
    print(ans)
    return

def examC():
    def gcd(x, y):
        if y == 0:
            return x
        while (y != 0):
            x, y = y, x % y
        return x
    K = I()
    ans = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            cur = gcd(i,j)
            for k in range(1,K+1):
                ans += gcd(cur,k)
    print(ans)
    return

def examD():
    N = I()
    S = SI()
    R = [0]*(N+1)
    G = [0]*(N+1)
    B = [0]*(N+1)
    for i in range(N):
        s = S[i]
        R[i+1] += R[i]
        G[i+1] += G[i]
        B[i+1] += B[i]
        if s=="R":
            R[i+1] += 1
        elif s=="G":
            G[i+1] += 1
        elif s=="B":
            B[i+1] += 1
    ans = 0
    for l in range(N):
        Ls = S[l]
        for r in range(l+3,N):
            Rs = S[r]
            if (Ls=="R" and Rs=="B") or (Ls=="B" and Rs=="R"):
                ans += G[r] - G[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="G":
                        ans -= 1
            elif (Ls=="R" and Rs=="G") or (Ls=="G" and Rs=="R"):
                ans += B[r] - B[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="B":
                        ans -= 1
            elif (Ls=="G" and Rs=="B") or (Ls=="B" and Rs=="G"):
                ans += R[r] - R[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="R":
                        ans -= 1
    print(ans)
    return

def examE():
    N, K = LI()

    ans = 0
    print(ans)
    return

def examF():
    N = I()
    A = LI()

    if N%2==0:
        O = [0] * N
        E = [0] * N
        for i in range(N):
            O[i] += O[i - 1]
            E[i] += E[i - 1]
            if i % 2 == 0:
                O[i] += A[i]
            else:
                E[i] += A[i]
        #print(O,E)
        ans = max(O[-1],E[-1])
        print(ans)
        return

    def dfs(n,k):
        if (n+2)//2 <k:
            return -inf
        if k == 0:
            return 0
        if n==0:
            if k==1:
                return A[0]
            return -inf
        if n==1:
            if k==1:
                return max(A[0],A[1])
            return -inf
        res = max(A[n]+dfs(n-2,k-1),dfs(n-1,k))
        return res

    ans = dfs(N-1,N//2)
    #print(dfs(4,2))
    print(ans)
    return

def examF2():
    N = I()
    A = LI()
    if N%2==0:
        O = [0] * N
        E = [0] * N
        for i in range(N):
            O[i] += O[i - 1]
            E[i] += E[i - 1]
            if i % 2 == 0:
                O[i] += A[i]
            else:
                E[i] += A[i]
        #print(O,E)
        ans = max(O[-1],E[-1])
        print(ans)
        return

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

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF2()

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

if N == 3:
  print(max(A))
  quit()

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(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(DP[N - 1][2])

Submission status: Wrong Answer

Solution code:
N = int(input())

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
a = np.array(input().split(), dtype=np.int)

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
a.sort(reverse=True)
k=0
for i in range(n//2):
    k+=a[2*i]
print(k)

Submission status: Wrong Answer

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

    if i%2==0:
        dp[i] = max(dp[i-2]+A[i],cum)

ans = dp[-1]


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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if n % 2 == 0:
    b = a[0::2]
    c = a[1::2]
    print(max(sum(b), sum(c)))
    exit()

from itertools import accumulate
b = [a[i] if i % 2 == 0 else 0 for i in range(n)]
c = [a[i] if i % 2 else 0 for i in range(n)]
bb = list(accumulate(b))
cc = list(accumulate(c))

ans = -float('INF')
for i in range(2,n-2):
    if i % 2 == 0:
        tmp = cc[-1] - cc[i] + bb[i-2]
    else:
        tmp = bb[-1] - bb[i] + cc[i-2]
    if i % 2:
        tt = cc[-1] - cc[i] + bb[i-1]
    else:
        tt = bb[-1] - bb[i] + cc[i-1]
    if ans < max(tmp,tt):
        ans = max(tmp,tt)
print(max([ans, bb[-2], bb[-1] - bb[0], cc[-1]]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if n%2 == 0:
    sum1 = 0
    sum2 = 0
    for i in range(n):
        if i%2 == 0:
            sum1 += a[i]
        else:
            sum2 += a[i]
    print(sum1 if sum1 > sum2 else sum2)
else:
    sum1 = [a[0]]
    sum2 = [a[1]]
    sum3 = [a[2]]
    max_sum = -1e10*n
    for i in range(n//2):
        sum1.append(sum1[i]+a[2*i])
    for i in range(n//2):
        sum2.append(sum2[i]+a[2*i+1])
    for i in range(n//2):
        sum3.append(sum2[i]+a[2*(i+1)])
    space1 = 0
    space2 = 0
    for space1 in range(n//2+1):
        for space2 in range(n//2+1):
            sum4 = sum1[space1] + sum2[space2] - sum2[space1] + sum3[-1] - sum3[space2]
            if sum4 > max_sum:
                max_sum = sum4
    print(max_sum)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
if n<=3:
    print(max(arr))
    exit()
if n%2==0:
    ans=0
    tmp=0
    for i in range(0,n,2):
        tmp+=arr[i]
    ans=max(ans,tmp)
    tmp=0
    for i in range(1,n,2):
        tmp+=arr[i]
    ans=max(ans,tmp)
    acum1=[0]
    acum2=[0]
    for i in range(n):
        if i%2==0:
            acum1.append(acum1[-1]+arr[i])
            acum2.append(acum2[-1]+0)
        else:
            acum1.append(acum1[-1]+0)
            acum2.append(acum2[-1]+arr[i])
    for i in range(0,n,2):
        tmp=(acum1[i]-acum1[0])+(acum2[-1]-acum2[i])
        ans=max(ans,tmp)
    print(ans)
else:
  print('A')

Submission status: Wrong Answer

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]
    # print(c)
    for i in range(N//2):
        # print(2*i,2*i+1)
        c = max(c,c+A[2*i]-A[2*i+1])
    print(c)
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: Wrong Answer

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
    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)
print(ans)

Submission status: Wrong Answer

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

def func(As):
    if N % 2 == 0:
        sum1 = sum(As[::2])
        sum2 = sum(As[1::2])
        return max(sum1, sum2)

    else:
        ans1 = sum(As[1::2])

        accAs = [0] * N
        accAs[0] = As[0]
        accRevAs = [0] * N
        accRevAs[-1] = As[-1]
        for i in range(2, N, 2):
            accAs[i] = accAs[i-2] + As[i]
        for i in reversed(range(0, N-2, 2)):
            accRevAs[i] = accRevAs[i+2] + As[i]
        print('accAs:', accAs)
        print('accRevAs:', accRevAs)
        accRevAs += [0] * 5

        ans2 = -float('inf')
        for i in range(0, N-2, 2):
            sm = accAs[i] + accRevAs[i+4]
            if sm > ans2:
                ans2 = sm

        dp0 = [0, As[0]] + [0] * (N-2) +[0]*5
        dp1 = [As[0], As[1]] + [0] * (N-2) +[0]*5
        for i in range(2, N, 2):
            dp1[i] = dp0[i-1] + As[i]
            dp1[i+1] = dp0[i-1] + As[i+1]
            dp0[i+1] = dp1[i]
        print('dp0:', dp0)
        print('dp1:', dp1)

        ans3 = sum(As[2::2])
        for i in range(1, N, 2):
            sm = dp0[i] if dp0[i] >= dp1[i] else dp1[i]
            sm += accRevAs[i+3]
            if sm > ans3:
                ans3 = sm

        return max(ans1, ans2, ans3)


ans = max(func(As+[0]*5), func(As[::-1]+[0]*5))
print(ans)

Submission status: Wrong Answer

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


# list rからxことる
def f(r, x):
    if x == 0:
        return 0

    if len(r) == 0:
        if x == 0:
            return 0
        else:
            return -10000000000
    elif len(r) == 1:
        if x == 1:
            return r[0]
        else:
            return -10000000000
    elif len(r) == 2:
        return max(r)
    elif len(r) == 3:
        if x == 1:
            return max(r)
        return r[0] + r[-1]

    ret1 = r[0] + f(r[2:], x-1)
    ret2 = r[1] + f(r[3:], x-1)
    ret3 = f(r[2:], x)

    return max(ret1, ret2, ret3)


print(f(a, n//2))

Submission status: Wrong Answer

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

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

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

print(ans)

Submission status: Wrong Answer

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

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

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

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

a = onem()

n = l()

if a % 2 == 0:
  print(max(sum(n[::2]),sum(n[1::2])))
else:
  co = -(10**18)

  nn = [n[i] for i in range(a)]
  for i in range(a):
    if i >= 2:
      nn[-(i+1)] += nn[-(i-1)]


  ura = [-(10**18) for i in range(a)]
  for i in range(1,a,2):
    if i != 1:
      ura[-(i+1)] = max(ura[-(i+1)],nn[-(i-1)],nn[-(i-2)])
    else:
      ura[-(i+1)] = 0

  po = 0
  for i in range(1,a,2):
    co = max(co,po+ura[i])
    po += n[i]


  om = [-(10**18) for i in range(a)]
  for i in range(0,a,2):
    if i >= 2:
      om[-(i+1)] = max(om[-(i+1)],nn[-(i)],nn[-(i-1)])
    elif i >= 1:
      om[-(i+1)] = max(om[-(i+1)],nn[-(i)])
    else:
      om[-(i+1)] = 0
  po = 0
  for i in range(0,a,2):
    co = max(co,po+om[i])
    po += n[i]
  print(co)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
#sys.setrecursionlimit(150000)


def solve(N: int, A: "List[int]"):
    if N%2==0:
        print(max(sum(A[::2]), sum(A[1::2])))
        exit()
    ans=max(sum(A[1::2]), sum(A[2::2]), sum(A[0:N-1:2]))

    a0=a1=0
    s0=[0]*(N//2+2)
    s1=[0]*(N//2+1)
    for i in range(N):
        if i%2==0:
            a0+=A[i]
            s0[i//2+1]=a0
        else:
            a1+=A[N-1-i]
            s1[i//2+1]=a1

    M=N//2
    for i in range(M):
        ans=max(ans, s0[i]+s0[M-i])
    for i in range(M+1):
        ans=max(ans, s0[M+1]-A[i*2])
    if M>2:
        for i in range(M-2):
            ans=max(ans, s0[i+1]+s0[M+1]-s0[i+3]+A[i*2+3])
    print(s0, s1, ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
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: Wrong Answer

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

if n % 2 == 0:
  ans = - 10 ** 19

  AE = A[::2]
  AO = A[1::2][::-1]

  acumAE = [0] * (n // 2 + 1)
  acumAO = [0] * (n // 2 + 1)

  for i in range(n // 2):
    acumAE[i+1] = acumAE[i] + AE[i]
    acumAO[i+1] = acumAO[i] + AO[i] 

  for e, o in zip(acumAE, acumAO[::-1]):
    ans = max(ans, e + o)
else:
  ans = - 10 ** 19

  AE = A[1::2]
  AO = A[2::2][::-1]

  acumAE = [0] * (n // 2 + 1)
  acumAO = [0] * (n // 2 + 1)

  for i in range(n // 2):
    acumAE[i+1] = acumAE[i] + AE[i]
    acumAO[i+1] = acumAO[i] + AO[i] 

  for e, o in zip(acumAE, acumAO[::-1]):
    ans = max(ans, e + o)

  AE = A[:n-1:2]
  AO = A[1:n-1:2][::-1]

  acumAE = [0] * (n // 2 + 1)
  acumAO = [0] * (n // 2 + 1)

  for i in range(n // 2):
    acumAE[i+1] = acumAE[i] + AE[i]
    acumAO[i+1] = acumAO[i] + AO[i] 

  for e, o in zip(acumAE, acumAO[::-1]):
    ans = max(ans, e + o)

  AA = A[::2]
  sumAA = sum(AA)
  score = 0

  for i in AA:
    score = max(score, sumAA - i)
  
  ans = max(ans, score)

print(ans)

Submission status: Wrong Answer

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

odd = sum(A[::2])
eve = sum(A[1::2])

print(odd, eve)

if N % 2 == 0:
    print(max(odd, eve))
else:
    res = -float('inf')
    odd_l = 0
    eve_l = 0
    odd_r = odd - A[0]
    eve_r = eve - A[1]

    for i in range(N-1):
        if i % 2 == 0:
            tmp = eve_l + odd_r
        else:
            tmp = odd_l + eve_r
        res = max(res, tmp)

        if i < N-2:
            if i % 2 == 0:
                odd_l += A[i]
                odd_r -= A[i+2]
            else:
                eve_l += A[i]
                eve_r -= A[i+2]

    if N >= 5:
        for i in range((N-1)//2-1):
            tmp = odd - A[i*2+2]
            res = max(res, tmp)

    res = max(res, eve)

    print(res)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
if n%2==0:
    print(max(sum(l[::2]),sum(l[1::2])))
    exit()
rrec,rec=0,0
rrc,rc=0,0
z,q=[0]*n,[0]*n
rl=[0]*n
ll=[0]*n
for i in range(n):
    if (i%2):rec+=l[i]
    else:rc+=l[i]
    if (n-1-i)%2:rrec+=l[n-1-i]
    else:rrc+=l[n-1-i]
    rl[n-1-i]=max(rrec,rrc)
    z[n-1-i]=rrec;q[n-1-i]=rrc
    ll[i]=max(rec,rc)
ans=min(z[0],q[0]-l[0])
for i in range(n):
    if i==0:continue
    elif i==n-1:
        ans=max(ans,z[0],q[0]-l[0])
    else:
        ans=max(ans,ll[i]+rl[i])
print(ans)