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:
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
"""
n = onem()
a = l()


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

    ans = - Max
    co = 0
    for i in range(0,n,2):
        if i+1 <= n-1:
            ans = max(ans,co+po[i+1])
        else:
            ans = max(ans,co)
        co += a[i]
    co = 0
    for i in range(1,n,2):
        if i + 1 <= n-1:
            ans = max(ans,co+po[i+1])
        else:
            ans = max(ans,co)
        co += a[i]
    print(ans)

else:
    po = [a[i] for i in range(n)]
    mi = [-Max for i in range(n)]
    
    for i in range(n-3,-1,-1):
        po[i] += po[i+2]
    ans =  sum(a[1::2])
    #print(ans)
    l1 = [-Max for i in range(n)]
    for i in range(n):
        if i != n-1:
            l1[i] = po[i+1]

    """
    co = 0
    for i in range(0,n,2):
        if i != n-1:
            l1[i] = co + po[i+1]
        else:
            l1[i] = co
        co += a[i]
    co = 0
    for i in range(1,n,2):
        if i != n-1:
            l1[i] = co + po[i+1]
        else:
            l1[i] = co
        co += a[i]
    """

    for i in range(n-1,-1,-1):
        if i == n-1:
            continue
        elif i == n-2:
            mi[i] = l1[i]
        else:
            mi[i] = max(mi[i+2]+a[i],l1[i])


    l1 = mi


    """
    for i in range(n-1,-1,-1):
        if i <= n-3:
            mi[i] = min(mi[i+2],a[i])
        else:
            mi[i] = a[i]
    print(mi)
    """
    
    l2 = [-Max for i in range(n)]
    
    for i in range(n-1,-1,-1):
        l2[i] = po[i]
        
    #print(l1)
    #print(l2)
    co = 0

    for i in range(0,n,2):
        if i + 2 <= n-1:
            #print(ans,co+l1[i+1],co+l2[i+2])
            ans = max(ans,co+l1[i+1],co+l2[i+2])
        elif i+1 <= n-1:
            ans = max(ans,co+l1[i+1])
        else:
            ans = max(ans,co)
        
        co += a[i]
    co = 0
    #print(ans)
    for i in range(1,n,2):
        #print(ans,co+l1[i+1])
        ans = max(ans,co+po[i+1])
        #ans = max(ans,co+l1[i+1])
        co += a[i]
    #print("po:"+str(mi[1]))
    print(ans)

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
"""
n = onem()
a = l()


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

    ans = - Max
    co = 0
    for i in range(0,n,2):
        if i + 2 <= n-1:
            ans = max(ans,co+po[i+1],co+po[i+2])
        elif i+1 <= n-1:
            ans = max(ans,co+po[i+1])
        else:
            ans = max(ans,co+0)
        co += a[i]
    co = 0
    for i in range(1,n,2):
        if i + 1 <= n-1:
            ans = max(ans,co+po[i+1])
        else:
            ans = max(ans,co+0)
        co += a[i]
    print(ans)
    """
    print("po")

else:
    po = [a[i] for i in range(n)]
    mi = [-Max for i in range(n)]
    
    for i in range(n-3,-1,-1):
        po[i] += po[i+2]
    ans =  sum(a[1::2])
    #print(ans)
    l1 = [-Max for i in range(n)]
    for i in range(n):
        if i != n-1:
            l1[i] = po[i+1]

    """
    co = 0
    for i in range(0,n,2):
        if i != n-1:
            l1[i] = co + po[i+1]
        else:
            l1[i] = co
        co += a[i]
    co = 0
    for i in range(1,n,2):
        if i != n-1:
            l1[i] = co + po[i+1]
        else:
            l1[i] = co
        co += a[i]
    """

    for i in range(n-1,-1,-1):
        if i == n-1:
            continue
        elif i == n-2:
            mi[i] = l1[i]
        else:
            mi[i] = max(mi[i+2]+a[i],l1[i])


    l1 = mi


    """
    for i in range(n-1,-1,-1):
        if i <= n-3:
            mi[i] = min(mi[i+2],a[i])
        else:
            mi[i] = a[i]
    print(mi)
    """
    
    l2 = [-Max for i in range(n)]
    
    for i in range(n-1,-1,-1):
        l2[i] = po[i]
        
    #print(l1)
    #print(l2)
    co = 0

    for i in range(0,n,2):
        if i + 2 <= n-1:
            #print(ans,co+l1[i+1],co+l2[i+2])
            ans = max(ans,co+l1[i+1],co+l2[i+2])
        elif i+1 <= n-1:
            ans = max(ans,co+l1[i+1])
        else:
            ans = max(ans,co)
        
        co += a[i]
    co = 0
    #print(ans)
    for i in range(1,n,2):
        #print(ans,co+l1[i+1])
        ans = max(ans,co+po[i+1])
        #ans = max(ans,co+l1[i+1])
        co += a[i]
    #print("po:"+str(mi[1]))
    print(ans)

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
"""
n = onem()
a = l()


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

    ans = - Max
    co = 0
    for i in range(0,n,2):
        if i + 2 <= n-1:
            ans = max(ans,co+po[i+1],co+po[i+2])
        elif i+1 <= n-1:
            ans = max(ans,co+po[i+1])
        else:
            ans = max(ans,co+0)
        co += a[i]
    co = 0
    for i in range(1,n,2):
        if i + 1 <= n-1:
            ans = max(ans,co+po[i+1])
        else:
            ans = max(ans,co+0)
        co += a[i]
    print(ans)

else:
    po = [a[i] for i in range(n)]
    mi = [-Max for i in range(n)]
    
    for i in range(n-3,-1,-1):
        po[i] += po[i+2]
    ans =  sum(a[1::2])
    #print(ans)
    l1 = [-Max for i in range(n)]
    for i in range(n):
        if i != n-1:
            l1[i] = po[i+1]

    """
    co = 0
    for i in range(0,n,2):
        if i != n-1:
            l1[i] = co + po[i+1]
        else:
            l1[i] = co
        co += a[i]
    co = 0
    for i in range(1,n,2):
        if i != n-1:
            l1[i] = co + po[i+1]
        else:
            l1[i] = co
        co += a[i]
    """

    for i in range(n-1,-1,-1):
        if i == n-1:
            continue
        elif i == n-2:
            mi[i] = l1[i]
        else:
            mi[i] = max(mi[i+2]+a[i],l1[i])


    l1 = mi


    """
    for i in range(n-1,-1,-1):
        if i <= n-3:
            mi[i] = min(mi[i+2],a[i])
        else:
            mi[i] = a[i]
    print(mi)
    """
    
    l2 = [-Max for i in range(n)]
    
    for i in range(n-1,-1,-1):
        l2[i] = po[i]
        
    #print(l1)
    #print(l2)
    co = 0

    for i in range(0,n,2):
        if i + 2 <= n-1:
            #print(ans,co+l1[i+1],co+l2[i+2])
            ans = max(ans,co+l1[i+1],co+l2[i+2])
        elif i+1 <= n-1:
            ans = max(ans,co+l1[i+1])
        else:
            ans = max(ans,co)
        
        co += a[i]
    co = 0
    #print(ans)
    for i in range(1,n,2):
        #print(ans,co+l1[i+1])
        ans = max(ans,co+po[i+1])
        #ans = max(ans,co+l1[i+1])
        co += a[i]
    #print("po:"+str(mi[1]))
    print(ans)

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
"""
n = onem()
a = l()


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

    ans = - Max
    co = 0
    for i in range(0,n,2):
        if i + 2 <= n-1:
            ans = max(ans,co+po[i+1],co+po[i+2])
        elif i+1 <= n-1:
            ans = max(ans,co+po[i+1])
        else:
            ans = max(ans,co+0)
        co += a[i]
    co = 0
    for i in range(1,n,2):
        if i + 1 <= n-1:
            ans = max(ans,co+po[i+1])
        else:
            ans = max(ans,co+0)
        co += a[i]
    print(ans)

else:
    po = [a[i] for i in range(n)]
    mi = [-Max for i in range(n)]
    
    for i in range(n-3,-1,-1):
        po[i] += po[i+2]
    ans =  sum(a[1::2])
    #print(ans)
    l1 = [-Max for i in range(n)]
    for i in range(n):
        if i != n-1:
            l1[i] = po[i+1]
        else:
            l1[i] = 0
    """
    co = 0
    for i in range(0,n,2):
        if i != n-1:
            l1[i] = co + po[i+1]
        else:
            l1[i] = co
        co += a[i]
    co = 0
    for i in range(1,n,2):
        if i != n-1:
            l1[i] = co + po[i+1]
        else:
            l1[i] = co
        co += a[i]
    """

    for i in range(n-1,-1,-1):
        if i == n-1:
            mi[i] = 0
        elif i == n-2:
            mi[i] = l1[i]
        else:
            mi[i] = max(mi[i+2]+a[i],l1[i])


    l1 = mi


    """
    for i in range(n-1,-1,-1):
        if i <= n-3:
            mi[i] = min(mi[i+2],a[i])
        else:
            mi[i] = a[i]
    print(mi)
    """
    
    l2 = [-Max for i in range(n)]
    
    for i in range(n-1,-1,-1):
        l2[i] = po[i]
        
    #print(l1)
    #print(l2)
    co = 0

    for i in range(0,n,2):
        if i + 2 <= n-1:
            #print(ans,co+l1[i+1],co+l2[i+2])
            ans = max(ans,co+l1[i+1],co+l2[i+2])
        elif i+1 <= n-1:
            ans = max(ans,co+l1[i+1])
        else:
            ans = max(ans,co)
        
        co += a[i]
    co = 0
    #print(ans)
    for i in range(1,n,2):
        #print(ans,co+l1[i+1])
        ans = max(ans,co+po[i+1])
        #ans = max(ans,co+l1[i+1])
        co += a[i]
    #print("po:"+str(mi[1]))
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 20

dp = [{} for i in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(max((i + 1) // 2 - 4, 0), (i + 1) // 2 + 3):
        dp[i + 1][j + 1] = -INF
        if j in dp[max(0, i - 1)]:
            dp[i + 1][j + 1] = max(dp[max(0, i - 1)][j] + a[i], dp[i + 1][j + 1])
        if j in dp[max(0, i - 2)]:
            dp[i + 1][j + 1] = max(dp[max(0, i - 2)][j] + a[i], dp[i + 1][j + 1])
        if j in dp[max(0, i - 3)]:
            dp[i + 1][j + 1] = max(dp[max(0, i - 3)][j] + a[i], dp[i + 1][j + 1])
print(dp[-1][n // 2])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
INF = 10 ** 20

dp = [{} for i in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(max((i + 1) // 2 - 3, 0), (i + 1) // 2 + 2):
        dp[i + 1][j + 1] = -INF
        if j in dp[max(0, i - 1)]:
            dp[i + 1][j + 1] = max(dp[max(0, i - 1)][j] + a[i], dp[i + 1][j + 1])
        if j in dp[max(0, i - 2)]:
            dp[i + 1][j + 1] = max(dp[max(0, i - 2)][j] + a[i], dp[i + 1][j + 1])
        if j in dp[max(0, i - 3)]:
            dp[i + 1][j + 1] = max(dp[max(0, i - 3)][j] + a[i], dp[i + 1][j + 1])
print(dp[-1][n // 2])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

a_array = np.array(a)

if n <= 4: 
  if n % 2 == 0:
    sum_1 = np.sum(a_array[0:-1:2])
    sum_2 = np.sum(a_array[1::2])
    ans = max(sum_1, sum_2)
  else:
    ans = max(a_array)

else:
  max_value = np.zeros((2, n), dtype = np.int)
  max_value[0, 0] = a_array[0]
  max_value[1, 0] = 1
  max_value[0, 1] = a_array[1]
  max_value[1, 1] = 1
  max_value[0, 2] = max((max_value[0,0] + a_array[2]), a_array[2])
  if (max_value[0, 0] + a_array[2]) > a_array[2]:
    max_value[1, 2] = 2
  else:
    max_value[1, 2] = 1 

  for i in range (3, n):
    if (a_array[i] + max_value[0, i-2]) >= (a_array[i] + max_value[0, i-3]):
      if ((i-1) // 2) <= (max_value[1, i-2] + 1) == (i+1) // 2:
        max_value[0, i] = a_array[i] + max_value[0, i-2]
        max_value[1, i] = max_value[1, i-2] + 1
      else:
        max_value[0, i] = a_array[i] + max_value[0, i-3]
        max_value[1, i] = max_value[1, i-3] + 1
    else:
      if ((i-1) //2) <= (max_value[1, i-3] + 1) == (i+1) // 2:        
        max_value[0, i] = a_array[i] + max_value[0, i-3]
        max_value[1, i] = max_value[1, i-3] + 1
      else:
        max_value[0, i] = a_array[i] + max_value[0, i-2]
        max_value[1, i] = max_value[1, i-2] + 1
  # print(max_value)
  # print(max_value[1, -1], max_value[1, -2], max_value[1, -3])
  # print(max_value[0, -1], max_value[0, -2], max_value[0, -3])
  if max_value[1, -1] == n // 2:
    ans_1 = max_value[0, -1]
  else: 
    ans_1 = -9999999999999999
  if max_value[1, -2] == n // 2:
    ans_2 = max_value[0, -2]
  else: 
    ans_2 = -9999999999999999
  if max_value[1, -3] == n // 2:
    ans_3 = max_value[0, -3]
  else: 
    ans_3 = -9999999999999999
  ans = max(max(ans_1, ans_2), ans_3)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

a_array = np.array(a)

if n % 2 == 0:
  sum_1 = np.sum(a_array[0:-1:2])
  sum_2 = np.sum(a_array[1::2])
  ans = max(sum_1, sum_2)

else:
  max_value = np.zeros((2, n), dtype = np.int)
  max_value[0, 0] = a_array[0]
  max_value[1, 0] = 1
  max_value[0, 1] = a_array[1]
  max_value[1, 1] = 1
  max_value[0, 2] = max((max_value[0,0] + a_array[2]), a_array[2])
  if (max_value[0, 0] + a_array[2]) > a_array[2]:
    max_value[1, 2] = 2
  else:
    max_value[1, 2] = 1 

  for i in range (3, n):
    if (a_array[i] + max_value[0, i-2]) >= (a_array[i] + max_value[0, i-3]):
      if ((i-1) // 2) <= (max_value[1, i-2] + 1) == (i+1) // 2:
        max_value[0, i] = a_array[i] + max_value[0, i-2]
        max_value[1, i] = max_value[1, i-2] + 1
      else:
        max_value[0, i] = a_array[i] + max_value[0, i-3]
        max_value[1, i] = max_value[1, i-3] + 1
    else:
      if ((i-1) //2) <= (max_value[1, i-3] + 1) == (i+1) // 2:        
        max_value[0, i] = a_array[i] + max_value[0, i-3]
        max_value[1, i] = max_value[1, i-3] + 1
      else:
        max_value[0, i] = a_array[i] + max_value[0, i-2]
        max_value[1, i] = max_value[1, i-2] + 1
  # print(max_value)
  # print(max_value[1, -1], max_value[1, -2], max_value[1, -3])
  # print(max_value[0, -1], max_value[0, -2], max_value[0, -3])
  if max_value[1, -1] == n // 2:
    ans_1 = max_value[0, -1]
  else: 
    ans_1 = -9999999999999999
  if max_value[1, -2] == n // 2:
    ans_2 = max_value[0, -2]
  else: 
    ans_1 = -9999999999999999
  if max_value[1, -3] == n // 2:
    ans_3 = max_value[0, -3]
  else: 
    ans_3 = -9999999999999999
  ans = max(max(ans_1, ans_2), ans_3)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

a_array = np.array(a)

if n % 2 == 0:
  sum_1 = np.sum(a_array[0:-1:2])
  sum_2 = np.sum(a_array[1::2])
  ans = max(sum_1, sum_2)

else:
  max_value = np.zeros((2, n), dtype = np.int)
  max_value[0, 0] = a_array[0]
  max_value[1, 0] = 1
  max_value[0, 1] = a_array[1]
  max_value[1, 1] = 1
  max_value[0, 2] = max((max_value[0,0] + a_array[2]), a_array[2])
  if (max_value[0, 0] + a_array[2]) > a_array[2]:
    max_value[1, 2] = 2
  else:
    max_value[1, 2] = 1 

  for i in range (3, n):
    if (a_array[i] + max_value[0, i-2]) >= (a_array[i] + max_value[0, i-3]):
      if ((i-1) // 2) <= (max_value[1, i-2] + 1) == (i+1) // 2:
        max_value[0, i] = a_array[i] + max_value[0, i-2]
        max_value[1, i] = max_value[1, i-2] + 1
      else:
        max_value[0, i] = a_array[i] + max_value[0, i-3]
        max_value[1, i] = max_value[1, i-3] + 1
    else:
      if ((i-1) //2) <= (max_value[1, i-3] + 1) == (i+1) // 2:        
        max_value[0, i] = a_array[i] + max_value[0, i-3]
        max_value[1, i] = max_value[1, i-3] + 1
      else:
        max_value[0, i] = a_array[i] + max_value[0, i-2]
        max_value[1, i] = max_value[1, i-2] + 1
  # print(max_value)
  # print(max_value[1, -1], max_value[1, -2], max_value[1, -3])
  # print(max_value[0, -1], max_value[0, -2], max_value[0, -3])
  if max_value[1, -3] == max_value[1, -1]:
    ans = max(max(max_value[0, -1], max_value[0, -2]), max_value[0, -3])
  else:
    ans = max(max_value[0, -1], max_value[0, -2])

print(ans)

Submission status: Wrong Answer

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

if N%2==0:
  dp=[]
  for i in range(2):
    array=[0]*N
    dp.append(array)
    
  #init
  dp[0][0]=alist[0]
  dp[0][1]=alist[0]
  dp[1][1]=alist[1]
  for i in range(2,N):
    dp[0][i]=dp[0][i-2]+alist[i]
    dp[1][i]=max(dp[1][i-2]+alist[i],dp[0][i-3]+alist[i])
    
  print(max(dp[0][-1],dp[0][-2],dp[1][-1]))
else:
  dp=[]
  for i in range(3):
    array=[0]*N
    dp.append(array)

  #init
  dp[0][0]=alist[0]
  dp[0][1]=alist[0]
  dp[0][2]=alist[0]+alist[2]
  dp[1][1]=alist[1]
  dp[1][2]=alist[1]
  dp[2][2]=alist[2]
  for i in range(3,N):
    dp[0][i]=dp[0][i-2]+alist[i]
    dp[1][i]=max(dp[1][i-2]+alist[i],dp[0][i-3]+alist[i])
    dp[2][i]=max(dp[2][i-2]+alist[i],dp[1][i-3]+alist[i],dp[0][i-4]+alist[i])
    
  print(max(dp[0][-1],dp[0][-2],dp[0][-3],dp[1][-1],dp[1][-2],dp[2][-1]))

Submission status: Wrong Answer

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

if N%2==0:
  dp=[]
  for i in range(2):
    array=[0]*N
    dp.append(array)
    
  #init
  dp[0][0]=alist[0]
  dp[0][1]=alist[0]
  dp[1][1]=alist[1]
  for i in range(2,N):
    dp[0][i]=dp[0][i-2]+alist[i]
    dp[1][i]=max(dp[1][i-2]+alist[i],dp[0][i-3]+alist[i])
    
  print(max(dp[0][-1],dp[1][-1]))
else:
  dp=[]
  for i in range(3):
    array=[0]*N
    dp.append(array)

  #init
  dp[0][0]=alist[0]
  dp[0][1]=alist[0]
  dp[0][2]=alist[0]+alist[2]
  dp[1][1]=alist[1]
  dp[1][2]=alist[1]
  dp[2][2]=alist[2]
  for i in range(3,N):
    dp[0][i]=dp[0][i-2]+alist[i]
    dp[1][i]=max(dp[1][i-2]+alist[i],dp[0][i-3]+alist[i])
    dp[2][i]=max(dp[2][i-2]+alist[i],dp[1][i-3]+alist[i],dp[0][i-4]+alist[i])
    
  print(max(dp[0][-1],dp[1][-1],dp[2][-1]))

Submission status: Wrong Answer

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

if N%2==0:
  dp=[]
  for i in range(2):
    array=[0]*N
    dp.append(array)
    
  #init
  dp[0][0]=alist[0]
  dp[0][1]=alist[0]
  dp[1][1]=alist[1]
  for i in range(2,N):
    dp[0][i]=dp[0][i-2]+alist[i]
    dp[1][i]=max(dp[1][i-2]+alist[i],dp[0][i-3])
    
  print(max(dp[0][-1],dp[1][-1]))
else:
  dp=[]
  for i in range(3):
    array=[0]*N
    dp.append(array)

  #init
  dp[0][0]=alist[0]
  dp[0][1]=alist[0]
  dp[0][2]=alist[0]+alist[2]
  dp[1][1]=alist[1]
  dp[1][2]=alist[1]
  dp[2][2]=alist[2]
  for i in range(3,N):
    dp[0][i]=dp[0][i-2]+alist[i]
    dp[1][i]=max(dp[1][i-2]+alist[i],dp[0][i-3])
    dp[2][i]=max(dp[2][i-2]+alist[i],dp[1][i-3],dp[0][i-4])
    
  print(max(dp[0][-1],dp[1][-1],dp[2][-1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = input().split()
for i in range(n):
  a[i] = int(a[i])
sum = 0
c = 0
if a[0]>a[1]:
  c = 0
else:
  c = 1
for i in range(0,n-1,2):
  if a[i]>a[i+1] and c==0:
    sum += a[i]
    c = 0
  elif a[i+1]>a[i] and c==1:
    sum += a[i+1]
    c = 1
  else:
    if c==0:
      sum += a[i]
    else:
      sum += a[i+1]
print(sum)

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())
A = np.array([0] + list(map(int, input().split())), np.int64)

if N % 2 == 0:
	O = A[1:][::2]
	E = A[1:][1::2]
	print(max(np.sum(O), np.sum(E)))
else:
	cnt = np.zeros(4, np.int64)
	for i in range(1,4):
		cnt[i] = np.max(A[1:i+1])

	for i in range(5,N+1,2):
		for j in range(3):
			cnt[3-j] += A[i-j]
		for j in range(2,4):
			cnt[j] = max(cnt[j-1], cnt[j])

	print(cnt[-1])

Submission status: Wrong Answer

Solution code:
C = -(10**9 + 7)


def main():
    from collections import defaultdict
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    dp = defaultdict(lambda: C)
    for i in range(N+1):
        dp[(i, 0)] = 0
        if i != 0:
            dp[(i, 1)] = max(dp[(i-1, 1)], A[i-1])
    for i in range(1, N+1):
        for j in range(i//2-1, (i+1)//2 + 1):
            if dp[(i-1, j+1)] != C:
                dp[(i, j+1)] = max(dp[(i, j+1)], dp[(i-1, j+1)])
            if dp[(i-2, j)] != C:
                dp[(i, j+1)] = max(dp[(i, j+1)], dp[(i-2, j)] + A[i-1])
            if dp[(i-3, j)] != C:
                dp[(i, j+1)] = max(dp[(i, j+1)], dp[(i-3, j)] + A[i-1])
    print(dp[(N, K)])
    # print(dp)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

if n%2==1:
    ans=-float('inf')
    Ax=[A[i] for i in range(0,n,2)]
    Bx=[A[i] for i in range(1,n,2)]
    for i in range(n//2):
        ans=max(ans,(sum(A[:i])+sum(Bx[i:])))
    print(ans)

if n%2==0:
    exit()

Submission status: Wrong Answer

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

ans = 0
if N % 2 == 0:
    one, two = 0, 0
    for i, v in enumerate(A):
        if i % 2 == 0:
            one += v
        else:
            two += v
    ans = max(one, two)
else:
    one, two, three = 0, 0, 0
    for i, v in enumerate(A):
        if i % 2 == 0:
            one += v
            three += v
        else:
            two += v
    one -= A[-1]
    three -= A[0]
    ans = max(one,two, three)

print(ans)

Submission status: Wrong Answer

Solution code:
C = -(10**9 + 7)


def main():
    from collections import defaultdict
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    dp = defaultdict(lambda: C)
    for i in range(N+1):
        dp[(i, 0)] = 0
        if i != 0:
            dp[(i, 1)] = max(dp[(i-1, 1)], A[i-1])
    for i in range(2, N+1):
        for j in range(i//2-1, (i+1)//2 + 1):
            if dp[(i-1, j)] == C and dp[(i-2, j-1)] == C and dp[(i-3, j-1)] == C:
                dp[(i, j)] = C
            else:
                dp[(i, j)] = max(dp[(i, j)], dp[(i-1, j)],
                                 dp[(i-2, j-1)] + A[i-1],
                                 dp[(i-3, j-1)] + A[i-1])
    print(dp[(N, K)])
    # print(dp)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
C = -(10**9 + 7)


def main():
    from collections import defaultdict
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    dp = defaultdict(lambda: C)
    for i in range(N+1):
        dp[(i, 0)] = 0
        if i != 0:
            dp[(i, 1)] = max(dp[(i-1, 1)], A[i-1])
    for i in range(2, N+1):
        for j in range(i//2-1, (i+1)//2 + 1):
            dp[(i, j)] = max(dp[(i, j)], dp[(i-1, j)],
                             dp[(i-2, j-1)] + A[i-1],
                             dp[(i-3, j-1)] + A[i-1])
    print(dp[(N, K)])
    # print(*dp, sep="\n")
    # print(dp)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# F - Select Half

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

l = [0] * n # a[0]〜a[i]からfloor((i+1)/2)個選ぶときの最大値
u = [0] * n # a[0]〜a[i]からceil((i+1)/2)個選ぶときの最大値

l[0] = 0
u[0] = a[0]
u[1] = max(a[:2])
l[1] = u[1]

# 0 1 2 3 4 5 6 7 8 9 10 i
# . . . . . . . . . . .
# 1 1 2 2 3 3 4 4 5 5 6  u[i]
# 0   1   2   3   4   5  l[i]

for i in range(2, n):
    u[i] = u[i - 2] + a[i]
    l[i] = max(u[i - 1], l[i - 2] + a[i])

print(l[-1])

Submission status: Wrong Answer

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

ans = 0
if n%2 == 0:
    for i in range(n//2):
        ans += a[i*2]
    for i in range(n//2):
        mem = ans - a[(n//2-i-1)*2] + a[(n//2-i-1)*2+1]
        ans = max(ans,mem)
else:
    odd = [a[0]]+[0]*(n//2)
    even = [a[1]]+[0]*(n//2-1)
    for i in range(2,n):
        if i%2==0:
            odd[i//2] = odd[i//2-1]+a[i]
        else:
            even[i//2] = even[i//2-1]+a[i]
            
    odd = [0]+odd
    even = [0]+even
            
    for i in range(n//2+1):
        for j in range(i,n//2+1):
            mem = odd[i]+odd[n//2+1]-odd[j+1]+even[j]-even[i]
            ans = max(ans,mem)
        
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
def main():
    import sys
    input = sys.stdin.readline
    l = list(map(int,input().split()))
    dp = [[-float("INF")]*(3) for i in range(n+1)]
    dp[0][0] = 0
    dp[1][-1] = 0
    dp[1][1] = l[0]
    for i in range(1,n):
        
        dp[i+1][-1] = max(dp[i][0],dp[i-1][-1]+l[i])
        dp[i+1][0] = max(dp[i][1],dp[i-1][0]+l[i])
        dp[i+1][1] = dp[i-1][1]+l[i]
    print(max(dp[-1]))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10**20
    N=I()
    A=LI()
    """左から見ていく，i個を見たときに，
    iが偶数：
    　現在i//2個取得　or i//2 - 1取得(もう余裕がない)
    
    iが奇数：
    　現在i//2 +1個取得　or i//2取得(もう余裕がない)
    さらにi番目をとったか撮ってないかで2通り 
    ただし，余裕がある状態から取らないのは，数が足りなくなる
    """
    tight_get=[-inf]*N
    tight_not=[-inf]*N
    lo=[-inf]*N
    
    #最初だけ，取ったら必ずlooseになる
    lo[0]=A[0]
    lo[1]=A[1]
    tight_not[0]=0
    tight_not[1]=0
    
    for i in range(2,min(3,N)):
        LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i]+tight_not[i-1]]
        tight_get[i]=max(LL)
        LL=[lo[i-2]]
        tight_not[i]=max(LL)
        lo[i]=lo[i-2]+A[i]
        
    for i in range(3,min(4,N)):
        LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i],tight_not[i-1]+A[i],lo[i-3]+A[i]]
        tight_get[i]=max(LL)
        LL=[lo[i-2],lo[i-3]]
        tight_not[i]=max(LL)
        lo[i]=max(lo[i-2]+A[i],lo[i-3]+A[i])
        
    for i in range(4,N):
        LL=[tight_get[i-2]+A[i],tight_not[i-2]+A[i],tight_not[i-1]+A[i],lo[i-3]+A[i],lo[i-4]+A[i]]
        tight_get[i]=max(LL)
        LL=[lo[i-2]]
        tight_not[i]=max(LL)
        lo[i]=lo[i-2]+A[i]
    
    if N%2==1:
        print(max(tight_get[-1],tight_not[-1]))
    else:
        print(max(lo[-1],lo[-2]))
    
    
    
        
        
        

main()

Submission status: Wrong Answer

Solution code:
# 嘘解答がアフターコンテスト通るのかチェック
n = int(input())
a = tuple(map(int,input().split()))

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

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

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

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

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

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