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: Runtime Error

Solution code:
n=int(input())
if n%2:
  a=list(map(int,input().split()))
  s=[[a[0],0,0],[0,a[1],0],[a[0]+a[2],0,a[2]],[0,max([a[0]+a[3],a[1]+a[3]]),0]]+[[0,0,0]for i in range(4,n)]
  for i in range(4,n):
    if i%2:
      s[i][1]=max(s[i-2][1],s[i-3][0])+a[i]
    else:
      s[i][0]=s[i-2][0]+a[i]
      s[i][2]=max([s[i-2][2],s[i-3][1],s[i-4][0]])+a[i]
  print(max([s[-1][2],s[-2][1],s[-3][0]]))
else:
  a=list(map(int,input().split()))
  s=[a[0],a[1]]+[0 for i in range(2,n)]
  for i in range(2,n):
    if i%2:
      s[i]=max([s[i-2],s[i-3]])+a[i]
    else:
      s[i]=s[i-2]+a[i]
  print(max(s[-2:]))

Submission status: Runtime Error

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

DP=[[-10**16 for i in range(N)]for j in range(3)]

DP[1][0]=0
DP[2][0]=0
DP[2][1]=0
DP[0][0]=A[0]
DP[1][1]=A[1]
DP[2][2]=A[2]

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

if N%2==0:
    print(max(DP[0][-2],DP[1][-1]))
else:
    print(max(DP[0][-3],DP[1][-2],DP[2][-1]))

Submission status: Runtime Error

Solution code:
N,K = [int(x) for x in input().split()]
count = [0]*(K+1)
ans = 0
mod = 1000000007
for i in range(K,0,-1):
    kosuu = pow(K//i,N,mod)
    if K // i >= 2:
        for j in range(K//i,1,-1):
            kosuu -= count[j*i]
    ans += i*kosuu
    count[i] = kosuu
print(ans%mod)

Submission status: Runtime Error

Solution code:
INF = -1000000000000001

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

a = int(n/2)

dpa = [[0]*(a+1) for i in range(n+1)]

dpa[0][0] = 0
dpa[1][0] = 0
dpa[1][1] = l[0]
j = 1
for i in range(2,n+1):
	if i == j*2:
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
	else:
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
		if (i != n):
			j += 1
#			print(i,j,dpa[i][j])
#			print("   ",i-2,j-1,dpa[i-2][j-1],"")
			dpa[i][j] = dpa[i-2][j-1]+l[i-1]

#print(dpa)
print(dpa[n][a])

Submission status: Runtime Error

Solution code:
import pprint
n = int(input())
ls = input().split()
lst = [int(e) for e in ls]
m = n //2
d = n % 2

def sum_res(plst):
  no = len(plst)
  if no <= 3:
    return max(plst)
  ret = []
  if no % 2 == 0:
    ret.append(plst[0]+sum_res(plst[2:no]))
    ret.append(sum_res(plst[0:no-2])+plst[no-1])
  else:

    ret.append(sum_res(plst[1:no]))

    if no >= 5:
      ret.append(plst[0]+sum_res(plst[2:no]))
  return max(ret)
#print(lst[26])
mmm = sum_res(lst)
print(mmm)

Submission status: Runtime Error

Solution code:
import pprint
n = int(input())
ls = input().split()
lst = [int(e) for e in ls]
m = n //2
d = n % 2

def sum_res(plst):
  no = len(plst)
  ret = []
  if no % 2 == 0:
    m = no // 2
    for i in range(m+1):
      sum = 0
      for j in range(m):
        if j < i :
          sum += plst[j*2]
        else:
          sum += plst[j*2+1]
      ret.append(sum)
  else:
    if no == 1:
      return plst[0]
    if no == 3:
      return max(plst)

    ret.append(sum_lst(plst[1:no]))

    if no >= 5:
      ret.append(plst[0]+sum_lst(plst[2:no-1]))

    if no >= 5:
      ret.append(plst[0]+sum_lst(plst[2:no-2])+plst[no-1])
  return max(ret)

mmm = sum_lst(lst)
print(mmm[0])

Submission status: Runtime Error

Solution code:
N = int(input())
import math
l = [int(x) for x in input().split()]
tobi = [0]*(math.ceil(N/2))
tobi[0] = l[0]
for i in range(1,math.ceil(N/2)):
    tobi[i] = tobi[i-1] + l[i*2]
from functools import lru_cache
@lru_cache(maxsize=1000000000)
def motomeru(x,y):
    if y == 0 or x == 0 or x == 1:
        return 0
    elif x % 2 == 0:
        return max(motomeru(x-2,y-1)+l[x-1],tobi[math.floor((x-1)/2)])
    else:
        return max(motomeru(x-2,y-1)+l[x-1],motomeru(x-1,y))
print(motomeru(N,N//2))

Submission status: Runtime Error

Solution code:
N = int(input())
import math
l = [int(x) for x in input().split()]
tobi = [0]*(math.ceil(N/2))
tobi[0] = l[0]
for i in range(1,math.ceil(N/2)):
    tobi[i] = tobi[i-1] + l[i*2]
def motomeru(x,y):
    if y == 0 or x == 0 or x == 1:
        return 0
    elif x % 2 == 0:
        return max(motomeru(x-2,y-1)+l[x-1],tobi[math.floor((x-1)/2)])
    else:
        return max(motomeru(x-2,y-1)+l[x-1],motomeru(x-1,y))
print(motomeru(N,N//2))

Submission status: Runtime Error

Solution code:
n=int(input())
A=sorted(list(map(int,input().split())),reverse=True)
li=[]
for i in range(n//2):
  li.append(A[2i])
print(sum(li))

Submission status: Runtime Error

Solution code:
n = int(input())
ai = [int(i) for i in input().split()]

is_odd = True

if n % 2 == 0:
    is_odd = False

if is_odd == True:
    dp = [[0 for i in range(3)] for j in range(n)]
else:
    dp = [[0 for i in range(2)] for j in range(n)]

if n == 3:
    print(max(ai[0],ai[2],ai[1]))
    print(ai[n+3])
    exit()
elif n == 2:
    print(max(ai[0],ai[1]))
    exit()
    

if is_odd == True:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
        dp[i][2] = max(dp[i-4][0]+ai[i],dp[i-3][1]+ai[i],dp[i-2][2]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))
else:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1]))

Submission status: Runtime Error

Solution code:
import collections
import math

N, *A = map(int, open(0).read().split())
a = dict(enumerate(A, 1))
dp = collections.defaultdict(int)
dp[1, 1] = a[1]

for i in range(2, N + 1):
    jj = range(math.floor(i // 2 - 1), math.ceil((i + 1) // 2) + 1)
    debug(jj)
    for j in jj:
        x = dp[i - 2, j - 1] + a[i]
        y = dp[i - 1, j]
        dp[i, j] = max(x, y)

print(dp[N, N // 2])

Submission status: Runtime Error

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

DP_odd = [0, 0, A[0]]
DP_even = [0, max(A[0], A[1])]

if N >= 3:
    DP_odd = [DP_even[0], max(DP_odd[1] + A[i], DP_even[1]), DP_odd[2] + A[2]]

for i in range(3, N):
    if (i + 1) % 2 == 1:    
        DP_odd = [max(DP_odd[0] + A[i], DP_even[0]), max(DP_odd[1] + A[i], DP_even[1]), DP_odd[2] + A[i]]
        print(DP_odd)
    else:
        DP_even = [max(DP_even[0] + A[i], DP_odd[1]), max(DP_even[1] + A[i], DP_odd[2])]
        print(DP_even)

if N % 2 == 1:
    ans = DP_odd[1]
else:
    ans = DP_even[1]

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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

a_array = np.array(a)

ans_array = np.zeros((n//2, n), dtype = np.int64)

if n >=4:

  ans_array[0, 0] = a_array[0]
  ans_array[0, 1] = a_array[1]
  ans_array[0, 2] = a_array[2]

  for i in range(1, n//2):
    j = 2*(i+1)
    # print(i, j)
    ans_array[i, j-2] = ans_array[i-1, j-4] + a_array[j-2]
    ans_array[i, j-1] = np.max(ans_array[i-1, j-4:j-2]) + a_array[j-1]
    if j < n:
      ans_array[i, j]  = np.max(ans_array[i-1, j-4:j-1]) + a_array[j]
  # print(ans_array)

  if n % 2 == 0:
    print(np.max(ans_array[-1, -2:]))
  else:
    print(np.max(ans_array[-1, -3:]))

else:
  print(max(a_array))

Submission status: Runtime Error

Solution code:
import numpy as np

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

a_array = np.array(a)

ans_array = np.zeros((n//2, n), dtype = np.int64)

if n >=4:

  ans_array[0, 0] = a_array[0]
  ans_array[0, 1] = a_array[1]
  ans_array[0, 2] = a_array[2]

  for i in range(1, n//2):
    j = 2*(i+1)
    # print(i, j)
    ans_array[i, j-2] = ans_array[i-1, j-4] + a_array[j-2]
    ans_array[i, j-1] = max(ans_array[i-1, j-4], ans_array[i-1, j-3]) + a_array[j-1]
    if j < n:
      ans_array[i, j]  = max(max(ans_array[i-1, j-4], ans_array[i-1, j-3]), ans_array[i-1, j-2]) + a_array[j]
  # print(ans_array)

  if n % 2 == 0:
    print(np.max(ans_array[-1, -2:]))
  else:
    print(np.max(ans_array[-1, -3:]))

else:
  print(max(a_array))

Submission status: Runtime Error

Solution code:
import numpy as np

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

a_array = np.array(a)

ans_array = np.zeros((n//2, n), dtype = np.int64)

if n >=4:

  ans_array[0, 0] = a_array[0]
  ans_array[0, 1] = a_array[1]
  ans_array[0, 2] = a_array[2]

  for i in range(1, n//2):
    j = 2*(i+1)
    # print(i, j)
    ans_array[i, j-2] = ans_array[i-1, j-4] + a_array[j-2]
    ans_array[i, j-1] = max(ans_array[i-1, j-4], ans_array[i-1, j-3]) + a_array[j-1]
    if j < n:
      ans_array[i, j]  = max(ans_array[i-1, j-3], ans_array[i-1, j-2]) + a_array[j]
  # print(ans_array)

  if n % 2 == 0:
    print(np.max(ans_array[-1, -2:]))
  else:
    print(np.max(ans_array[-1, -3:]))

else:
  print(max(a_array))

Submission status: Runtime Error

Solution code:
import numpy as np

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

a_array = np.array(a)

ans_array = np.zeros((n//2, n), dtype = np.int)

if n >=4:

  ans_array[0, 0] = a_array[0]
  ans_array[0, 1] = a_array[1]
  ans_array[0, 2] = a_array[2]

  for i in range(1, n//2):
    j = 2*(i+1)
    # print(i, j)
    ans_array[i, j-2] = ans_array[i-1, j-4] + a_array[j-2]
    ans_array[i, j-1] = max(ans_array[i-1, j-4], ans_array[i-1, j-3]) + a_array[j-1]
    if j < n:
      ans_array[i, j]  = max(ans_array[i-1, j-3], ans_array[i-1, j-2]) + a_array[j]
  # print(ans_array)

  if n % 2 == 0:
    print(np.max(ans_array[-1, -2:]))
  else:
    print(np.max(ans_array[-1, -3:]))

else:
  print(max(a_array))

Submission status: Runtime Error

Solution code:
import numpy as np

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

a_array = np.array(a)

ans_array = np.zeros((n//2, n), dtype = np.int)

if n >=4:

  ans_array[0, 0] = a_array[0]
  ans_array[0, 1] = a_array[1]
  ans_array[0, 2] = a_array[2]

  for i in range(1, n//2):
    j = 2*(i+1)
    # print(i, j)
    ans_array[i, j-2] = ans_array[i-1, j-4] + a_array[j-2]
    ans_array[i, j-1] = max(ans_array[i-1, j-4], ans_array[i-1, j-3]) + a_array[j-1]
    if j < n:
      ans_array[i, j]  = max(ans_array[i-1, j-3], ans_array[i-1, j-2]) + a_array[j]
  # print(ans_array)

  print(np.max(ans_array[-1, -3:]))

else:
  print(max(a_array))

Submission status: Runtime Error

Solution code:
import numpy as np

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

a_array = np.array(a)

ans_array = np.zeros((n//2, n), dtype = np.int)

ans_array[0, 0] = a_array[0]
ans_array[0, 1] = a_array[1]
ans_array[0, 2] = a_array[2]

for i in range(1, n//2):
  j = 2*(i+1)
  # print(i, j)
  ans_array[i, j-2] = ans_array[i-1, j-4] + a_array[j-2]
  ans_array[i, j-1] = max(ans_array[i-1, j-4], ans_array[i-1, j-3]) + a_array[j-1]
  if j < n:
    ans_array[i, j]  = max(ans_array[i-1, j-3], ans_array[i-1, j-2]) + a_array[j]

# print(ans_array)

print(np.max(ans_array[-1, -3:]))

Submission status: Runtime Error

Solution code:
inf = 10**18
N = int(input())
A = list(map(int, input().split()))
dp0=[[-inf]*(2+N//2) for _ in range(N+1)]
dp1=[[-inf]*(2+N//2) for _ in range(N+1)]
dp0[0][0] = 0

for i, x in enumerate(A):
    j = i//2
    for n in (j, j + 1):
        dp0[i+1][n] = max(dp0[i][n], dp1[i][n])
        dp1[i+1][n] = dp0[i][n - 1] + x
    #print(dp0)
    #print(dp1)

print(max(dp0[N][N//2], dp1[N][N//2]))

Submission status: Runtime Error

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

dp=[[-float('inf'),-float('inf'),-float('inf')] for i in range(n)]
# dp[i][0]:iまででまだ飛ばしてない
# dp[i][1]:一つ飛ばしてる
# dp[i][2]:２つ飛ばしてる
dp[0][0]=a[0]
dp[1][1]=a[1]
dp[2][2]=a[2]

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

if n%2==0:
    print(max(dp[-2][0],dp[-1][1]))
else:
    print(max(dp[-3][0],dp[-2][1],dp[-1][2]))

Submission status: Runtime Error

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

dp=[[-float('inf'),-float('inf'),-float('inf')] for i in range(n)]
# dp[i][0]:iまででまだ飛ばしてない
# dp[i][1]:一つ飛ばしてる
# dp[i][2]:２つ飛ばしてる
dp[0][0]=a[0]
dp[1][1]=a[1]
dp[2][2]=a[2]
for i in range(2,n):
    dp[i][0]=dp[i-2][0]+a[i]
    if i>=3:
        dp[i][1]=max(dp[i-2][1]+a[i],dp[i-3][0]+a[i])
    if i>=4:
        dp[i][2]=max(dp[i-2][2]+a[i],dp[i-3][1]+a[i],dp[i-4][0]+a[i])

if n%2==0:
    print(max(dp[-2][0],dp[-1][1]))
else:
    print(max(dp[-3][0],dp[-2][1],dp[-1][2]))

Submission status: Runtime Error

Solution code:
n = int(input())
ai = [int(i) for i in input().split()]

is_odd = True

if n % 2 == 0:
    is_odd = False

if is_odd == True:
    dp = [[0 for i in range(3)] for j in range(n)]
else:
    dp = [[0 for i in range(2)] for j in range(n)]

if n == 3:
    print(max(ai[0]+ai[2],ai[1]))
    exit()
elif n == 2:
    print(max(ai[0],ai[1]))
    exit()

dp[1][0] = ai[0]
dp[1][1] = ai[1]

if is_odd == True:
    for i in range(n+n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
        dp[i][2] = max(dp[i-4][0]+ai[i],dp[i-3][1]+ai[i],dp[i-2][2]+ai[i])
    print(max(dp[n-2][0],dp[n-1][1],dp[n-1][2]))
else:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1]))

Submission status: Runtime Error

Solution code:
n = int(input())
ai = [int(i) for i in input().split()]

is_odd = True

if n % 2 == 0:
    is_odd = False

if is_odd == True:
    dp = [[0 for i in range(3)] for j in range(n)]
else:
    dp = [[0 for i in range(2)] for j in range(n)]


if is_odd == True:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
        dp[i][2] = max(dp[i-4][0]+ai[i],dp[i-3][1]+ai[i],dp[i-2][2]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))
else:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1]))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

# aを偶数奇数の要素で振り分け
a1=[]
a2=[]

for i in range(n):
    if i%2==0:
        a1.append(a[i])
    else:
        a2.append(a[i])

# 累積和も作っておく
a3=list(itertools.accumulate(a1))
a4=list(itertools.accumulate(a2))


x1=sum(a1)
x2=sum(a2)


if n%2==0:
    ans=-float('inf')
    for i in range(n//2):
        ans=max(a3[i]+a4-a4[i],ans)
    print(max(ans,x1,x2))
else:
    # 奇数番目だけの要素を選んだ時の最大値
    ans1=sum(a1)-min(a1)
    # dp1[i]=奇数偶数奇数or偶数奇数と移動した時のi番目までのMAX
    dp1 = [-float('inf')] * (n // 2 + 1)
    dp1[0] = a1[0]
    # dp2[i]=奇数偶数or偶数のみと移動した時のi番目までのMAX
    dp2 = [-float('inf')] * (n // 2)
    dp2[0] = a2[0]
    for i in range(n // 2 - 1):
        dp2[i + 1] = max(a3[i] + a2[i + 1], dp2[i] + a2[i + 1])
        if i==0:
            dp1[i + 2] = dp2[i] + a1[i + 2]
        else:
            dp1[i + 2] = max(dp2[i] + a1[i + 2], dp1[i + 1] + a1[i + 2])
    print(max(dp1[-1], dp2[-1],ans1))

Submission status: Runtime Error

Solution code:

f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")
N = int(f.readline())
A = list(map(int, f.readline().split()))
A.insert(0, 0)

select_num = N//2
inf = -10e+10

Dp_f = [[inf] * (3) for _ in range(N+1)]
Dp_s = [[inf] * (3) for _ in range(N+1)]
# 3　次元はそれぞれStart~3つに該当

pre_margin = 0
for i in range(1,N+1):
    Start = (i-1)//2
    End = (i+1)//2
    
    cur_margin = Start
    
    for j in range(Start,End+1):
        Dp_f[i][j-cur_margin] = max(Dp_s[i-1][j-pre_margin], Dp_f[i-1][j-pre_margin])   
        # [0] in 3rd dimension  not chosen at last num
        # must be transfered from [i-1]
    for j in range(Start,End+1):
        if Dp_f[i-1][j-1-pre_margin] == inf:
            Dp_s[i][j-cur_margin] = 0 + A[i]
        else:
            Dp_s[i][j-cur_margin] = Dp_f[i-1][j-1-pre_margin]+A[i]
            
    pre_margin = cur_margin
print(max(Dp_f[-1][select_num - cur_margin], Dp_s[-1][select_num - cur_margin]))

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def make4(initial, L, M, N, O):
    return [[[[initial for i in range(O)]
                for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def make3(initial, L, M, N):
    return [[[initial for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    A = LI()
    dp_use = [-IINF] * 5
    dp_not_use = [-IINF] * 5
    dp_not_use[0] = 0

    for a in A:
        tmp_use = [-INF] * 5
        tmp_not_use = [-INF] * 5
        for current_dif in range(-3,2):
            if current_dif-1 >= -3:
                tmp_use[current_dif] = dp_not_use[current_dif - 1] + a
            if current_dif+1 < 2:
                tmp_not_use[current_dif] = max(dp_use[current_dif+1], dp_not_use[current_dif+1])
        dp_use = tmp_use
        dp_not_use = tmp_not_use

    dif = N//2 - (N-N//2)
    print(max(dp_use[dif], dp_not_use[dif]))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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 = sum(sum(a[:-1:2]))
    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]
    ans = max(ans,co)
    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: Runtime Error

Solution code:
def main():
    from functools import lru_cache

    inf = 2 * 10 ** 14 + 1

    N = int(input())
    *a, = map(int, input().split())

    @lru_cache(maxsize=None)
    def recursion(cur, need):
        """
        cur: pickableなindex
        """
        if cur >= N:
            if need == 0:
                return 0
            else:
                return -inf

        rest = N - cur
        if (rest + 1) // 2 < need:
            return -inf

        return max(
            a[cur] + recursion(cur + 2, need - 1),
            recursion(cur + 1, need)
        )

    ans = recursion(0, N // 2)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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_1 = -9999999999999999
  if max_value[1, -3] == n // 2:
    ans_3 = max_value[0, -3]
  else: 
    ans_1 = -9999999999999999
  ans = max(max(ans_1, ans_2), ans_3)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

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

a_array = np.array(a)

if n % 2 == 3:
  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: Runtime Error

Solution code:
n = int(input())
a = map(int,input().split())
sum1 = 0
sum2 = 0
for i in range(0,n,2):
  sum1 += a[i]
for i in range(1,n,2):
  sum2 += a[i]
if sum2>sum1:
  print(sum2)
else:
  print(sum1)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [[-1 * pow(10, 15)] * 3 for _ in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for i in range(N):
        if i < 2:
            continue
        dp[i][0] = dp[i-2][0] + A[i]
        if i < 3:
            continue
        dp[i][1] = max(dp[i-3][0], dp[i-2][1]) + A[i]
        if i < 4:
            continue
        dp[i][2] = max(dp[i-4][0], dp[i-3][1], dp[i-2][2]) + A[i]
    if N % 2 == 0:
        return max(dp[-1][1], dp[-2][0])
    else:
        return max(dp[-1][2], dp[-2][1], dp[-3][0])
print(main())

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(input())
A = [0] + list(map(int, input().split()))
if N <= 3:
	print(max(A))
	sys.exit()

dp = np.zeros([N//2+1, N+1], np.int64)
for i in range(1,4):
	dp[1,i] = max(A[1:i+1])

for j in range(2,(N//2)+1):
	for i in range(j*2-1, min(N+1, j*2+2)):
		dp[j,i] = max(dp[j,i-1],dp[j-1,i-2] + A[i])

print(max(dp[-1,-4:]))

Submission status: Runtime Error

Solution code:
INF = 110110110

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


def solve(now, num, sum):
    if num == N // 2:
        return sum
    need = N // 2 - num
    can = (N - now + 1) // 2
    if can < need:
        return -INF * INF
    return max(solve(now+1, num, sum), solve(now+2, num + 1, sum + A[now]))

print(solve(0, 0, 0))

Submission status: Runtime Error

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


dp0, dp1 = 0, A[0]
for i in range(1, N):
    tdp0 = max(dp0, dp1)   # 计算 dp[i][0]
    tdp1 = dp0 + nums[i]   # 计算 dp[i][1]
    dp0, dp1 = tdp0, tdp1
        
print(max(dp0, dp1))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Spyder Editor

This is a temporary script file.
"""

#f = open("/Users/naoki/Documents/Atcoder/input.txt")
N = int(input())

A = list(map(int, input().split()))
A.insert(0, 0)

select_num = N//2
Dp = [[[-9999] *2] * (select_num+1)] * (N+1)

for i in range(1,N+1):
    Start = (i-1)//2
    End = (i+1)//2
    
    for j in range(Start,End+1):
        Dp[i][j][0] = max(Dp[i-1][j][1], Dp[i-1][j][0])
        # [0] in 3rd dimension  not chosen at last num
        # must be transfered from [i-1]
    for j in range(Start,End+1):
        if j == 1:
            Dp[i][j][1] = 0 + A[i]
        else:
            Dp[i][j][1] = Dp[i-1][j-1][0]+A[i]

print(max(Dp[-1][select_num][0], Dp[-1][select_num][1]))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Spyder Editor

This is a temporary script file.
"""

#f = open("/Users/naoki/Documents/Atcoder/input.txt")
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)

select_num = N//2


Dp = [[[-9999 for _ in range(2)] for _ in range(select_num+1)] for _ in range(N+1)]

for i in range(1,N+1):
    Start = (i-1)//2
    End = (i+1)//2
    
    for j in range(Start,End+1):
        Dp[i][j][0] = max(Dp[i-1][j][1], Dp[i-1][j][0])   
        # [0] in 3rd dimension  not chosen at last num
        # must be transfered from [i-1]
    for j in range(Start,End+1):
        if j == 1:
            Dp[i][j][1] = 0 + A[i]
        else:
            Dp[i][j][1] = Dp[i-1][j-1][0]+A[i]

print(max(Dp[-1][select_num][0], Dp[-1][select_num][1]))