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

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(le_o[-1], le_o[-1] + a[2*i+1] - a[2*i]))


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

    print(ans)

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

    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(le_o[-1], 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 = le[n]
    for i in range(0, n + 1):
        ans = max(ans, le[i] + ro[n-i])

    print(ans)

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

    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
if n <= 3:
  print(max(a))
  exit()

a = tuple(a)
dp = [[-10**15]*3 for i in range(n)]
dp[0][2] = a[0]
dp[1][2] = a[1]
dp[2][2] = a[0]+a[2]
dp[3][2] = max(a[0],a[1])+a[3]
dp[3][1] = a[0]+a[3]
for i in range(2,n-2):
  if i%2 == 0:
    dp[i+2][2] = dp[i][2]+a[i+2]
  else:
    dp[i+2][2] = max(dp[i][2],dp[i-1][2])+a[i+2]
  dp[i+2][1] = max(dp[i][1]+a[i+2],dp[i-1][2]+a[i+2])
  dp[i+2][0] = max(dp[i][0]+a[i+2],dp[i-1][1]+a[i+2],dp[i-2][2]+a[i+2])
if i%2 == 0:
  c = min(a[0],a[-1])
  dp[n-1][2] -= c
print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [[[0,0] for _ in range(N+1)] for _ in range(N+1)]
dp[1][1][0] = A[0]
dp[1][1][1] = 1
if dp[1][1][0]<A[1]:
  dp[2][1][0] = A[1]
  dp[2][1][1] = 1
else:
  dp[2][1][0] = dp[1][1][0]

for i in range(2,N):
  a = A[i]
  ma = (i+2)//2
  mi = i//2
  if dp[i][ma-1][1]:
    if dp[i][ma][0]<dp[i-1][ma-1][0] + a:
      dp[i+1][ma][0] = dp[i-1][ma-1][0]+a
      dp[i+1][ma][1] = 1
    else:
      dp[i+1][ma][0] = dp[i][ma][0]
  else:
    dp[i+1][ma][0] = dp[i][ma-1][0] + a
    dp[i+1][ma][1] = 1
    
  if dp[i][mi-1][1]:
    if dp[i][mi][0]<dp[i-1][mi-1][0] + a:
      dp[i+1][mi][0] = dp[i-1][mi-1][0]+a
      dp[i+1][mi][1] = 1
    else:
      dp[i+1][mi][0] = dp[i][mi][0]
  else:
    dp[i+1][mi][0] = dp[i][mi-1][0] + a
    dp[i+1][mi][1] = 1
    
print(dp[-1][N//2][0])

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 = []
    even = []
    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
            even.append(A[i])
    
    s = 0
    ans = sum(odd)

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(2*1000000)

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

dp_dict = {}


def dp(i, j):
    if i >= N:
        return (-1*1000000000)
    if (N//2)-j < (i-1)//2:
        return (-1*1000000000)
    if j == 1:
        return A[i]
    if (i, j) in dp_dict:
        return dp_dict[(i, j)]
    else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        dp_dict[(i, j)] = temp
        return temp


select = N//2
if select == 1:
    print(max(A))
else:
    print(dp(0, select))

Submission status: Wrong Answer

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

if N%2 == 0:
    List=[]
    for i in range(1+(N//2)):
        sumd = 0
        for j in range(i):
            sumd = sumd + A[2*j]
        for j in range(i,N//2):
            sumd = sumd + A[1+2*j]
        List.append(sumd)
    print(max(List))    
else:
    print(0)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [[[0,0] for _ in range(N+1)] for _ in range(N+1)]
dp[1][1][0] = A[0]
dp[1][1][1] = 1
if dp[1][1][0]<A[1]:
  dp[2][1][0] = A[1]
  dp[2][1][1] = 1
else:
  dp[2][1][0] = dp[1][1][0]

for i in range(2,N):
  a = A[i]
  ma = (i+2)//2
  mi = i//2
  if dp[i][ma-1][1]:
    if dp[i][ma][0]<dp[i-1][ma-1][0] + a:
      dp[i+1][ma][0] = dp[i-1][ma-1][0]+a
      dp[i+1][ma][1] = 1
    else:
      dp[i+1][ma][0] = dp[i][ma][0]
  else:
    dp[i+1][ma][0] = dp[i][ma-1][0] + a
    dp[i+1][ma][1] = 1
    
  if dp[i][mi-1][1]:
    if dp[i][mi][0]<dp[i-1][mi-1][0] + a:
      dp[i+1][mi][0] = dp[i-1][mi-1][0]+a
      dp[i+1][mi][1] = 1
    else:
      dp[i+1][mi][0] = dp[i][mi][0]
  else:
    dp[i+1][mi][0] = dp[i][mi-1][0] + a
    dp[i+1][mi][1] = 1
    
print(dp[-1][N//2][0])

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
lim=n%2+2
dp=[[0]*lim for _ in range(n+1)]
for i in range(n):
  dp[i+1][0]=dp[i-1][0]+arr[i]
  dp[i+1][1]=max(dp[i-1][1]+arr[i],dp[i-2][0]+arr[i])
  if lim==3:
    dp[i+1][2]=max(dp[i-1][2]+arr[i],dp[i-2][1]+arr[i],dp[i-3][0]+arr[i])
print(max(dp[-1][:lim]))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(2*100000)
N = int(input())
A = list(map(int, input().split(" ")))

dp_dict = {}


def dp(i, j):
    if i >= N:
        return (-1*1000000000)-1
    if j == 1:
        return A[i]
    if (i, j) in dp_dict:
        return dp_dict[(i, j)]
    else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        dp_dict[(i, j)] = temp
        return temp


print(dp(0, (N//2)))

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
dp=[[0]*3 for _ in range(n+1)]
for i in range(n):
  dp[i+1][0]=dp[i-1][0]+arr[i]
  dp[i+1][1]=max(dp[i-1][1]+arr[i],dp[i-2][0]+arr[i])
  dp[i+1][2]=max(dp[i-1][2]+arr[i],dp[i-2][1]+arr[i],dp[i-3][0]+arr[i])
print(max(dp[-1]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N = int(input())
lst = list(map(int,input().split()))
if N % 2 == 0:
    k = sum(lst[::2])
    l = sum(lst[1::2])
else:
    k = sum(lst[::2])-min(lst[::2])
    l = sum(lst[1::2])-min(lst[1::2])
print(k if k>=l else l)

Submission status: Wrong Answer

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

dp = [0] * (N + 1)
dp[2] = max(A[0], A[1])
s = 0
for i, a in enumerate(A, 1):
  if i <= 2:
    continue
  if i%2: # 奇数
    dp[i] = max(dp[i-1], a+dp[i-2])
    s += a
  else: # 偶数
    dp[i] = max(a+dp[i-2], s)

print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
inf = 10 ** 16
if N % 2:
  dp = [[-inf] * 3 for _ in range(N + 2)]
  dp[0][0] = 0
  dp[1][1] = 0
  dp[2][2] = 0
  if N > 4: dp[4][2] = a[0]
  for i in range(N):
    for j in range(3):
      if dp[i][j] == -inf: continue
      if i + 2 <= N + 1: dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + a[i])
      if i + 3 <= N + 1 and (j < 2): dp[i + 3][j + 1] = max(dp[i + 3][j + 1], dp[i][j] + a[i])
      if i + 4 <= N + 1 and (j == 0): dp[i + 4][j + 1] = max(dp[i + 4][j + 1], dp[i][j] + a[i])
  print(max(dp[-1][-1], dp[-2][-2], dp[-3][-3]))
  #print(dp)
else:
  x = 0
  y = 0
  for i in range(N):
    if i % 2: x += a[i]
    else: y += a[i]
  print(max(x, y))

Submission status: Wrong Answer

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

if N % 2 == 1:
    ans_1 = 0
    ans_2 = 0
    ans_3 = 0
    for i in range(0,N-1,2):
        ans_1 += a_list[i]
        #print(i)
    for j in range(1,N,2):
        ans_2 += a_list[j]
    for k in range(2,N+1,2):
        ans_3 += a_list[k]
    print(max(ans_1,ans_2,ans_3))
else:
    ns_1 = 0
    ns_2 = 0
    for i in range(0,N,2):
        ns_1 += a_list[i]
        #print(i)
    for j in range(1,N+1,2):
        ns_2 = (ns_2 + (a_list[j]))
        #print(a_list[j])
    print(max(ns_2,ns_1))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
inf = 10 ** 16
if N % 2:
  dp = [[-inf] * 3 for _ in range(N + 2)]
  dp[0][0] = 0
  dp[1][1] = 0
  dp[2][2] = 0
  for i in range(N):
    for j in range(3):
      if dp[i][j] == -inf: continue
      if i + 2 <= N + 1: dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + a[i])
      if i + 3 <= N + 1 and (j < 2): dp[i + 3][j + 1] = max(dp[i + 3][j + 1], dp[i][j] + a[i])
      if i + 4 <= N + 1 and (j == 0): dp[i + 4][j + 1] = max(dp[i + 4][j + 1], dp[i][j] + a[i])
  print(max(dp[-1][-1], dp[-2][-2], dp[-3][-3]))
else:
  x = 0
  y = 0
  for i in range(N):
    if i % 2: x += a[i]
    else: y += a[i]
  print(max(x, y))

Submission status: Wrong Answer

Solution code:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# import itertools
# from operator import attrgetter, itemgetter
# import math

# from numba import jit
# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = [0] + list(map(int, readline().split()))

    if n % 2 == 0:
        ans1 = sum(a[::2])
        ans2 = sum(a[1::2])
        print(max(ans1, ans2))
        sys.exit()

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

    # 普通に選ぶ場合
    dp[1][0] = 0
    dp[2][0] = max(a[1], a[2])
    dp[3][0] = max(a[1], a[2], a[3])

    # 1個多く選ぶ場合（奇数個のみ）
    dp[1][1] = a[1]
    dp[3][1] = a[1] + a[3]

    i = 4

    while i < n + 1:
        cur1 = a[i]

        # 偶数だよ
        dp[i][0] = max(dp[i - 1][1], dp[i - 2][0] + cur1)

        i += 1
        cur2 = a[i]

        # 奇数だよ
        dp[i][0] = max(dp[i - 2][0] + cur2, dp[i - 3][0] + cur2, dp[i - 1][0], dp[i - 2][1])
        dp[i][1] = dp[i - 2][1] + cur2

        i += 1

    print(dp[n][0])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
if n%2==0:
  dp=[[0 for i in range(2)] for j in range(n)]
  dp[0][0]=a[0]
  dp[1][1]=a[1]
  for i in range(2,n):
    if i==2:
      dp[i][0]=dp[i-2][0]+a[i]
      dp[i][1]=dp[i-2][1]+a[i]
    else:
      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:
  dp=[[0 for i in range(3)] for j in range(n)]
  dp[0][0]=a[0]
  dp[1][1]=a[1]
  dp[2][2]=a[2]
  for i in range(2,n):
    if i==2:
      dp[i][0]=dp[i-2][0]+a[i]
      dp[i][1]=dp[i-2][1]+a[i]
    else:
      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],dp[i-4][0])+a[i]
  print(dp[n-1][2])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin


def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    if n % 2 == 0:
        v = [[None for j in range(2)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        for i in range(2, n):
            for j in range(2):
                c = []
                if v[i-2][j] is not None:
                    c.append(v[i-2][j])
                if j >= 1 and i >= 3:
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(2) if v[n-1][j] is not None]
        print(max(c))
    else:
        v = [[None for j in range(3)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        v[2][0] = a[0]+a[2]
        v[2][2] = a[2]
        for i in range(3, n):
            for j in range(3):
                c = []
                if v[i-2][j] is not None:
                    c.append(v[i-2][j])
                if j >= 1:
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                if j >= 2 and i >= 4:
                    if v[i-4][j-2] is not None:
                        c.append(v[i-4][j-2])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(1, 3) if v[n-1][j] is not None]
        print(max(c))


def input(): return stdin.readline().rstrip()


main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
inf = 10 ** 16
if N % 2:
  dp = [[-inf] * 3 for _ in range(N + 2)]
  dp[0][0] = 0
  dp[1][1] = 0
  dp[2][2] = 0
  for i in range(N):
    for j in range(3):
      if dp[i][j] == -inf: continue
      if i + 2 <= N + 1: dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + a[i])
      if i + 3 <= N + 1 and (j < 2): dp[i + 3][j + 1] = max(dp[i + 3][j + 1], dp[i][j] + a[i])
  print(max(dp[-1][-1], dp[-2][-2], dp[-3][-3]))
else:
  x = 0
  y = 0
  for i in range(N):
    if i % 2: x += a[i]
    else: y += a[i]
  print(max(x, y))

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect

sys.setrecursionlimit(10 ** 8)
# mem = {}

M = 10 ** 9 + 7


def gu(A):
    # aa = sum([a for (i, a) in enumerate(A) if i % 2 == 0])
    bb = sum([a for (i, a) in enumerate(A) if i % 2 == 1])

    t = bb
    maxcc = None
    for i in range(2, len(A)+1, 2):
        t = t - A[i - 1] + A[i - 2]
        if maxcc is None:
            maxcc = t
        else:
            maxcc = max(maxcc, t)

    return max(bb, maxcc) if maxcc is not None else bb


def ki(A):
    return sum([a for (i, a) in enumerate(A) if i % 2 == 0])


def main():
    N = int(input())
    A = [int(a) for a in input().split()]

    if N % 2 == 0:
        print(gu(A))
        return

    max_v = None

    for i in range(N - 1):
        if i % 2 == 0:
            aa = gu(A[:i])
            bb = ki(A[i + 2:])
            # print(aa + bb)
            max_v = max(max_v, aa + bb) if max_v is not None else aa + bb
        else:
            aa = ki(A[:i])
            bb = gu(A[i + 2:])
            # print(aa + bb)
            max_v = max(max_v, aa + bb) if max_v is not None else aa + bb
    print(max_v)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
def main():
    N = int(stdin.readline())
    A = list(map(int, stdin.readline().rstrip().split()))
    dp = [0] * N
    dp[1] = max(A[0], A[1])
    for i in range(2, N):
        if i & 1 == 0:
            dp[i] = max(dp[i-1], A[i] + dp[i-2])
        else:
            dp[i] = A[i] + dp[i-2]
    ret=dp[N-1]
    stdout.write(str(ret)+"\n")
main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N==2:
    print(max(A))
elif N==3:
    print(max(A))
else:
    if N%2==1:
        dp=[[0 for i in range(0,3)] for i in range(0,N)]
        dp[0][2]=A[0]
        dp[0][1]=-float('inf')
        dp[0][0]=-float('inf')
        dp[1][2]=-float('inf')
        dp[1][1]=A[0]
        dp[1][0]=-float('inf')

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

        test1=dp[N-1][0]

        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=-float('inf')
        dp[0][0]=0
        dp[1][1]=A[1]
        dp[1][0]=-float('inf')

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

        test2=dp[N-1][0]

        A=A[::-1]
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=-float('inf')
        dp[0][0]=0
        dp[1][1]=A[1]
        dp[1][0]=-float('inf')

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

        test3=dp[N-1][0]

        test4=sum(A[i] for i in range(0,N) if i%2==1)

        print(max(test1,test2,test3,test4))

    if N%2==0:
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=A[0]
        dp[0][0]=-float('inf')
        dp[1][1]=-float('inf')
        dp[1][0]=A[0]

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

        test1=dp[N-1][0]

        A=A[::-1]
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=A[0]
        dp[0][0]=-float('inf')
        dp[1][1]=-float('inf')
        dp[1][0]=A[0]

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

        test2=dp[N-1][0]

        test3=sum(A[i] for i in range(0,N) if i%2==0)
        test4=sum(A[i] for i in range(0,N) if i%2==1)

        print(max(test1,test2,test3,test4))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin


def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    if n % 2 == 0:
        v = [[None for j in range(2)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        for i in range(2, n):
            for j in range(2):
                c = []
                if v[i-2][j] is not None:
                    c.append(v[i-2][j])
                if j >= 1 and i >= 3:
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(2) if v[n-1][j] is not None]
        print(max(c))
    else:
        v = [[None for j in range(3)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        v[2][2] = a[2]
        for i in range(3, n):
            for j in range(3):
                c = []
                if v[i-2][j] is not None:
                    c.append(v[i-2][j])
                if j >= 1:
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                if j >= 2 and i >= 4:
                    if v[i-4][j-2] is not None:
                        c.append(v[i-4][j-2])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(3) if v[n-1][j] is not None]
        print(max(c))


def input(): return stdin.readline().rstrip()


main()

Submission status: Wrong Answer

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

sm_e = []
sm_o = []

e = 0
o = 0

for i in range(n):
    if i % 2 == 0:
        e += a[i]
        sm_e.append(e)
    else:
        o += a[i]
        sm_o.append(o)

tot_e = sm_e[-1]
tot_o = sm_o[-1]

m = len(sm_o)

if n % 2 == 0:
    ans = max(tot_e, tot_o)
    for i in range(m):
        ans = max(ans, sm_e[i] + tot_o - sm_o[i])
    # for i in range(m-1):
    #     ans = max(ans, sm_o[i] + tot_e - sm_e[i+1])
    print(ans)
    exit()

ans = tot_o

for i in range(m):
    if i != m-1:
        ans = max(ans, sm_e[i]+tot_o-sm_o[i])
    else:
        ans = max(ans, tot_o-a[-1])

l = [0]*m
for i in range(m):
    l[i] = sm_e[i]-sm_o[i]

val = l[0]
tmp = 0

for i in range(m-1):
    ans = max(ans, sm_o[i] + tot_e - sm_e[i+1])
    if i != 0:
        if val < l[i]:
            val = l[i]
    ans = max(ans, sm_o[i] + tot_e - sm_e[i+1] + val)

for i in range(n):
    if i % 2 == 0:
        ans = max(ans, tot_e - a[i])

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin


def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    if n % 2 == 0:
        v = [[None for j in range(2)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        for i in range(3, n):
            for j in range(2):
                c = []
                if v[i-2][j] is not None:
                    c.append(v[i-2][j])
                if j >= 1 and i >= 3:
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(2) if v[n-1][j] is not None]
        print(max(c))
    else:
        v = [[None for j in range(3)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        v[2][2] = a[2]
        for i in range(3, n):
            for j in range(3):
                c = []
                if v[i-2][j] is not None:
                    c.append(v[i-2][j])
                if j >= 1:
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                if j >= 2 and i >= 4:
                    if v[i-4][j-2] is not None:
                        c.append(v[i-4][j-2])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(3) if v[n-1][j] is not None]
        print(max(c))


def input(): return stdin.readline().rstrip()


main()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
if n%2==0:
    print(max(sum(l[::2]),sum(l[1::2])))
    exit()
rrec,rec=0,0
rrc,rc=0,0
z,q=[0]*n,[0]*n
rl=[0]*n
ll=[0]*n
for i in range(n):
    if (i%2):rec+=l[i]
    else:rc+=l[i]
    if (n-1-i)%2:rrec+=l[n-1-i]
    else:rrc+=l[n-1-i]
    rl[n-1-i]=max(rrec,rrc)
    z[n-1-i]=rrec;q[n-1-i]=rrc
    ll[i]=max(rec,rc)
ans=-float("INF")
for i in range(n):
    if i==0:max(ans,rl[i+1])
    elif i==n-1:
        ans=max(ans,ll[i-1])
    else:
        ans=max(ans,ll[i-1]+rl[i+1])
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
if n%2==0:
    print(max(sum(l[::2]),sum(l[1::2])))
    exit()
rrec,rec=0,0
rrc,rc=0,0
z,q=[0]*n,[0]*n
rl=[0]*n
ll=[0]*n
for i in range(n):
    if (i%2):rec+=l[i]
    else:rc+=l[i]
    if (n-1-i)%2:rrec+=l[n-1-i]
    else:rrc+=l[n-1-i]
    rl[n-1-i]=max(rrec,rrc)
    z[n-1-i]=rrec;q[n-1-i]=rrc
    ll[i]=max(rec,rc)
ans=float("INF")
for i in range(n):
    if i==0:max(ans,rl[i+1])
    elif i==n-1:
        ans=max(ans,ll[i-1])
    else:
        ans=max(ans,ll[i-1]+rl[i+1])
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(map(int,input().split()))
import numpy as np
get_DP  = [[-np.inf for i in range(3)] for j in range(N)]
pass_DP = [[-np.inf for i in range(3)] for j in range(N)]
for i in range(N):
    # 常にとるやつ
    get_DP[i][0] = (pass_DP[i-1][0] if i>0 else 0) + S[i] 
    pass_DP[i][0] = get_DP[i-1][0]
    if i>0:
        get_DP[i][1] = (pass_DP[i-1][1] if i!=1 else 0) + S[i]
        pass_DP[i][1] = max(pass_DP[i-1][0], get_DP[i-1][1])
    if i>1:
        get_DP[i][2] = (pass_DP[i-1][2] if i!=2 else 0) + S[i]
        pass_DP[i][2] = max(pass_DP[i-1][1], get_DP[i-1][2])

    
print(max(get_DP[-1]+pass_DP[-1]))