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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(i) for i in input().split(' ')]

SUM0 = 0
SUM1 = 0
mi = 10**9 + 1
lis0 = []
lis1 = []
for i,a in enumerate(A):
    if i%2 == 0:
        if mi > a:
            mi = a
        SUM0+= a
        lis0.append(a)
    else:
        SUM1 += a
        lis1.append(a)
# print(SUM0,SUM1)
if N%2 == 0:
    answer = SUM0 if SUM0 > SUM1 else SUM1
else:

    SUM0 -= mi
    tmp = SUM0 if SUM0 > SUM1 else SUM1
    tmp0 = []
    tmp1 = []
    t0 = 0
    t1 = 0
    mx = - 10**15
    ttt = []
    for i,j in zip(lis0,lis1):
        t0 += i
        ttt.append(i)
        t1 += j
        a1 = SUM1 - t1
        a0 = SUM0 - t0
        a = t0+ a1
        if a > mx:
            mx =a

    answer = mx if mx > tmp else tmp
    t0 = 0 
    t1 = 0
    mx = - 10**15
    for b,i in enumerate(lis1):
        t0 += lis0[b+1]
        t1 += i
        a1 = SUM1 - t1
        a0 = SUM0 - t0
        a = a0 + t1

        if a > mx:
            mx =a
    answer = mx if mx > answer else answer
print(answer)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int, input().split()))
d=-100000000000000
if n%2==0:
    for i in range(n//2+1):
        e=0
        for k in range(0,i):
            e+=a[2*k]
        for l in range(i,n//2):
            e+=a[2*l+1]
        if e>d:
            d=e
if n%2==1:
    for i in range(n//2+1):
        e=0
        for k in range(0,i):
             e+=a[2*k]
        for j in range (i,n//2):
            f=0
            f+=a[2*j+1]
            if e+f>d:
                d=e+f
            for l in range(i,n//2):
                f=f+a[2*l+2]-a[2*l+1]
                if e+f>d:
                    d=e+f
            
print(d)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))
if(n%2==0):
    answera=0
    answerb=0
    for i in range(int(n/2)):
        answera+=a[2*i]
        answerb+=a[2*i+1]
    print(max(answera, answerb))
else:
    ff=0
    fb=0
    bf=0
    bb=0
    for i in range(int(n/2)-1):
        bf+=a[3+2*i]
        bb+=a[4+2*i]
    answerb=max(bb,bf)+a[0]
    answerc=max(bb,bf)+a[1]
    answerd=bb+a[2]       
    answera=max(answerb,answerc,answerd)
    for j in range(int(n/2)-2):
        ff+=a[2*j]
        fb+=a[2*j+1]
        bf-=a[2*j+5]
        bb-=a[2*j+6]
        answerb=ff+max(bf,bb)+a[2*j+2]
        answerc=max(ff,fb)+max(bf,bb)+a[2*j+3]
        answerd=max(ff,fb)+bb+a[2*j+4]
        answere=max(answerb,answerc,answerd)
        if(answere>answera):
            answer=answere
    j=int(n/2)-2
    ff+=a[2*j]
    fb+=a[2*j+1]
    answerb=ff+a[2*j+2]
    answerc=max(ff,fb)+a[2*j+3]
    answerd=max(ff,fb)+a[2*j+4]       
    answere=max(answerb,answerc,answerd)
    if(answere>answera):
        answera=answere
    print(answera)

Submission status: Wrong Answer

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



if n % 2 == 0:
    tp = sum(arr[::2])
    print(max(sum(arr)-tp,tp))
else:
    hoge = -(10**12)
    buf = [[hoge for i in range(3)] for j in range(n)]
    buf[0][0] = arr[0]
    buf[1][1] = arr[1]
    buf[2][2] = arr[2]
    buf[2][0] = arr[0]+arr[2]

    for i in range(3,n):
        buf[i][0] = buf[i-2][0] + arr[i]
        buf[i][1] = max(buf[i-3][0] + arr[i],buf[i-2][1]+arr[i])
        buf[i][2] = max(buf[i-3][1] + arr[i],buf[i-2][2]+arr[i])
        if i >= 4:
            buf[i][2] = max(buf[i-4][0] + arr[i],buf[i-2][2]+arr[i])

    # print(buf)
    for l in buf:
        print(l)
    print(max(buf[-1][2],buf[-2][1],buf[-3][0]))

Submission status: Wrong Answer

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

def getsum(use):
    wa = sum([a[i] for i in use])
    return wa

sums = []
if n%2==0:
    sums.append(sum([a[i] for i in range(n) if i%2==0]))
    sums.append(sum([a[i] for i in range(n) if i%2!=0]))

else:
# 0からスタート　２つ余裕あり
    for i in range(n//2):
        for j in range(n//2):
            use = [i for i in range(n-2) if i%2==0]
            for k in range(n//2):
                if k>=i : use[k]+=1
                if k>=j : use[k]+=1
            sums.append(getsum(use))


ans = max(sums)
print(ans)

# 1からスタート　１つ余裕あり
#use = [i+1 for i in range(n-1) if i%2==0]
# 2からスタート　余裕なし（2,4... n-1）
#use = [i+2 for i in range(n-1) if i%2==0]

Submission status: Wrong Answer

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

ldp = [[0]*n,[0]*n,]
rdp = [
    [0]*n,
    [0]*n,
]
for i in range(n):
    flag = (i+1)%2
    ldp[flag][i] = a[i] if i-2 < 0 else ldp[flag][i-2]+a[i]
    ldp[(flag+1)%2][i] = 0 if i-1 < 0 else ldp[(flag+1)%2][i-1]

for i in range(n, 0, -1):
    flag = (n-(i-1))%2
    rdp[flag][i-1] = a[i-1] if i+1 >= n else rdp[flag][i+1]+a[i-1]
    rdp[(flag+1)%2][i-1] = 0 if i >= n else rdp[(flag+1)%2][i]
if n%2 == 0:
    ans = max(rdp[1][1], ldp[1][n-2])
    for i in range(1, n-1):
        if i%2 == 0:
            ans = max(max(ldp[0][i-1], ldp[1][i-1]) + rdp[1][i+1], ans)
        else:
            ans = max(ldp[1][i-1] + max(rdp[0][i+1], rdp[1][i+1]), ans)
else:
    ans = max(rdp[1][2], ldp[1][n-3])
    for i in range(1, n-2):
        if i%2 == 0:
            if i%2 == 0:
                ans = max(max(ldp[0][i-1], ldp[1][i-1]) + rdp[1][i+2], ans)
            else:
                ans = max(ldp[1][i-1] + max(rdp[0][i+2], rdp[1][i+2]), ans)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
s_odd = []
s_eve = []
s_odd_a = []
s_odd_b = []
if n % 2 == 0:
    for i in range(0, n // 2):
        s_odd.append(a[i * 2])
        s_eve.append(a[i * 2 + 1])
    print(max(sum(s_odd), sum(s_eve)))
else:
    for i in range(0, n // 2):
        s_odd.append(a[i * 2])
        s_eve.append(a[i * 2 + 1])
        s_odd_a.append(a[(i + 1) * 2])
    if n > 5:
        s_odd_b = s_odd_a
        s_odd_b.append(a[0])
        print(max(sum(s_odd), sum(s_eve), sum(s_odd_a), sum(s_odd_b) - min(s_odd_b)))
    else:
        print(s_odd, s_eve, s_odd_a)
        #print(sum(s_odd), sum(s_eve), sum(s_odd_a))
        print(max(sum(s_odd), sum(s_eve), sum(s_odd_a)))

Submission status: Wrong Answer

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

N = int(input())
if N % 2 == 0:
	T = np.array(list(map(int, input().split())),np.int64)
	A = T[::2]
	B = T[1::2]
	ans = max(np.sum(A), np.sum(B))

else:
	I = np.array(list(map(int, input().split())), np.int64)
	A = I[::2]
	B = I[1::2]
	ans = 0
	tmp = np.sum(A)
	for a in A:
		ans = max(ans, tmp-a)
	np.cumsum(A, axis = 0, out = A)
	np.cumsum(B, axis = 0, out = B)
	ans = max(ans,B[-1])
	for i in range(len(A)-1):
		ans = max(ans, A[i]+(B[-1]-B[i]))
	for i in range(len(B)-1):
		ans = max(ans, B[i]+(A[-1]-A[i+1]))
	for i in range(1,len(B)-1):
		ans = max(ans, A[i-1]+B[i]-B[i-1]+A[-1]-A[i+1])

print(ans)

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:
    ans=0
    tmp=0
    for i in range(0,n-2,2):
        tmp+=arr[i]
    ans=max(ans,tmp)
    tmp=0
    for i in range(1,n-1,2):
        tmp+=arr[i]
    ans=max(ans,tmp)
    tmp=0
    for i in range(2,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+1])
        ans=max(ans,tmp)
    for i in range(1,n,2):
        tmp=(acum2[i]-acum2[0])+(acum1[-1]-acum1[i+1])
        ans=max(ans,tmp)
    acummax=[0]
    for i in range(n-1,-1,-1):
        tmp=acum1[-1]-acum1[i]+acum2[i]
        acummax.append(max(acummax[-1],tmp))
    acummax=acummax[::-1]
    for i in range(0,n,2):
        tmp=(acum1[i]-acum1[0]-acum2[i+1])+acummax[i+1]
        ans=max(ans,tmp)
    print(ans)

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(dp)
#print(*ans, sep='\n')

Submission status: Wrong Answer

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()
x = n//2

dp = [[a[i]]*(x+1) for i in range(n)]

se = [2,3,4]

for i in range(n):
    for j in range(2,x+1):
        a = -10000000000000000
        for k in se:
            p = i-k
            if p >= 0:
                a = max(a,dp[p][j-1])
        dp[i][j] += a

print(dp[n-1][x])

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)]*6 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):
				if idx-k-1>=0:
					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())
li = list(map(int, input().split()))
e = li[0::2] # one more  maybe
o = li[1::2]
s = -10000000000
m = int(n/2)
if n % 2 == 0:
    for i in range(m+1):
        s = max(s,sum(e[:i])+sum(o[i:]))
else:
    li += [0]
    print(li)
    e = li[0::2] # one more  maybe
    o = li[1::2]
    m = int(n/2)
    for i in range(m+1):
        s = max(s,sum(e[:i])+sum(o[i:]))

print(s)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(i) for i in input().split(" ")]

if len(A)%2==0:
    A1=sum(A[0::2])
    A2=sum(A[1::2])
    if(A1>A2):
        print(A1)
    else:
        print(A2)
else:
    print(
        max(
            [
                sum(A[0:n:2]+A[n::2])
                for n in range(2,len(A))
            ][:int(len(A)/2)]
            +
            [
                sum(A[1::2])
            ]
            +
            [
                sum(A[2::2])
            ]
        )
    )

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] = 0
    dp[0][2] = 0
    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:
N = int(input())
As = [int(n) for n in input().split()]

ruiseki_l = [As[0]]
ruiseki_r = [As[-1]]
for i in range(1, N // 2):
    ruiseki_l.append(ruiseki_l[-1] + As[i * 2])
    ruiseki_r.append(ruiseki_r[-1] + As[-i * 2 - 1])

ruiseki_r = list(reversed(ruiseki_r))
# print(ruiseki_l)
# print(ruiseki_r)
if N % 2 == 0:
    print(max([x + y for x, y in zip([0] + ruiseki_l, ruiseki_r + [0])]))

Submission status: Wrong Answer

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:
		ans1 = 0
		ans2 = 0
		for i in range(int(N // 2)):
			ans1 += A[2 * i]
			ans2 += A[2 * i + 1]

		print(max(ans1, ans2))
	
	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: Wrong Answer

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

if N%2 == 0:
    sumA = 0
    sumB = 0
    for i in range(N):
        if i%2==0:
            sumA += A[i]
        else:
            sumB += A[i]
    print(max(sumA, sumB))
else:
    partSum = [0] * N
    partSum[0] = A[0]
    partSum[1] = A[1]
    #odd_part = [0] * N
    #even_part[0] = A[0]
    for i in range(2,N):
        partSum[i] = (partSum[i-2] + A[i])

    ans = partSum[N-2]
    # blockとblock+1は選択されない
    for block in range(N-1):
        #print("========================block=",block)
        tmp = 0
        if block%2 == 0:
            #left
            if block >= 2:
                tmp += max(partSum[block-1], partSum[block-2]) # TODO: outbounds
            #   print("left : ",tmp, " || " , partSum[block-1], partSum[block-2])
            #right
            tmp += (partSum[N-1] - partSum[block])
            #print("right : " , (partSum[N-1] - partSum[block]))
        else:
            #left
            tmp += partSum[block-1]
            #print("left: " , tmp)
            #right
            if block < N-2:
                tmp += max((partSum[N-2] - partSum[block]), (partSum[N-1] - partSum[block+1]))
            #print("right : " , max((partSum[N-2] - partSum[block]), (partSum[N-1] - partSum[block+1])), (partSum[N-2] - partSum[block]), (partSum[N-1] - partSum[block+1]))
        #print("ppp = ",tmp)
        ans = max(ans, tmp)
    print(ans)

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)
    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 = [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)

ans = max(sm1[-1], 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 math            
N = int(input())
A = list(map(int,input().split()))
ans = 0
if N % 2 == 0:
    ans = max(sum(A[::2]),sum(A[1::2]))
else:
    for i in range(N-N//2):
        num = sum(A[i::2])
        if num > ans:
            ans = num   
print(ans)

Submission status: Wrong Answer

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


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

    even = 0
    odd = 0
    minimum = min(A)
    min_idx = []
    for i in range(N):
        if i % 2 == 0:
            even += A[i]
        else:
            odd += A[i]
        if A[i] == minimum:
            min_idx.append(i)

    if N % 2 == 0:
        print(max(even, odd))
    else:
        print(max(odd, even - minimum))

    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

@lru_cache(None)
def F(index, n):
    if index >= N:
        return -INF
    if N - index < 2 * n:
        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: Wrong Answer

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

N = int(input())
A = list(map(int, input().split()))
Aeven = sum(A[1::2])
Aodd = sum(A[0::2])

if N % 2 == 0:
    ans = max(Aeven, Aodd)
    print(ans)
    exit()


def cnt1(N, A):
    if len(A) <= 3:
        return max(A)
    global Aeven, Aodd
    od = 0
    ev = 0
    ri = Aodd - A[0]
    memo_l = [0]
    memo_r = [ri]

    for i in range(N // 2 - 1):
        od += A[i * 2]
        ev += A[i * 2 + 1]
        memo_l.append(max(od, ev))
        ri -= A[(i + 1) * 2]
        memo_r.append(ri)

    res = max(x+y for x, y in zip(memo_l, memo_r))
    res = max(res, Aeven)

    return res


def rec(N, B):
    if N <= 3:
        return max(B)
    global Aeven, Aodd

    res = cnt1(N, B)
    B.reverse()
    res = max(cnt1(N, B), res)

    ad = B.pop() + B.popleft()
    Aodd -= ad
    Aeven -= B.popleft() + B.pop()
    return max(res, ad + rec(N - 4, B))


B = deque(A)
ans = rec(N, B)
print(ans)

Submission status: Wrong Answer

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

def main():
    n=int(input())
    a=list(map(int,input().split()))
    #print(a)
    
    if n%2==0:
        print(max(sum(a[::2]),sum(a[1::2])))
        sys.exit()

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

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

    #print(dp)

    print(max(dp[n-3][n//2],dp[n-2][n//2],dp[n-1][n//2]))

main()

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()
	
dp=[[-(10**20)]*6 for i in range(n+5)]+[[0]+[-(10**20)]*6 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):
				if idx-k-1>=0:
					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:
from operator import itemgetter
N = int(input())
A = list(map(int,input().split()))
B = sorted(enumerate(A), key=itemgetter(1),reverse=True)

if N%2 ==0:
    print(max(sum(A[::2]),sum(A[1::2])))
else:
    m1 = sum(A[1::2])
    m = sum(A[::2])
    m3 = m - min(A[::2])
    print(max(m1,m3))

Submission status: Wrong Answer

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

E=[]
O=[]

for i in range(N):
    if i%2==0:
        E.append(A[i])
    else:
        O.append(A[i])
SE=[E[0]]
SO=[O[0]]
rSE=[E[-1]]
rSO=[O[-1]]

for i in range (1,len(E)):
    SE.append(SE[-1]+E[i])
    rSE.append(rSE[-1]+E[-(i+1)])

for i in range (1,len(O)):
    SO.append(SO[-1]+O[i])
    rSO.append(rSO[-1]+O[-(i+1)])

rSE.reverse()
rSO.reverse()
MO=[0 for i in range(len(O))]

if N%2==0:
    ans=max(SE[-1],SO[-1])
else:
    ans=SO[-1]
    for i in range(len(MO)):
        if i>0:
            MO[i]=max(MO[i-1]+O[i],SE[i-1]+O[i])
        else:
            MO[i]=SO[i]
    ans=max(ans,MO[-1],SE[-1]-E[-1],SE[-1]-E[-2])
    for i in range(len(E)-2):
        ans=max(ans,SE[i]+rSO[i+1],MO[i]+rSE[i+2],SE[-1]-E[i])


print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

if N % 2 == 0:
    p = sum(A[i*2] for i in range(N//2))
    q = sum(A[i*2 + 1] for i in range(N//2))
    print(max(p, q))

elif N == 1:
    print(0)
else:
    dpL = [0] * N
    dpLn = [0] * N
    dpR = [0] * N
    dpRn = [0] * N

    for i in range(N):
        if i < 2:
            dpL[i] += A[i]
            dpLn[i] += 1
        else:
            dpL[i] = dpL[i - 2] + A[i]
            dpLn[i] = dpLn[i - 2] + 1

    for i in range(N - 1, -1, -1):
        if i > N - 3:
            dpR[i] += A[i]
            dpRn[i] += 1
        else:
            dpR[i] = dpR[i + 2] + A[i]
            dpRn[i] = dpRn[i + 2] + 1

    ans = -10**18

    for r in range(6):
        for i in range(N - r):
            if dpLn[i] + dpRn[i + r] == N//2:
                ans = max(ans, dpL[i] + dpR[i + r])

    for i in range(min(N, 6)):
        if dpLn[-i-1] == N//2: ans = max(ans, dpL[-i-1])
        if dpRn[i] == N // 2: ans = max(ans, dpR[i])
    print(ans)

Submission status: Wrong Answer

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

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

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

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

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

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

    print(ans)

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

    print(ans)

Submission status: Wrong Answer

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

if N%2==0:
  alist1=alist[::2]
  alist2=alist[1::2]
  print(max(sum(alist1),sum(alist2)))
else:
  alist1=alist[::2]
  alist1.sort()  
  alist2=alist[1::2]
  print(max(sum(alist1)-alist1[0],sum(alist2)))

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-1]+rl[i+1])
print(ans)