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:
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] = 0
    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 = dp[-1][0]
    #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()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

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

mx = 0
def dfs(i,c,s):
  global mx
  #print(i,c,s)
  if c == n//2:
    mx = max(s,mx)
    return
  if i > n-1:
    return
  dfs(i+2,c+1,s+a[i])
  if ((n-1)-(i+3))//2 >= n-c-1:
    dfs(i+3,c+1,s+a[i])
  if ((n-1)-(i+4))//2 >= n-c-1:
    dfs(i+4,c+1,s+a[i])
  
dfs(0,0,0)
dfs(1,0,0)
dfs(2,0,0)

print(mx)

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())
A = list(map(int, input().split()))

if N % 2:
    pass
else:
    print(max(sum(A[::2]), sum(A[1::2])))

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=[[0]+[-(10**20)]*7 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>=0:
		dp[idx]=dp[idx-2].copy()
	for j in range(1,6):
			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(6):
		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:
# Function to return max sum such that 
# no two elements are adjacent 
def find_max_sum(arr): 
	incl = 0
	excl = 0
	
	for i in arr: 
		
		# Current max excluding i (No ternary in 
		# Python) 
		new_excl = excl if excl>incl else incl 
		
		# Current max including i 
		incl = excl + i 
		excl = new_excl 
	
	# return max of incl and excl 
	return (excl if excl>incl else incl) 

# Driver program to test above function 
num=int(input())
arr=list(map(int,input().split(" ")))
print (find_max_sum(arr))

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(3,n):
        dp[i][0]=dp[i-2][0]+a[i]
        dp[i][1]=max(dp[i-3][0],dp[i-2][1])+a[i]
        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:
import sys
sys.setrecursionlimit(10 ** 9)

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

mx = 0
def dfs(i,c,s):
  global mx
  #print(i,c,s)
  if c == n//2:
    mx = max(s,mx)
    return
  if i > n-1:
    return
  dfs(i+2,c+1,s+a[i])
  if ((n-1)-(i+3))//2 >= n-c:
    dfs(i+3,c+1,s+a[i])
  if ((n-1)-(i+4))//2 >= n-c:
    dfs(i+4,c+1,s+a[i])
  
dfs(0,0,0)
dfs(1,0,0)
dfs(2,0,0)

print(mx)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			print(args)


def main():
	log = Logger(1)
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	
	half = int(n/2) + 1
	dp = [[None]*half for i in range(n)]
	dp[0][0] = 0
	dp[0][1] = a[0]
	dp[1][0] = 0
	dp[1][1] = a[1]
	log.print(dp[0])
	log.print(dp[1])
	for i in range(2, n):
		for j in range(half):
			if dp[i-2][j-1] is None and dp[i-1][j] is None:
				continue
			elif dp[i-2][j-1] is None:
				dp[i][j] = dp[i-1][j]
			elif dp[i-1][j] is None:
				dp[i][j] = dp[i-2][j-1] + a[i]
			else:
				dp[i][j] = max(dp[i-2][j-1] + a[i], dp[i-1][j])
		log.print(dp[i])
	print(dp[n-1][half-1])

	


main()

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

for i,j in B:
    if A[i] < 1e11:
        ans += j
        if i < N-1:
            A[i+1] = 1e12
        if i > 0:
            A[i-1] = 1e12
        A[i] = 1e11
        cnt += 1
    if cnt == N//2:
        break

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] + odd[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)

# 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 = 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 = 0



    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:
def selectHalf(ar):
    new_arr = []
    minus_ar = []
    minus = 0
    count = 0
    for i in ar:
        if i < 0:
            minus += 1
            minus_ar.append(i)
        if i % 2 == 0:
            new_arr.append(i)
            count += 1
    if count > 0:
        return sum(new_arr)
    else:
        return "0"

N = int(input())
ar = list(map(int, input().rstrip().split()))
print(selectHalf(ar))

Submission status: Wrong Answer

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

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])
    for i in range(3):
        for j in range(i):
            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 % 2 == 0:
        print(max(sum(a[::2]), sum(a[1::2])))
        return
    dp = [[[-10**15]*3, [-10**15]*3] for _ in [0]*(n+1)]
    dp[0][0][0] = 0
    for i in range(n):
        # 使う場合
        dp[i+1][1][0] = max(dp[i+1][1][0], dp[i][0][0]+a[i])
        dp[i+1][1][1] = max(dp[i+1][1][1], dp[i][0][1]+a[i])
        dp[i+1][1][2] = max(dp[i+1][1][2], dp[i][0][2]+a[i])
        # 使わない場合
        dp[i+1][0][1] = max(dp[i+1][0][1], dp[i][0][0])
        dp[i+1][0][2] = max(dp[i+1][0][2], dp[i][0][1])
        # 更新
        dp[i+1][0][0] = max(dp[i+1][0][0], dp[i][1][0])
        dp[i+1][0][1] = max(dp[i+1][0][1], dp[i][1][1])
        dp[i+1][0][2] = max(dp[i+1][0][2], dp[i][1][2])
    print(max(dp[n][0][2], dp[n][1][2], dp[n-1][1][1], dp[n][0][1]))


main()

Submission status: Wrong Answer

Solution code:
from math import floor

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

L = floor(N/2)

A.sort(reverse=True)

print(sum(A[:L]))

Submission status: Wrong Answer

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

    # res = max(dp[N - 1][2], dp[N - 2][1], dp[N - 3][0])
    res = 10 ** 17

print(res)

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
tmp = 0
cnt = 0

for i,j in B:
    if A[i] < 1e10:
        ans += j
        if i < N-1:
            A[i+1] = 1e11
        if i > 0:
            A[i-1] = 1e11
        #A[i] = 1e11
        cnt += 1
    
    if cnt == N//2:
        break

print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

left=[0]*N
right=[0]*N

left[0]=A[0]
left[1]=A[1]
for i in range(2,N):
    left[i]=A[i]+left[i-2]
right[-1]=A[-1]
right[-2]=A[-2]
for i in range(N-3,-1,-1):
    right[i]=A[i]+right[i+2]

ans=0
if N%2==0:
    ans=max(right[0],left[-1])
    for i in range(N-2):
        if i%2==0:
            continue
        ans=max(ans,left[i]+right[i+2])
    
        
else:
    P=[0]*N
    Q=[0]*N
    P[-2]=A[-2]
    Q[-2]=A[-1]
    for i in range(-4,-N-1,-1):
        if i%2==0:
            P[i]=A[i]+max(P[i+2],Q[i+2])
            Q[i]=A[i+1]+Q[i+2]

    data=[0]*N
    for i in range(N):
        data[i]=max(P[i],Q[i])
    
    qqq=0
    for i in range(N-2):
        if i%2==0:
            #使わない
            ans=max(ans,qqq+right[i+2])
            if i+3<N:
                ans=max(ans,qqq+A[i+1]+data[i+3])
            #使う
            qqq+=A[i]
    ans=max(ans,qqq)
    
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 n %2 == 0 and i == len(sm2)-1:
        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

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 n %2 == 0 and i == len(sm2)-1:
        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:
n = int(input())
lis = list(map(int,input().split()))
dp = set()
dp.add((0,0))
for num in lis:
  gone = set()
  kanasii = -10 ** 19
  for now,status in dp:
    if status == 0:
      gone.add((now + num,1))
    kanasii = max(kanasii,now)
  if kanasii != -10 ** 19:gone.add((kanasii,0))
  dp = gone
ans = -10 ** 19
for num,status in dp:
  ans = max(ans,num)
print(ans)

Submission status: Wrong Answer

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

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])
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:
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)
    
    print(max(S[-1]+mss,S[-2]))

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

Submission status: Wrong Answer

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

if N%2 == 0:
    c1 = 0
    c2 = 0
    for i in range(N//2):
        c1 += A[2*i]
        c2 += A[2*i+1]
    print(max(c1, c2))
else:
    c_odd = 0
    c_even = 0
    for i in range(N//2):
        c_odd += A[2*i]
        c_even += A[2*i+1]
    c_odd += A[-1]
    
    left_odd = 0
    left_even = 0
    max_tot = -int(1e20)
    for i in range(N):
        if i%2 == 0:
            right_odd = c_odd - left_odd - A[i]
            right_even = c_even - left_even
        else:
            right_odd = c_odd - left_odd
            right_even = c_even - left_even - A[i]
        #print(left_odd, left_even, right_odd, right_even)
        if i%2 == 0:
            cand = max(left_odd + right_odd, left_odd + right_even, left_even + right_odd, left_even + right_even)
        else:
            cand = max(left_odd + right_even, left_even + right_odd)
        #print(cand)
        if cand > max_tot:
            max_tot = cand
        if i%2 == 0:
            left_odd += A[i]
        else:
            left_even += A[i]
    print(max_tot)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

l.sort(reverse = True)

ans = 0

for i in range(0,n-1,2):
  ans += l[i]
    
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 n %2 == 0 and i == len(sm2)-1:
        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

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 n %2 == 0 and i == len(sm2)-1:
        continue
    ans = max(ans, sm2[i] + sm1[-1] - sm1[i+1])
    
    if val < switch_better[i]:
        tmp = i
    
    ans = max(ans, sm2[i]+sm1[-1]-sm1[i+1]-sm2[tmp]+sm1[tmp])

print(ans)

Submission status: Wrong Answer

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

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

    # print (B)
    # print (W)

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

    print (ans)
    exit()

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

DP0[N][0] = 0

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

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

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

# for i in DP0:
#     print (i)

# for i in DP1:
#     print (i)

# for j in DP2:
#     print (j)

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])
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(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]))
            else:
                al.append(a[i] + max(d,k[now-1]))
#print(al)
print(max(al))

Submission status: Wrong Answer

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

if N%2 == 0:
    c1 = 0
    c2 = 0
    for i in range(N//2):
        c1 += A[2*i]
        c2 += A[2*i+1]
    print(max(c1, c2))
else:
    c_odd = 0
    c_even = 0
    for i in range(N//2):
        c_odd += A[2*i]
        c_even += A[2*i+1]
    c_odd += A[-1]
    
    left_odd = 0
    left_even = 0
    max_tot = -int(1e20)
    for i in range(N):
        if i%2 == 0:
            right_odd = c_odd - left_odd - A[i]
            right_even = c_even - left_even
        else:
            right_odd = c_odd - left_odd
            right_even = c_even - left_even - A[i]
        print(left_odd, left_even, right_odd, right_even)
        if i%2 == 0:
            cand = max(left_odd + right_odd, left_odd + right_even, left_even + right_odd, left_even + right_even)
        else:
            cand = max(left_odd + right_even, left_even + right_odd)
        #print(cand)
        if cand > max_tot:
            max_tot = cand
        if i%2 == 0:
            left_odd += A[i]
        else:
            left_even += A[i]
    print(max_tot)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    if n % 2 == 0:
        print(max(sum(a[::2]), sum(a[1::2])))
        return
    dp = [[[-10**15]*3, [-10**15]*3] for _ in [0]*(n+1)]
    dp[0][0][0] = 0
    for i in range(n):
        # 使う場合
        dp[i+1][1][0] = max(dp[i+1][1][0], dp[i][0][0]+a[i])
        dp[i+1][1][1] = max(dp[i+1][1][1], dp[i][0][1]+a[i])
        dp[i+1][1][2] = max(dp[i+1][1][2], dp[i][0][2]+a[i])
        # 使わない場合
        dp[i+1][0][1] = max(dp[i+1][0][1], dp[i][0][0])
        dp[i+1][0][2] = max(dp[i+1][0][2], dp[i][0][1])
        # 更新
        dp[i+1][0][0] = max(dp[i+1][0][0], dp[i][1][0])
        dp[i+1][0][1] = max(dp[i+1][0][1], dp[i][1][1])
        dp[i+1][0][2] = max(dp[i+1][0][2], dp[i][1][2])
    print(max(dp[n][0][2], dp[n][1][2], dp[n-1][1][1]))


main()

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)
    
    print(max(S[-1]+mss,S[-2]))

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