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()))
ans1=0
ans2=0
inf=-10**18
if n%2:
    dp=[[inf]*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]
        else:
            dp[i][1]=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]
        elif i>=3:
            dp[i][2]=max(dp[i-3][1],dp[i-2][2])+a[i]
        else:
            dp[i][2]=dp[i-2][2]+a[i]
    ans=max(dp[n-3][0],dp[n-2][1],dp[n-1][2])
    # print(dp)
    dp=[[inf]*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])+a[i]
    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=[[inf]*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])+a[i]
        else:
            dp[i][1]=dp[i-2][1]+a[i]
    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:
nm = int(input())
nlist = list(map(int, input().split()))
 
ans = 0
ans2 = 0
ans3 = 0
ans4 =0
 
l = 0
flg = 0
anslist=[]
 
if len(nlist)%2==0:
  l = len(nlist)
  for i in range(l):
    if i % 2 == 0:
      ans += nlist[i]
    else:
      ans2 +=nlist[i]
 
  if ans > ans2:
    print(ans)
  else:
    print(ans2)
      
else:
  l = len(nlist)-1
  for i in range(l):
    if i % 2 == 0:
      ans += nlist[i]
    else:
      ans2 += nlist[i]
  for i in range(1,len(nlist)):
    if i % 2 == 0:
      ans3 +=nlist[i]
    else:
      ans4 += nlist[i]
  anslist.append(ans)
  anslist.append(ans2)
  anslist.append(ans3)
  anslist.append(ans4)
  print(max(anslist))

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 = -100000000000
        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:
n = int(input())
a = list(map(int, input().split()))

s1 = sum(a[0:int(n/2)*2:2])
s2 = sum(a[1:int(n/2)*2+1:2])
a.reverse()
"""
s3 = sum(a[-int(n/2)-1:-1:-2])
s4 = sum(a[-int(n/2)-2:-2:-2])
"""
s3 = sum(a[0:int(n/2)*2:2])
s4 = sum(a[1:int(n/2)*2+1:2])

"""
print(s1)
print(s2)
print(s3)
print(s4)
"""

print(max(s1,s2, s3, s4))

Submission status: Wrong Answer

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

if N % 2 == 0:#Nが偶数
  inf = float("inf")
  DP = [[-inf for i in range(2)] for i in range(N)]
  #print(DP)
  DP[0][0] = A[0]
  DP[1][1] = A[1]
  for i in range(2, N):
    DP[i][0] = DP[i - 2][0] + A[i]
    DP[i][1] = max(DP[i - 2][1], DP[i - 3][0]) + A[i]
  print(DP[N - 1][1])
  
else:#Nが奇数         
  #print(N)
  inf = float("inf")
  DP = [[-inf for i in range(3)] for i in range(N)]
  #print(DP)
  DP[0][0] = A[0]
  DP[1][1] = A[1]
  DP[2][2] = A[2]
  DP[2][0] = A[0] + A[2]
  for i in range(3, N):
    DP[i][0] = DP[i - 2][0] + A[i]
    DP[i][1] = max(DP[i - 2][1], DP[i - 3][0]) + A[i]
    DP[i][2] = max(DP[i - 2][2], DP[i - 3][1]) + A[i]
  print(DP[N - 1][2])

Submission status: Wrong Answer

Solution code:
n=int(input())
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])
    ans=max(dp[-3][0],max(dp[-2]),max(dp[-1]))
    so=[0]
    se=[0]
    for i in range(n):
        if i%2==0:
            so.append(so[-1]+l[i])
        else:
            se.append(se[-1]+l[i])
    ans=max(se[-1],so[n//2],so[-1]-so[1],ans)
    for i in range(1,n//2):
        ans=max(ans,so[i]+se[-1]-se[i],so[i]+so[-1]-so[i+1],so[-1]-so[-(i+1)]+se[n//2-i])
    print(ans)    
else:
    print(max(sum(l[::2]),sum(l[1::2])))

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)]
    dp[0][2] = 0
    for i in range(4, len(a)):
        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:-2]))
    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 = [int(e) for e in input().split(" ")]

A.reverse()
sum1 = 0
for i in range(int(N/2)):
    sum1 = sum1 + A[2*i]

print(sum1)

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 = -10**9
  for j in range(len(rui_1)):
    for k in range(j+1, len(rui_1)):
      if j == len(rui_1)-2:
        x = rui_0[j]+max(A[-1], A[-2], A[-3])
      else:
        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:
  ans = - 10 ** 19

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

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

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

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

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

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

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

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

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

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

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

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

print(ans)

Submission status: Wrong Answer

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

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

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

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

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

    ans = 0
    print(ans)
    return

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

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

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

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

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

    dp = [[-inf]*3 for _ in range(N+1)]
    dp[0][0] = 0
    dp[0][1] = 0
    dp[0][2] = -inf
    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 = 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())
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:
    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:
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 10

dp = [[0] * 2 for _ in range(n + 1)]

for i, e in enumerate(a, 1):
    e += INF
    dp[i][0] = max(dp[i-1][0], dp[i-1][1])
    if i - 2 >= 0:
        dp[i][1] = max(dp[i-2][0], dp[i-2][1]) + e

ans = max(dp[n][1], dp[n-1][1]) - n // 2 * INF
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
inf = float('inf')
ans = -1 *inf

if N % 2 == 0:
    S_odd = [0]*(N//2+1)
    S_even = [0]*(N//2+1)
    s_odd = 0
    s_even = 0
    for i in range(len(A)):
        if i%2 == 0:
            s_odd += A[i]
            S_odd[i//2+1] = s_odd
        else:
            s_even += A[i]
            S_even[i//2+1] = s_even
    
    s = 0
    for j in range(N//2+1):
        s = S_odd[j] + S_even[N//2]-S_even[j] 
        ans = max(ans,s)
else:
    S_odd = [0]*(N//2+2)
    S_even = [0]*(N//2+1)
    odd = []
    s_odd = 0
    s_even = 0
    for i in range(len(A)):
        if i%2 == 0:
            s_odd += A[i]
            S_odd[i//2+1] = s_odd
            odd.append(A[i])
        else:
            s_even += A[i]
            S_even[i//2+1] = s_even
    
    s = 0
    print(S_odd)
    print(S_even)
    ans = sum(odd)-min(odd)
    print(ans)

    for j in range(0,N//2):
        s = S_odd[j] + S_even[N//2]-S_even[j]
        ans = max(ans,s)

print(ans)

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)

        cuml = [0] * (n + 1)
        cumr = [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]
            else:
                cumr[i] = cumr[i + 2] + a[i]
        
        for i in range(n - 2):
            if i%2 == 1:
                ans = max(ans,cuml[i] + cumr[i + 2])
    
    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:
n=int(input())
a=list(map(int,input().split()))
if n%2==0:
    print(max(sum(a[::2]),sum(a[1::2])))
    exit()
ans=-10**10
t1=a[1::2]
t2=a[::2]
ans=sum(t1)
s=sum(t1)
for i in range(n//2):
    s+=t2[i]
    s-=t1[i]
    ans=max(ans,s)
s+=t2[-1]
s-=t2[0]
ans=max(ans,s)
s=sum(t2)
for i in range(n//2+1):
    ans=max(ans,s-t2[i])
t1=a[1::2][::-1]
t2=a[::2][::-1]
ans=sum(t1)
s=sum(t1)
for i in range(n//2):
    s+=t2[i]
    s-=t1[i]
    ans=max(ans,s)
s+=t2[-1]
s-=t2[0]
ans=max(ans,s)
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]))

print(le)
print(lo)
print(re)
print(ro)
print(le_o)

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:
import sys

n = int(input())
a = list(map(int,input().split()))
a1 = []
a2 = []
for i in range(n):
    if i%2 == 0:
        a1.append(a[i])
    else:
        a2.append(a[i])
        
ans = -11470000000000000
m = n//2
x = sum(a1) 

if n%2 == 0:
    print(max(sum(a1),sum(a2)))
    sys.exit()

else:
    aa1 = []
    aa2 = []
    v = 0
    vv = 0
    nn = n//2
    for i in a1:
        v += i
        aa1.append(v)
    for i in a2:
        vv += i
        aa2.append(vv)
    
    for i in range(nn + 1):
        ans = max(ans,x-a1[i])
        
    for i in range(nn-1):
        c = aa1[i] + (aa2[nn-1] - aa2[i])
        ans = max(ans,c)
    
    for i in range(nn-1):
        c = aa2[i] + (aa1[nn] - aa1[i+1])
        ans = max(ans,c)
        
    ans = max(ans,sum(a2))
    
print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
def main():
    N = int( input())
    A = list( map( int, input().split()))
    if N == 2:
        print(A[0], A[1])
        return
    OddSum = [0]
    EvenSum = [0]
    for i in range(N):
        if i%2 == 0:
            OddSum.append(OddSum[-1] + A[i])
            EvenSum.append(EvenSum[-1])
        else:
            OddSum.append(OddSum[-1])
            EvenSum.append(EvenSum[-1] + A[i])
    if N%2 == 0:
        ans = max(OddSum[-1], EvenSum[-1])
        for i in range(1,N,2):
            t = EvenSum[-1] - EvenSum[i+1] + OddSum[i] - OddSum[0]
            if ans < t:
                ans = t
        print(ans)
        return

    ans = max( EvenSum[-1], OddSum[-1] - min(A[::2]))
    Head = [0]
    for i in range(1,N+1):
        if i%2 == 1:
            Head.append(Head[-1])
            continue
        if i == 2:
            Head.append(A[i-1])
            continue
        Head.append( max(Head[-1], OddSum[i-2]) + A[i-1])

    Back = [0]
    for i in range(N,0,-1):
        if i%2 == 1:
            Back.append(Back[-1])
            continue
        if i == N-1:
            Back.append(A[i-1])
            continue
        Back.append( max(Back[-1], OddSum[-1] - OddSum[i+2]) + A[i-1])

    # if ans < Head[-1]:
    #     ans = Head[-1]
    # if ans < Back[-1]:
    #     ans = Back[-1]
    for i in range(2,N+1,2):
        if ans < Head[i] + Back[N-1-i]:
            ans = Head[i] + Back[N-1-i]
        if ans < Head[i] + Back[N+1-i] - A[i-1]:
            ans = Head[i] + Back[N+1-i] - A[i-1]
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
ans = 0
if n % 2 == 0:
  b = []
  for i in range(n//2):
    ans += a[2*i]
    b.append(a[2*i+1] - a[2*i])
  #print(b)
  for i in range(1,n//2)[::-1]:
    b[i-1] += b[i]
  #print(b)
  b.append(0)
  print(ans + max(b))
else:
  b = []
  c = []
  for i in range(n//2):
    ans += a[2*i]
    b.append(a[2*i+1] - a[2*i])
    c.append(a[2*i+2] - a[2*i+1])
  for i in range(1,n//2)[::-1]:
    b[i-1] += b[i]
    c[i-1] += c[i]
  #print(b)
  #print(c)
  d = c[:]
  for i in range(1,n//2)[::-1]:
    d[i-1] = max(d[i-1],d[i],0)
  #print(d)
  e = []
  for i in range(n//2):
    e.append(b[i]+d[i])
  #print(ans)
  e.append(0)
  print(ans + max(e))

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 = max(prefix[-1], prefix[-2])

    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 - 2])
            dp[2][i] = dp[2][i - 2] + nums[i] # ok
    print(max(dp[1][-1], dp[2][-3], dp[1][-2]))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
if N%2 == 0:
    O = [0] * (N//2+1)
    E = [0] *(N//2+1)
    for i in range(N//2):
        E[i+1] = E[i] + A[2*i]
        O[i+1] = O[i] + A[N-1-2*i]
    ans = 0
    for i in range(N//2+1):
        ans = max(ans, E[i] + O[N//2-i])
    print(ans)
else:
    ans = 0
    Min = 10**10
    for i in range(N//2+1):
        Min = min(Min, A[2*i])
        ans += A[2*i]
    ans -= Min
    O = [0] * (N//2+1)
    E = [0] *(N//2+1)
    for i in range(N//2):
        E[i+1] = E[i] + A[2*i]
        O[i+1] = O[i] + A[N-1-2*i]
    Max = [0, 0]
    li1 = []
    li1.append(Max)
    for i in range(N//2):
        if Max[1] == 0:
            if A[2*i] >= A[2*i+1]:
                Max = [Max[0]+A[2*i], 0]
            else:
                Max = [Max[0]+A[2*i+1], 1]
        else:
            if E[i] + A[2*i] >= Max[0] + A[2*i+1]:
                Max = [E[i] + A[2*i], 0]
            else:
                Max = [Max[0]+A[2*i+1], 1]
        li1.append(Max)
    Max = [0,0]
    li2 = [[0,0]]
    for i in range(N//2):
        if Max[1] == 0:
            if A[N-1-2*i] >= A[N-1-2*i-1]:
                Max = [Max[0]+A[N-1-2*i], 0]
            else:
                Max = [Max[0]+A[N-1-2*i-1], 1]
        else:
            if O[i] + A[N-1-2*i] >= Max[0] + A[N-1-2*i-1]:
                Max = [O[i] + A[N-1-2*i], 0]
            else:
                Max = [Max[0]+A[N-1-2*i-1], 1]
        li2.append(Max)
    for i in range(N//2+1):
        Max = li1[i] 
        if Max[1] == 1:
            ans = max(ans, Max[0]+li2[N//2-i][0])
        else:
            ans = max(ans, Max[0]+li2[N//2-i][0])
    print(ans)

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 - 2):
			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())
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 = max(sum(a[2::2]), sum(a[0:-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 + 1):
        ans = max(ans, patb[i] + pata[n // 2 + 1] - pata[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])
        ans=max(ans,tmp)
    for i in range(1,n,2):
        tmp=(acum2[i]-acum2[0])+(acum1[-1]-acum1[i])
        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])+acummax[i]
        ans=max(ans,tmp)
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a = list(map(int,input().split()))
a0 = [0] * (n//2+1)
a1 = [0] * (n//2+1)
for i in range(n//2):
    a0[i+1] = a0[i] + a[i*2]
if n% 2 != 0:
    a0.append(a0[-1] + a[-1])

max_even = [0] * (n//2+1)
for i in range(n//2):
    max_even[i+1] = max(max_even[i]+a[2*i+1], a0[i+1])

ans = 0
if n%2 == 0:
    ans = max_even[-1]
else:
    for i in range(0,n//2+1):
        ans = max(ans, max_even[i] + a0[-1] - a0[i+1])
print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
def main():
    N = int( input())
    A = list( map( int, input().split()))
    if N == 2:
        print(A[0], A[1])
        return
    OddSum = [0]
    EvenSum = [0]
    for i in range(N):
        if i%2 == 0:
            OddSum.append(OddSum[-1] + A[i])
            EvenSum.append(EvenSum[-1])
        else:
            OddSum.append(OddSum[-1])
            EvenSum.append(EvenSum[-1] + A[i])
    if N%2 == 0:
        ans = max(OddSum[-1], EvenSum[-1])
        for i in range(1,N,2):
            t = EvenSum[-1] - EvenSum[i+1] + OddSum[i] - OddSum[0]
            if ans < t:
                ans = t
        print(ans)
        return

    ans = max( EvenSum[-1], OddSum[-1] - min(A[::2]))
    Head = [0]
    for i in range(1,N+1):
        if i%2 == 1:
            Head.append(Head[-1])
            continue
        if i == 2:
            Head.append(A[i-1])
            continue
        Head.append( max(Head[-1], OddSum[i-2]) + A[i-1])

    Back = [0]
    for i in range(N,0,-1):
        if i%2 == 1:
            Back.append(Back[-1])
            continue
        if i == N-1:
            Back.append(A[i-1])
            continue
        Back.append( max(Back[-1], OddSum[-1] - OddSum[i+2]) + A[i-1])

    # if ans < Head[-1]:
    #     ans = Head[-1]
    # if ans < Back[-1]:
    #     ans = Back[-1]
    for i in range(2,N+1,2):
        if ans < Head[i] + Back[N-1-i]:
            ans = Head[i] + Back[N-1-i]
        if ans < Head[i] + Back[N+2-i] - A[i-1]:
            ans = Head[i] + Back[N+2-i] - A[i-1]
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math
from math import gcd

N = int(input())
s = input().split()
p = [int(w) for w in s] #これで勝手にNまで拾ってくれます
#print(p)

if(N % 2 == 0):
    #print(p[0:N:2])
    #print(p[1:N+1:2])
    ans = max(sum(p[0:N:2]) , sum(p[1:N+1:2]))
    print(ans)

#else:
else:
    print(sum(p))