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()))
if N%2:
    a, b, c = 0, 0, 0
    for i in range(0,N-2,2):
        c=max(a+A[i+2],b+A[i+2],c+A[i+2])
        b=max(a+A[i+1],b+A[i+1])
        a+=A[i]
    print(max(a,b,c))
else:
    print(max(sum(A[::2]), sum(A[1::2])))

Submission status: Wrong Answer

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

inf = float('inf')

# 累積和
if n % 2 == 0:
    while True:
      pass
    l_even = [0]
    l_odd = [0]
    for i in range(n):
        if i % 2 == 0:
            l_even.append(l_even[-1] + a[i])
        else:
            l_odd.append(l_odd[-1] + a[i])
    ans = -inf
    for i in range(n // 2 + 1):
        if ans < l_even[i] + l_odd[-1] - l_odd[i]:
            ans = l_even[i] + l_odd[-1] - l_odd[i]
    print(ans)
    exit()

# dp[i] = i回ずらしを使った時の最大値
# 1個ずつdpを更新
# i = 0, 1, 2
dp = [a[0], a[1], a[2]]
for i in range(2, n, 2):
    try:
        dp[2] = max([dp[2] + a[i+2], dp[1] + a[i+2]])
    except:
        pass
    try:
        dp[1] = max([dp[1] + a[i+1], dp[0] + a[i+1]])
    except:
        pass
    dp[0] += a[i]

print(max(dp))

Submission status: Wrong Answer

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

inf = float('inf')

# 累積和
if n % 2 == 0:
    l_even = [0]
    l_odd = [0]
    for i in range(n):
        if i % 2 == 0:
            l_even.append(l_even[-1] + a[i])
        else:
            l_odd.append(l_odd[-1] + a[i])
    ans = -inf
    for i in range(n // 2 + 1):
        if ans < l_even[i] + l_odd[-1] - l_odd[i]:
            ans = l_even[i] + l_odd[-1] - l_odd[i]
    print(ans)
    exit()

# dp[i] = i回ずらしを使った時の最大値
# 1個ずつdpを更新
# i = 0, 1, 2
dp = [a[0], a[1], a[2]]
for i in range(2, n, 2):
    try:
        dp[2] = max([dp[2] + a[i+2], dp[1] + a[i+2]])
    except:
        pass
    try:
        dp[1] = max([dp[1] + a[i+1], dp[0] + a[i+1]])
    except:
        pass
    dp[0] += a[i]

print(max(dp))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

if N%2 == 0:
  B = [0]
  W = [0]
  for i in range(N//2):
    B.append(B[-1]+A[i*2])
  for i in range(N//2):
    W.append(W[-1]+A[N-1-i*2])
  ans = [B[i]+W[N//2-i] for i in range(N//2+1)]
  print(max(ans))
else:
  A.append(-INF)
  dp = [[0,0,0,0] for i in range(N//2+2)]
  for i in range(N//2+1):
    a,b = A[i*2],A[i*2+1]
    dp[i+1][0] = dp[i][0] + a
    dp[i+1][1] = max(dp[i][0],dp[i][1]) + b
    dp[i+1][2] = max(dp[i][0],dp[i][1])
    dp[i+1][3] = max(dp[i][2],dp[i][3]) + a
  print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

if N%2 == 0:
  B = [0]
  W = [0]
  for i in range(N//2):
    B.append(B[-1]+A[i*2])
  for i in range(N//2):
    W.append(W[-1]+A[N-1-i*2])
  ans = [B[i]+W[N//2-i] for i in range(N//2+1)]
else:
  A.append(-INF)
  dp = [[0,0,0,0] for i in range(N//2+2)]
  for i in range(N//2+1):
    a,b = A[i*2],A[i*2+1]
    dp[i+1][0] = dp[i][0] + a
    dp[i+1][1] = max(dp[i][0],dp[i][1]) + b
    dp[i+1][2] = max(dp[i][0],dp[i][1])
    dp[i+1][3] = max(dp[i][2],dp[i][3]) + a
  print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()

def odd(A):
    oddi=np.array(A[::2],dtype=np.int64)
    eveni=np.array(A[1::2],dtype=np.int64)
    left=np.cumsum(oddi[:-1]-eveni)
    left=np.insert(left,0,0)
    left=np.append(left,0)
    right=np.cumsum(oddi[:0:-1]-eveni[::-1])[::-1]
    right=np.insert(right,0,0)
    right=np.append(right,0)
    tmp=np.max(np.maximum.accumulate(left)+right)
    return tmp+np.sum(eveni)

def even(A):
    left=np.array([0]+A[::2],dtype=np.int64)
    right=np.array(A[1::2]+[0],dtype=np.int64)
    return np.max(left.cumsum()+right.cumsum())

def main():
    n=int(input())
    A=list(map(int, input().split()))
    if n%2==1:
        print(odd(A))
    else:
        print(even(A))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n = ni()
a = nl()
dp = [[0]*3 for _ in range(n+5)]
t = n%2
for i in range(n):
    dp[i][0] = dp[i-2][0] + a[i]
    dp[i][1] = max(dp[i-2][1], dp[i-3][0]) + a[i]
    if t:
        dp[i][2] = max(dp[i-2][2], dp[i-3][1], dp[i-4][0]) + a[i]
if t:
    print(max(dp[n-3][0], dp[n-2][1], dp[n-1][2]))
else:
    print(max(dp[n-2][0], dp[n-1][1]))

Submission status: Wrong Answer

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


INF=10**20
def main():
    N=ii()
    A=list(mi())

    sel_count = N//2
    X = []
    for i,a in enumerate(A):
        X.append((-1*a,i))

    heapq.heapify(X)
    i = 0
    # selected = []
    ans = 0
    ng_index = set()
    while X and i < sel_count:
        current_max, j = heapq.heappop(X)
        current_max *= -1

        if j in ng_index: continue
        ans += current_max
        
        ng_index.add(j-1)
        ng_index.add(j)
        ng_index.add(j+1)

        i += 1
    
    print(ans)

    



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()
dp = [[defaultdict(lambda:-INF) for _ in range(2)] for _ in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
    for j in range(2):
        for k, e in dp[i][j].items():
            if i // 2 <= k <= i // 2 + 1:
                dp[i + 1][0][k] = max(dp[i + 1][0][k], e)
                if j == 0:
                    dp[i + 1][1][k + 1] = max(dp[i + 1][1][k + 1], e + A[i])

print(max(dp[n][0][n // 2], dp[n][1][n // 2]))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    if N % 2 == 0:
        print(max(sum(A[::2]), sum(A[1::2])))
        return

    dp = [[0]*3 for _ in range(N//2 + 1)]
    for i in range(N//2):
        dp[i+1][0] = dp[i][0] + A[2*i]

        dp[i+1][1] = max(dp[i][0], dp[i][1]) + A[2*i+1]

        dp[i+1][2] = max(dp[i][0], dp[i][1], dp[i][2]) + A[2*i+2]

    print(max(dp[-1]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

C = [0 for _ in range(N)] #奇数個、余裕あり
D = [0 for _ in range(N)] #偶数個
E = [0 for _ in range(N)] #奇数個、余裕なし

E[0] = a[0]

for i in range(N):
  if i % 2 == 0:#奇数個
    C[i] = max(C[i-2]+a[i],D[i-1])
    E[i] = E[i-2] + a[i]
  else:
    D[i] = max(D[i-2]+a[i],E[i-1])

if N % 2 == 0:
  print(D[N-1])
else:
  print(C[N-1])

Submission status: Wrong Answer

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

C = [0 for _ in range(N)] #奇数個、余裕あり
D = [0 for _ in range(N)] #偶数個
E = [0 for _ in range(N)] #奇数個、余裕なし

C[0] = a[0]

for i in range(N):
  if i % 2 == 0:#奇数個
    C[i] = max(C[i-2]+a[i],D[i-1])
    E[i] = E[i-2] + a[i]
  else:
    D[i] = max(D[i-2]+a[i],E[i-1])

if N % 2 == 0:
  print(D[N-1])
else:
  print(C[N-1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
if N%2 == 0:
  dp = [[0]*2 for _ in range(N)] #0index
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  for i in range(2,N):
    dp[i][0] = dp[i-2][0]+A[i]
    if i-3>=0:
      dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
    else:
      dp[i][1] = max(dp[i-2][1],0)+A[i]
  ans = max(dp[-2][0],dp[-1][1])
  print(ans)
#i個目を使ってj(0-2)回多く飛んでいる。
else: #N%2 == 1:
  dp = [[0]*3 for _ in range(N)] #0index
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  dp[2][2] = A[2]
  dp[2][0] = A[0]+A[2]
  print(dp)
  for i in range(3,N):
    dp[i][0] = dp[i-2][0]+A[i]
    if i-3 >= 0:
      dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
    else:
      dp[i][1] = max(dp[i-2][1],0)+A[i]
    if i-4 >= 0:
      dp[i][2] = max(dp[i-2][2],dp[i-3][1],dp[i-4][0])+A[i]
    elif i-3 >= 0:
      dp[i][2] = max(dp[i-2][2],dp[i-3][1],0)+A[i]
  #else:
  #  dp[i][2] = max(dp[i-2][2],0,0)+A[i]
  print(dp[-1],dp[-2],dp[-3])

  ans = max(dp[-3][0],dp[-2][1],dp[-1][2])
  print(ans)
  exit()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
if N%2 == 0:
  odd = 0; even = 0
  for i in range(N//2):
    odd += A[2*i+1]
    even += A[2*i]
  print(max(odd,even))
  exit()
#i個目を使ってj(0-2)回多く飛んでいる。
dp = [[0]*3 for _ in range(N)] #0index
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]
  if i-3 >= 0:
    dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
  else:
    dp[i][1] = max(dp[i-2][1],0)+A[i]
  if i-4 >= 0:
    dp[i][2] = max(dp[i-2][2],dp[i-3][1],dp[i-4][0])+A[i]
  elif i-3 >= 0:
    dp[i][2] = max(dp[i-2][2],dp[i-3][1],0)+A[i]
  else:
    dp[i][2] = max(dp[i-2][2],0,0)+A[i]
#print(dp)

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
if N%2 == 0:
  odd = 0; even = 0
  for i in range(N//2):
    odd += A[2*i+1]
    even += A[2*i]
  print(max(odd,even))
  exit()
#i個目を使ってj(0-2)回多く飛んでいる。
dp = [[0]*3 for _ in range(N)] #0index
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(2,N):
  dp[i][0] = dp[i-2][0]+A[i]
  if i-3 >= 0:
    dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
  else:
    dp[i][1] = max(dp[i-2][1],0)+A[i]
  if i-4 >= 0:
    dp[i][2] = max(dp[i-2][2],dp[i-3][1],dp[i-4][0])+A[i]
  elif i-3 >= 0:
    dp[i][2] = max(dp[i-2][2],dp[i-3][1],0)+A[i]
  else:
    dp[i][2] = max(dp[i-2][2],0,0)+A[i]
#print(dp)
ans = max(dp[-3][0],dp[-2][1],dp[-1][2])
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

N = int(input())
a = [0] + list(map(int, input().split()))

o = [a[2*i+1] for i in range(N//2)]
o = list(itertools.accumulate(o))
print(o)
dp = [0 for i in range(N+1)]

dp[0] = dp[1] = 0
dp[2] = max(a[1], a[2])
if N > 2: dp[3] = max([a[1], a[2], a[3]])

if N > 3:
    for i in range(4, N+1):
        if i % 2 == 0:
            dp[i] = max(dp[i-2] + a[i], o[(i-3)//2] + a[i-1])
        else:
            dp[i] = max([dp[i-2] + a[i], dp[i-3] + a[i-1], o[(i-2)//2] ])

print(dp[N])

Submission status: Wrong Answer

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

INF = 10**18
dp = [[-INF]*n for i in range(2)]

dp[0][0] = 0
dp[0][1] = max(a[0], a[1])
dp[1][0] = a[0]
dp[1][1] = max(a[0], a[1])

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

Submission status: Wrong Answer

Solution code:
import copy

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

k = 1 + n%2
INF = 10**9
dp = [[-INF]*4 for i in range(n+5)]
dp[0][0] = 0

for i in range(n):
    for j in range(k+1):
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j])
        now = copy.deepcopy(dp[i][j])
        if (i+j) % 2 == 0:
            now += a[i]
        dp[i+1][j] = max(dp[i+1][j], now)
print(dp[n][k])

Submission status: Wrong Answer

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

dp = [[0]*n for i in range(2)]

dp[0][1] = max(a[0], a[1])
dp[1][0] = a[0]
dp[1][1] = max(a[0], a[1])

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

Submission status: Wrong Answer

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

dp = [[0]*n for i in range(2)]

dp[1][0] = a[0]
dp[1][1] = max(a[0], a[1])

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

Submission status: Wrong Answer

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

if N % 2 == 0:
    L = [0]
    R = [0]
    for i in range(N//2):
        L.append(A[2*i]+L[-1])
        R.append(A[-2*i-1]+R[-1])
    R.append(0)
    L.append(0)
    R = R[::-1]
    print(max(L[i]+R[i+1] for i in range(N//2+1)))
else:
    base = sum(A[:N-1:2])
    B = [0]
    W = [0]
    for i in range(N//2):
        B.append(A[-2*i-3]+B[-1])
        W.append(A[-2*i-2]+W[-1])
    W = W[::-1]
    B = B[::-1]
    D1 = [ W[i] - B[i]  for i in range(N//2)]
    D2 = [ B[i+1] + A[-1] - W[i] for i in range(N//2)]

    M1 = [0]
    M2 = [0]
    for i in range(N//2):
        M1.append(max(M1[-1], D1[i]))
        M2.append(max(M2[-1], D2[-1-i]))
    M2.append(0)
    M2 = M2[::-1]
    ans = base + max(M1[i]+M2[i] for i in range(N//2))
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo


show_flg=False
show_flg=True

ans=0


n=I()
a=LI()

if n==2:
    print(max(a))
    exit()

dp=[[-inf]*3for i in range(n)]
dp[0][0]=a[0]
dp[1][1]=a[1]
dp[2][2]=a[2]
N=(n)//2

for i in range(n):
    dp[i][2]=max([dp[i-2-j][2-j]+a[i] for j in range(3) if i-2-j>=0]+[dp[i][2]])
    dp[i][1]=max([dp[i-2-j][1-j]+a[i] for j in range(2) if i-2-j>=0 and (i)//2<=N]+[dp[i][1]])
    dp[i][0]=max([dp[i-2-j][j]+a[i] for j in range(1) if i-2-j>=0 and (i+1)//2<=N]+[dp[i][0]])

ans=max(dp[n-1][:]+dp[n-2][:2]+dp[n-3][:1])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo


show_flg=False
show_flg=True

ans=0


n=I()
a=LI()+[0]*4

dp=[[0]*3for i in range(n+1+4)]
dp[0][0]=a[0]
dp[1][1]=a[1]
dp[2][2]=a[2]

for i in range(n):
    dp[i][2]=max([dp[i-2-j][2-j]+a[i] for j in range(3) if i-2-j>=0]+[dp[i][2]])
    dp[i][1]=max([dp[i-2-j][1-j]+a[i] for j in range(2) if i-2-j>=0 and (i+1+1)//2<n//2]+[dp[i][1]])
    dp[i][0]=max([dp[i-2-j][j]+a[i] for j in range(1) if i-2-j>=0 and (i+1)//2<n//2]+[dp[i][0]])

ans=max(dp[n-1][:]+dp[n-2][:2]+dp[n-3][:1])
print(ans)