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 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**18]*3, [-10**18]*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][1][2], dp[n][0][1]))


main()

Submission status: Wrong Answer

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

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

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

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

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


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

    print(ans)

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

    print(ans)

Submission status: Wrong Answer

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

if N%2==0:
    odd=0
    even=0
    for i in range(N):
        if i%2==0:
            odd += A[i]
        else:
            even += A[i]
    print(max(odd,even))

else:
    r1=0
    r2=0
    r3=0
    for i in range(N//2):
        r1+=A[2*i]
        r2+=A[2*i+1]
        r3+=A[2*i+2]
    print(max(r1,r2,r3))

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)
    print(li1)
    print(li2)
    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 numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

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

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
        c = -10**24
        for j in range(i * 2, n):
            c = max(c, a[j - 2])
            b[j] = c + d[j]

        a = b.copy()
    print(a[-1])
    exit()
    
b = a[:20]
e = [True]*20

for i in range(1, n // 2):
    c = [0] * 20
    f = [False]*20
    d = -10**24
    for j in range(20):
        if 2 * i + j >= n:
            continue
        if not e[j]:
            continue
        d = max(d, b[j])
        c[j] = d + a[2 * i + j]
        f[j] = True
    e = f.copy()
    b = c.copy()
ans = -10 ** 24
for i in range(20):
    if e[i]:
        ans = max(ans, b[i])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i, v in enumerate(list(map(int, input().split()))):
    A.append([i, v])

A.sort(key=lambda x:x[1], reverse=True)
idx = set()
ans = 0
cnt = 0
for i in A:
    if i[0] in idx:
        continue
    idx.add(i[0])
    idx.add(i[0]+1)
    idx.add(i[0]-1)
    ans += i[1]
    cnt += 1
    if cnt == N//2:
        break

print(ans)

Submission status: Wrong Answer

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

s=0
for i in range(len(A)):
    s+=int(A[i])

if n%2==0:
    ss=0
    for i in range(int(len(A)//2)):
        ss+=int(A[2*i])
    print(max(ss,s-ss))
else:
    m=0
    for i in range(int(n//2)):
        m+=int(A[2*i+1])
    L=[]
    a=int(A[0])
    for i in range(int(n//2)-1):
        a+=int(A[2*i+3])
    L.append(a)
    for i in range(int(n//2)-1):
        L.append(L[i]-int(A[2*i+3])+int(A[2*i+2]))
    m=max(m,max(L))
    LL=[]
    b=0
    for i in range(int(n//2)):
        b+=int(A[2*i+2])
    LL.append(b)
    for i in range(int(n//2)-1):
        LL.append(LL[i]-int(A[2*i+2])+int(A[2*i+1]))
    m=max(m,max(LL))
    print(m)

Submission status: Wrong Answer

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

ans = 0
idx = [n for n in reversed(range(0 if N % 2 != 0 else 1, N, 2))][:N//2]
print(sum([ A[i] for i in idx ]))

Submission status: Wrong Answer

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


if n%2==0:
    tmp1=0
    tmp2=0
    for i in range(0,n,2):
        tmp1+=a[i]
    for i in range(1,n,2):
        tmp2+=a[i]
    ans=max(tmp1,tmp2)
else:
    tmp_max=s = [[] for i in range(n//2)]
    for i in range(n//2):
        if i==0:
            for j in range(0,n-1,2):
                tmp_max[i].append(max(a[j],a[j+1],a[j+2]))
        else:
            for j in range(n//2-i):
                tmp_max[i].append(max(tmp_max[i-1][j]+a[2*i+2+2*j],tmp_max[i-1][j+1]+a[2*j]))
    ans = tmp_max[n//2-1][0]
    
print(ans)

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

print(ans)

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(1, n-2, 2):
            index = s[i]
            if i == index:
                continue
            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:
N = int(input())
A = list(map(int, input().split()))

if N % 2 == 0:#Nが偶数
  x = int(N / 2)
  odd = [0] * x
  even = [0] * x
  for i in range(N):
    if i % 2 == 0:
      odd[int(i / 2)] = A[i]
    else:
      even[int((i - 1) / 2)] = A[i]
  ans = 0
  
  for i in range(x + 1):
    ans2 = sum(odd[:i]) + sum(even[i:])
    ans = max(ans, ans2)
      
  print(ans)
  
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())
A = list(map(int, input().split()))
dp = [0]*N
dp[1] = max(A[0],A[1])
k = A[0]
i = 1

while(i<N-1):
  if i%2 == 0:#追加なし　奇数
    dp[i+1] = max(dp[i-1]+A[i+1],k)
    k += A[i]
  else:#追加あり　偶数
    dp[i+1] = max(dp[i-1]+A[i+1],dp[i])
  i += 1
  
print(dp[N-1])

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

Submission status: Wrong Answer

Solution code:
n = int(input())
#n > 1
a = [int(i) for i in input().split()]
a_odd = []
a_even = []

odd_acc = [0]
even_acc = [0]

for i in range(n):
    if i % 2 == 0:
        a_even.append(a[i])
        even_acc.append(even_acc[-1]+a[i])
    else:
        a_odd.append(a[i])
        odd_acc.append(odd_acc[-1]+a[i])

odd_acc_rev = [0]
even_acc_rev = [0]

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

if n % 2 == 0:
    ans = -10**15
    for i in range(len(a_odd)):
        if i != len(a_odd)-1:
            ans = max(ans,odd_acc[i+1]+ even_acc[-1] - even_acc[i+2])
        else:
            ans = max(ans,odd_acc[i+1])
    print(ans)
else:
    ans = -10**15
    for i in range(len(a_odd)):
        if i != len(a_odd)-1:
            ans = max(ans,odd_acc[i+1]+ even_acc[-1] - even_acc[i+2])
        else:
            ans = max(ans,odd_acc[i+1])
        #print(ans)
    for i in range(len(a_odd)):
        if i != len(a_odd)-1:
            ans = max(ans,even_acc_rev[i+1]+ odd_acc_rev[-1] - odd_acc_rev[i+2])
        else:
            ans = max(ans,even_acc_rev[i+1])
        #print(ans)

    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))
A = np.array(A)
A1 = A[0:N:2]
cand = []
cand.append(np.sum(A1))
cand.append(np.sum(A)-cand[0])
if N%2==0:
    print(max(cand))
    exit()
A2 = A[1:N-1:2]
ans = np.sum(A2)
for i in range(N//2+1):
    for j in range(i, N//2+1):
        ans = max([ans, np.sum(A1[:i])+np.sum(A2[i:j])+np.sum(A1[j+1:])])
print(ans)

Submission status: Wrong Answer

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

# even
if n % 2 ==0: 
    pat0 = 0
    pat1 = 0
    for i in range(n//2):
        pat0 += a[i*2]
        pat1 += a[i*2 + 1]
    print (max(pat0, pat1))
# odd
else:
    length = n//2 # 何個選ぶべきか
    # ずらす点0
    pat0 = 0
    pat1 = 0
    for i in range(length):
        pat0 += a[i*2]
        pat1 += a[i*2 + 1]
    pat2 = pat0 - a[0] + a[-1]
    s0max = max(pat0,pat1,pat2)
    # ずらす点1
    s1max = 0
    for shift in range(length):
        pat3 = 0
        pat4 = 0
        hosei = 0
        for i in range(length):
            if i >= shift:
                hosei = 1
            pat3 += a[i*2 + hosei]
            pat4 += a[i*2 + 1 + hosei]
        s1max = max(s1max, pat3, pat4)
    # ずらす点2
    s2max=0
    for shift in range(length):
        for shift2 in range(shift, length):
            pat5 = 0
            for i in range(length):
                hosei = 0
                if i >= shift:
                    hosei += 1
                if i>= shift2:
                    hosei += 1
                pat5 += a[i*2 + hosei]
            s2max = max(s2max, pat5)
    print (max(s1max, s2max,s0max))

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

if N % 2 == 0:
    even = A[::2]
    odd = A[1::2]
    assert len(even) == len(odd) == N // 2
    print(max(sum(even), sum(odd)))
    exit()


@lru_cache(maxsize=None)
def dp(i, numSkips):
    if i < 0:
        if numSkips == 0:
            return 0
        return float('-inf')
    best = A[i] + dp(i - 2, numSkips)
    if numSkips >= 1:
        best = max(best, A[i] + dp(i - 3, numSkips - 1))
    if numSkips >= 2:
        best = max(best, A[i] + dp(i - 4, numSkips - 2))
    return best


# Warm cache
for i in range(N):
    dp(i, 0)
    dp(i, 1)
    dp(i, 2)

print(max(dp(N - 1, 2), dp(N - 2, 1), dp(N - 3, 0)))

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
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])
            ans = max(ans,tmp)
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 - 1):
            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:
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])
            ans = max(ans,tmp)
print(ans)

Submission status: Wrong Answer

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

if N % 2:
    dp = [0] * N
    for i in range(N):
        if i == 0 or i == 1:
            dp[i] = A[i]
        if i == 3:
            dp[i] = dp[i - 2] + A[i]
        else:
            dp[i] = max(dp[i - 2] + A[i], dp[i - 3] + A[i])
    print(max(dp[-1], dp[-2], dp[-3]))
else:
    print(max(sum(A[::2]), sum(A[1::2])))

Submission status: Wrong Answer

Solution code:
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]
    print(ans)
    
if __name__ == '__main__':
    main()

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][1][2], dp[n][0][1]))


main()

Submission status: Wrong Answer

Solution code:
n = int(input())
#n > 1
a = [int(i) for i in input().split()]
a_odd = []
a_even = []

odd_acc = [0]
even_acc = [0]

for i in range(n):
    if i % 2 == 0:
        a_even.append(a[i])
        even_acc.append(even_acc[-1]+a[i])
    else:
        a_odd.append(a[i])
        odd_acc.append(odd_acc[-1]+a[i])

odd_acc_rev = [0]
even_acc_rev = [0]

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

if n % 2 == 0:
    ans = -10**15
    for i in range(len(a_odd)):
        if i != len(a_odd)-1:
            ans = max(ans,odd_acc[i+1]+ even_acc[-1] - even_acc[i+2])
        else:
            ans = max(ans,odd_acc[i+1])
    print(ans)
else:
    ans = -10**15
    for i in range(len(a_odd)):
        if i != len(a_odd)-1:
            ans = max(ans,odd_acc[i+1]+ even_acc[-1] - even_acc[i+2])
        else:
            ans = max(ans,odd_acc[i+1])
        #print(ans)
    for i in range(len(a_odd)):
        if i != len(a_odd)-1:
            ans = max(ans,even_acc_rev[i+1]+ odd_acc_rev[-1] - odd_acc_rev[i+2])
        else:
            ans = max(ans,even_acc_rev[i+1])
        #print(ans)

    print(ans)

Submission status: Wrong Answer

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

if n % 2 == 0:
    ans = max(sum(a[::2]), sum(a[1::2]))
else:
    ans = 0
    for i in range(n):
        mae = a[:i]
        ato = a[i+1:]
        this_ans = 0
        if i % 2:
            this_ans = max( sum(mae[::2]), sum(mae[1::2]) ) + max( sum(ato[::2]), sum(ato[1::2]) ) 
        else:
            this_ans = max( sum(mae[::2]) + sum(ato[1::2]) , sum(mae[1::2]) + sum(ato[::2]))
        ans = max(this_ans, ans)

print(ans)

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)
  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])
  #print(d)
  e = []
  for i in range(n//2):
    e.append(b[i]+d[i])
  #print(ans)
  print(ans+max(e))

Submission status: Wrong Answer

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

if n//2==n/2:
    m=sum(l[1::2])
    mx=m
    for i in range(0,n,2):
        m=m+l[i]-l[i+1]
        mx=max(m,mx)
else:
    ll=l[:]
    lm=[]

    for j in range(1,n,2):
        l=l[:n-j]
        m=sum(l[1::2])
        mx=m
        for i in range(0,n-j,2):
            m=m+l[i]-l[i+1]
            mx=max(m,mx)
        lm.append(mx+sum(ll[n-j::2]))
    mx=max(lm)
print(mx)

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

print(ans)

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

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

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

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

a = onem()

n = l()

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

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

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



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

Submission status: Wrong Answer

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

b = min(A[0::2])
c = min(A[1::2])
d = sum(A[0::2])
e = sum(A[1::2])

if N%2 != 0:
    d -= b
    e -= c

print(max(d,e))

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
        c = -10**24
        for j in range(i * 2, n):
            c = max(c, a[j - 2])
            b[j] = c + d[j]

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

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