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

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

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 = lo[n]
    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] + le_o[i])
        if n-i >= 1:
            ans = max(ans, le[i] + ro[n-i] + re[1] - ro[1])
        if i > 0:
            ans = max(ans, lo[i] + re[n-i] + le[1] - lo[1])
    print(ans)

Submission status: Wrong Answer

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

if n % 2 == 0:
    print(max(sum(a[0::2]), sum(a[1::2])))

else:
    pata, patb = [0], [0]
    for i in range(n):
        if i % 2 == 0:
            pata.append(pata[-1] + a[i])
        else:
            patb.append(patb[-1] + a[i])
    
    ans = sum(a[1::2])  
    for i in range(0, n // 2 + 1):
        ans = max(ans, pata[i] + patb[n // 2] - patb[i])
        
    for i in range(0, n // 2):
        ans = max(ans, patb[i] + pata[n // 2 + 1] - pata[i + 1])
        
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
INF=float('inf')
if n<=3:
    print(max(l))
elif n%2==1:
    dp=[[-INF]*3 for i in range(n+1)]
    dp[1][0]=l[0]
    dp[2][1]=l[1]
    dp[3][2]=l[2]
    for i,j in enumerate(l,1):
        dp[i][0]=max(dp[i-2][0]+j,dp[i][0])
        dp[i][1]=max(dp[i-2][1]+j,dp[i-3][0]+j,dp[i][1])
        dp[i][2]=max(dp[i-2][2]+j,dp[i-3][1]+j,dp[i-4][0]+j,dp[i][2])
    print(max(dp[-3][0],max(dp[-2]),dp[-1][2]))
else:
    print(max(sum(l[::2]),sum(l[1::2])))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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(oddacc[i]+evenacc[-1]-evenacc[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(100)-50 for _ in range(5)]

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

Submission status: Wrong Answer

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

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

print(ans)

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)]*5 for i in range(n+5)]
 
 
#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)
	if idx<2:
		dp[idx][0]=0
	if idx-2>=0:
		dp[idx]=dp[idx-2].copy()
	for j in range(1,4):
			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(4):
		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:
def main():
    n=int(input())
    A=list(map(int,input().split()))
    if n==3:
        return max(A)
    Odd,Even=[],[]
    for i,a in enumerate(A):
        if i%2==0:
            Even.append(a)
        else:
            Odd.append(a)
    if n%2==0:
        return max(sum(Even),sum(Odd))
    #ans=sum(Odd)
    #tmp=sum(Even)-max(Even)
    #ans=max(ans,tmp)
    DP=[[None]*3 for _ in range(n)]
    DP[0][0]=A[0]
    DP[1][1]=A[1]
    DP[2][0]=A[0]+A[2]
    DP[2][2]=A[2]
    DP[3][1]=max(A[0],A[1])+A[3]
    #print(DP)
    for i in range(4,n):
        a=A[i]
        if i%2==0:
            DP[i][0]=DP[i-2][0]+a
            DP[i][2]=max(DP[i-2][2]+a,DP[i-3][1]+a,DP[i-4][0]+a)
        if i%2!=0:
            DP[i][1]=max(DP[i-2][1]+a,DP[i-3][0]+a)
    ans=max(DP[-1][2],DP[-2][1],DP[-3][0])
    return ans
    
if __name__=='__main__':
    print(main())

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]
	np.cumsum(A, axis = 0, out = A)
	np.cumsum(B, axis = 0, out = B)
	ans = max(B[-1], A[-2], A[-1]-A[0])
	for i in range(len(A)-2):
		ans = max(ans, A[i]+(B[-1]-B[i]))


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)
##print(B)
ans = 0
cnt = 0
flag = [1 for _ in range(N)]
for i,j in B:
    if flag[i]:
        ans += j
        if i < N-1:
            flag[i+1] = 0
        if i > 0:
            flag[i-1] = 0
        flag[i] = 0
        cnt += 1
    if cnt == N//2:
        break

print(ans)

Submission status: Wrong Answer

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

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

ans = max(dp[N-2][1], dp[N-3][1] + A[N-1])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if len(a) % 2 == 0:
    b, c = 0, 0
    for i in range(0, n, 2):
        b += a[i]
    for i in range(1, n+1, 2):
        c += a[i]
else:
    a.remove(min(a))
    n -= 1
    print(a)
    b, c = 0, 0
    for i in range(0, n, 2):
        b += a[i]
    for i in range(1, n+1, 2):
        c += a[i]
print(b if b > c else c)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    t = [0]*n
    for i in range(n):
        t[i] = a[i]
        if 1 < i:
            t[i] += t[i-2]
    if n%2 == 0:
        print(max(t[n-1], t[n-2]))
    else:
        x = t[n-2] #全て偶数index
        y = -float("inf")
        for i in range(0, n, 2):
            y = max(y, t[n-1] - a[i])
        z = -float("inf") #奇数|偶数
        for i in range(1, n-2, 2):
            buf = t[i-1] + (t[n-2] - t[i])
            z = max(z, buf)
        w = -float("inf")#偶数|奇数
        for i in range(2, n-1, 2):
            buf = t[i-1] + (t[n-1] - t[i])
            w = max(w, buf)
        s = [-1]*n
        s[0] = 0
        s[1] = 1
        for i in range(2, n):
            s[i] = s[i-2]
            if i%2 == 1:
                if t[s[i]] > t[i]:
                    s[i] = i
        v = -float("inf")
        for i in range(3, n-2, 2):
            index = s[i]
            buf = t[n-1] - t[i+1] + t[index-1]
            buf += t[i] - t[index]
            v = max(v, buf)
        print(max(x, y, z, w, v))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n,*a=map(int,open(0).read().split())
if n%2==0:
	o=a[::2]
	e=a[1::2]
	o=[0]+list(accumulate(o))
	e=list(accumulate(e[::-1]))[::-1]+[0]
	ans=0
	for i in range(n//2+1):
		ans=max(ans,o[i]+e[i])
	print(ans)
	exit()
o=a[::2]
e=a[1::2]
o=[0]+list(accumulate(o))
e=list(accumulate(e[::-1]))[::-1]+[0]
dp=[0]*n
for i in range(n):
	if i%2==1:
		dp[i]=max(o[i//2]+a[i-1],o[i//2]+a[i],dp[i-2]+a[i])
	else:
		dp[i]=max(dp[i-1],dp[i-2]+a[i])
print(dp[-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
A1 = [A[i] for i in range(n) if i%2==1]
A2 = [A[i] for i in range(n) if i%2==0]

cum_A1 = [0]*(len(A1)+1)
cum_A2 = [0]*(len(A2)+1)

#print(A1, A2)

for i in range(len(A1)):
  cum_A1[i+1] =  cum_A1[i] + A1[i] 
for i in range(len(A2)):
  cum_A2[i+1] =  cum_A2[i] + A2[i] 
#print(cum_A1, cum_A2)

if n%2==0:
  print(max(sum(A1), sum(A2)))
else:
  mx = -10**18
  for i in range(1, n//2+1):
    v1 = cum_A1[i] + cum_A2[-1] - cum_A2[i+1]
    v2 = cum_A2[i] + cum_A1[-1] - cum_A1[i]
    v = max(v1, v2)
    if v>mx:
      mx = v
  mx = max(sum(A1), sum(A2)-min(A2), mx)
  print(mx)

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
doTest=1

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import itertools

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    #
    n=int(readline())
    aa=list(map(int, readline().rstrip().split()))
    #ss=readline().rstrip()
    #yn(1)
    c=n//2
    ans=0
    for cmb in itertools.combinations(list(range(n-c+1)),c):
        rui=0
        sm=0
        for i in range(len(cmb)):
            sm+=aa[cmb[i]+rui]
            rui+=1
        ans=max(ans,sm)
    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Wrong Answer

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
  
dp = [[[-float('inf')] * extra for _ in range(2)] for _ in range(N + 1)]
dp[0][0] = [0] + [-float('inf')] * (extra - 1)
dp[0][1] = [-float('inf')] * extra
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])


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

Submission status: Wrong Answer

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

half = int(N // 2)
rest = int(N % 2)
sum_1 = 0
sum_2 = 0
sum_3 = 0

if rest == 0:
  for i in range(half):
    sum_1 += A[2*i]
    sum_2 += A[2*i+1]
  print(max(sum_1, sum_2))
else:
  for i in range(half):
    sum_1 += A[2*i]
    sum_2 += A[2*i+1]
    sum_3 += A[2*i+2]
  print(max(sum_1, sum_2, sum_3))

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
INF=float('inf')
if n<=3:
    print(max(l))
elif n%2==1:
    dp=[[-INF]*3 for i in range(n+1)]
    dp[1][0]=l[0]
    dp[2][1]=l[1]
    dp[3][2]=l[2]
    for i,j in enumerate(l,1):
        dp[i][0]=max(dp[i-2][0]+j,dp[i][0])
        dp[i][1]=max(dp[i-2][1]+j,dp[i-3][0]+j,dp[i][1])
        dp[i][2]=max(dp[i-2][2]+j,dp[i-3][1]+j,dp[i-4][0]+j,dp[i][2])
    print(max(dp[-3][0],max(dp[-2]),max(dp[-1])))
else:
    print(max(sum(l[::2]),sum(l[1::2])))

Submission status: Wrong Answer

Solution code:
import math

N = int(input())
A = list(map(int, input().split()))
x = math.floor(N/2)

count = 0
for i in range(x):
    count += int(A[-(1+(2*i))])
print(count)

Submission status: Wrong Answer

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

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

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

print(ans)

Submission status: Wrong Answer

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

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

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

ans = 0

# mixed
for i in range(N // 2):
    ans_tmp = odd[i] + evn[N // 2 - 1 - i]
    # print("# mixed", i, odd[i], evn[N // 2 - 1 - i], ans_tmp)
    ans = max(ans, ans_tmp)

# odd only
for i in range(len(odd) - N // 2):
    ans_tmp = odd[i + N // 2] - odd[i]
    # print("# odd", i, odd[i + N // 2], odd[i], ans_tmp)
    ans = max(ans, ans_tmp)

if N % 2 > 0:
    sum_tmp = odd[-1]
    for i in range(N):
        if i % 2 == 0:
            ans_tmp = sum_tmp - A[i]
            ans = max(ans, ans_tmp)

# evn only
for i in range(len(evn) - N // 2):
    ans_tmp = evn[i + N // 2] - evn[i]
    # print("# evn", i, evn[i + N // 2], evn[i], ans_tmp)
    ans = max(ans, ans_tmp)

print(ans)

Submission status: Wrong Answer

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

if n < 20:
    d = a.copy()

    for i in range(1, n // 2):
        b = [0] * n
        f = [0]*n
        c = 0
        e = 0
        for j in range(i * 2, n):
            if c < a[j - 2]:
                e = j-2
            c = max(c, a[j - 2])
            b[j] = c + d[j]
            f[j] = e

        a = b.copy()
    print(a[-1])
    exit()
    
b = a[:10]

for i in range(1, n // 2):
    c = [0] * 10
    d = 0
    for j in range(10):
        if 2 * i + j >= n:
            continue
        d = max(d, b[j])
        c[j] = d + a[2 * i + j]
    b = c.copy()
print(max(b))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3.6
N = int(input())
A = [int(x) for x in input().split()]

if N%2 == 0:
    a = sum(A[::2])
    b = sum(A[1::2])
    print(max([a,b]))
else:
    n = N//2
    ans = sum(A[2::2])
    p = ans

    for i in range(n):
        q = p
        for j in range(i):
            q -= A[2*j+1]
            q += A[2*j]
            ans = max(ans,q)
        p -= A[2*i+2]
        p += A[2*i+1]
    print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a00, a01, a02, a10, a11, a12 = 0, 0, 0, 0, 0, 0
    for a in A:
        a00, a01, a02, a10, a11, a12 = a10, max(a11, a00), max(a01, a12), a00 + a, a01 + a, a02 + a

    if N & 2:
        return max(a10, a11, a12, a00, a01)
    else:
        return max(a10, a11, a00)


print(main())

Submission status: Wrong Answer

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

lis_0 = A[::2]
lis_1 = A[1::2]

if N%2 == 0:
  print(max(sum(lis_0), sum(lis_1)))
else:
  rui_0 = [0 for _ in range(len(lis_0)+1)]
  rui_1 = [0 for _ in range(len(lis_1)+1)]
  for i in range(1, len(lis_1)+1):
    rui_0[i] = rui_0[i-1] + lis_0[i-1]
    rui_1[i] = rui_1[i-1] + lis_1[i-1]
  rui_0[-1] = rui_0[-2] + lis_0[-1]
  last1 = rui_1[-1]
  last0 = rui_0[-1]
  
  num = 0
  for j in range(len(rui_1)):
    for k in range(j+1, len(rui_1)):
      x = rui_0[j]+rui_1[k]-rui_1[j]+last0-rui_0[k+1]
      if num < x:
      	num = x
  print(max(sum(lis_1), sum(lis_0)-lis_0[0], sum(lis_0)-lis_0[-1], num))

Submission status: Wrong Answer

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]

    print (max(e,o))

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] , ol[-1] + EOE)

    print (ans)

Submission status: Wrong Answer

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)
    
    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,p))

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

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n = int(input())
    a = list(map(int,input().split()))
    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)
    
    else:
        cuml = [0] * (n + 1)
        cumr = [0] * (n + 1)
        cumr2 = [0] * (n + 1)

        for i in range(n):
            if i == 0:
                cuml[i + 1] = a[i]
            else:
                cuml[i + 1] = cuml[i - 1] + a[i]
        
        for i in range(n - 1,-1,-1):
            if i == n - 1:
                cumr[i] = a[i]
                cumr2[i] = a[i]
            else:
                cumr[i] = cumr[i + 2] + a[i]
                if i%2 == 1:
                    if i == n - 2:
                        continue
                    if i == n - 4:
                        cumr2[i] = cumr2[i + 3] + a[i]
                    else:
                        cumr2[i] = max(cumr2[i + 2],cumr[i + 3]) + a[i]
        
        tmp = 0
        ans = 0
        for i in range(n - 1):
            if i%2 == 1:
                tmp += a[i]
            ans = max(ans,cuml[i] + cumr[i + 2])
            if i <= n - 6 and i%2 == 1:
                ans = max(ans,cuml[i] + cumr2[i + 2])
            if i <= n - 4 and i%2 == 1:
                ans = max(ans,cuml[i] + cumr[i + 3])
    
        ans = max(ans,tmp)
    print(ans)

if __name__ =='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
odd = [0]*(math.ceil(N/2)+1)
even = [0]*(N//2+1)
odd_sum,even_sum = 0,0
for i in range(N):
    if(i%2 == 0):
        odd_sum += A[i]
        odd[i//2+1] = odd_sum
    else:
        even_sum += A[i]
        even[i//2+1] = even_sum
print(odd,even)
ans = 0
if(N%2 == 0):
    for i in range(N//2+1):
        tmp = odd[i]+(even[N//2]-even[i])
        ans = max(ans,tmp)
else:
    for i in range(N//2+1):
        for j in range(i,N//2+1):
            tmp = odd[i] + (even[j]-even[i]) + (odd[N//2+1]-odd[j+1])
            #print(odd[i],even[j]-even[i],odd[N//2+1]-odd[j+1],tmp)
            ans = max(ans,tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
def solve(n,a):
    wa=0
    for i in range(n):
        if(i%2==0):
            wa+=a[i]
    kotae=wa
    for i in range(n//2):
        wa+=a[(n//2-i-1)*2+1]
        wa-=a[(n//2-i-1)*2]
        if(wa>kotae):
            kotae=wa
    return kotae

n=int(input())

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


print(solve(n,a))

Submission status: Wrong Answer

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
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)
	elif n== 4:
		return max(al[0]+al[2],al[0]+al[3],al[1]+al[3],al[1]+al[4])

	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][-4],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: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
if n%2 == 0:
     e = [a[0]]
     es = [a[0]]
     o = [a[1]]
     os = [a[1]]
     ans = 0
     for i in range(2,n):
          if i % 2 == 0:
               e.append(a[i])
               es.append(es[-1]+a[i])
          else:
               o.append(a[i])
               os.append(os[-1] + a[i])

     for i in range(0,n//2):
          ans = max([ans,os[i]-es[i]+es[-1],es[i]-os[i]+os[-1]])

else:
     e = [a[0]]
     es = [a[0]]
     o = [a[1]]
     os = [a[1]]
     ans = 0
     for i in range(2, n-1):
          if i % 2 == 0:
               e.append(a[i])
               es.append(es[-1] + a[i])
          else:
               o.append(a[i])
               os.append(os[-1] + a[i])

     for i in range(0, (n-1) // 2):
          ans = max([ans, os[i] - es[i] + es[-1], es[i] - os[i] + os[-1]])
print(ans)

Submission status: Wrong Answer

Solution code:
import itertools


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


p = itertools.combinations(list(range(N)), 2)

if N % 2 == 0:
    S = sum(A)
    s = sum(A[0::2])

    if S - s < s:
        print(s)
    else:
        print(S - s)

else:
    ans = 0
    for v in p:
        a, b = min(v), max(v)
        A_new = A[:a] + A[a+1:b] + A[b+1:]
        if ans < sum(A_new[0::2]):
            ans = sum(A_new[0::2])
    print(ans)