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())
A = list(map(int,input().split()))
if N%2 == 0:
    odd = [0]
    even = [0]
    for i in range(N):
        if i%2 == 1:
            odd.append(odd[-1]+A[i])
        else:
            even.append(even[-1]+A[i])
    ans = -float('inf')

    for i in range(N//2+1):
        ans = max(ans,odd[i]+even[N//2-i])

    print(ans)
    exit()

if N == 3:
    print(max(A))
    exit()

if N == 5:
    ans = -float('inf')
    for i in range(N):
        for j in range(i+2,N):
            ans = max(A[i]+A[j])
    print(ans)
    exit()

A.append(0)
DP = A[:2]
for i in A[2:]:
    DP.append(DP[-2]+i)
DDP = [-float('inf')]*N
for i in range(3,N):
    DDP[i] = (max(DDP[i-2]+A[i],DP[i-3]+A[i]))
DP, DDP = DDP[:],[-float('inf')]*N
DDP = [-float('inf')]*N
for i in range(3,N):
    DDP[i] = (max(DDP[i-2]+A[i],DP[i-3]+A[i]))
print(DDP[-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
n = int(input())
a = list(map(int, input().split()))
# 奇数、偶数の累積わを持つ
cum_odd = [0] * (n // 2)
cum_even = [0] * (n // 2 + 1)
cum_odd[0] = a[1]
cum_even[0] = a[0]
for i in range(1, n // 2):
    cum_odd[i] = cum_odd[i - 1] + a[2 * i + 1]
for i in range(1, (n + 1) // 2):
    cum_even[i] = cum_even[i - 1] + a[2 * i]
if n % 2 == 0:
    print(max(cum_odd[-1], cum_even[-1]))
else:
    dif = -(10 ** 10)
    for i in range((n + 1) // 2):
        dif = max(dif, -a[i] - a[i + 2] + max(a[i], max(a[i + 1], a[i + 2])))
    ans = max(cum_odd[-1], cum_even[-1] + dif)
    for i in range(n // 2):  # どこで切り替わるか？
        ans = max(ans, cum_even[i] + cum_odd[-1] - cum_odd[i])
        ans = max(ans, cum_odd[i] + cum_even[-1] - cum_even[i + 1])
    print(ans)

Submission status: Runtime Error

Solution code:
gomi = input()
num = list(map(int, input().split()))

answer = []

for i in range(len(num) // 2):
    kouho = max(set(num))
    for i in range(len(num)):
        if num[i] == kouho:
            temp2 = i
    num.remove(kouho)
    try:
        num.remove(num[temp2 + 1])
    except:
        pass
    try:
        num.remove(num[temp2 - 1])
    except:
        pass
    answer.append(kouho)
print(sum(answer))

Submission status: Runtime Error

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
from bisect import bisect_left, insort_left

def main():
    n = II()
    aa = MII()
    index = [i for i in range(n)]
    aa = list(zip(index, aa))
    aa.sort(key=lambda x: x[1], reverse=True)
    # print(aa)
    sumv = 0
    cnt = 0
    neibs = [-100]
    u = n//2
    i = 0
    while cnt < u:
        idx = aa[i][0]
        d = bisect_left(neibs, idx)
        l = neibs[d-1]
        r = neibs[d] if len(neibs) != d else neibs[d-1]
        if l == idx-1 or l == idx+1 or r == idx-1 or r == idx+1:
            i+=1; continue
        sumv += aa[i][1]
        insort_left(neibs, idx)
        # neibs.append(idx)
        cnt += 1
        i += 1
    print(sumv)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def number(n,a):
  if n%2 == 0:
    return max(sum(a[0:n:2]),sum(a[1:n:2]))


if N%2 == 0:
  print(number(N,A))
else:
  ans = []
  for i in range(N-2):
    ans.append(number(0,A[0:i])+number(i+2,A[i+2:]))
    print(max(ans))

Submission status: Runtime Error

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

if n < 20:
    d = a.copy()

    for i in range(1, n // 2):
        b = [0] * n
        c = -10**24
        for j in range(i * 2, n):
            c = max(c, a[j - 2])
            b[j] = c + d[j]

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

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

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
from functools import lru_cache

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
# 奇数の時と偶数の時、奇数の場合は真ん中を選ぶかどうか
INF = 10 ** 17

@lru_cache(None)
def F(index, n):
    if index >= N:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

AE = A[::2]
AO = A[1::2][::-1]

acumAE = [0] * (n // 2 + 1)
acumAO = [0] * (n // 2 + 1)

for i in range(n // 2):
  acumAE[i+1] = acumAE[i] + AE[i]
  acumAO[i+1] = acumAO[i] + AO[i] 

# print(acumAE, acumAO)

if n % 2 == 0:
  ans = - 10 ** 19
  for e, o in zip(acumAE, acumAO[::-1]):
    ans = max(ans, e + o)

print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

inf = 10**18
import sys
sys.setrecursionlimit(2*(10**5))

@lru_cache(maxsize=10**5)
def solve(ind, cnt):
    if cnt == 0:
        return 0
    if ind >= N:
        return -inf
    res1 = solve(ind + 1, cnt)
    res2 = solve(ind + 2, cnt - 1)
    if res1 == -inf:
        return res2 + arr[ind]
    elif res2 == -inf:
        return res1
    res = max(res1, res2 + arr[ind])
    return res

N = int(input())
arr = [int(x) for x in input().split()]
print(solve(0, int(N / 2)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n = n_in()

A = l_in()

if n%2 == 0:
    res = sum(A[::2])
    dp = [[0,0] for _ in range(n)]
    #dp[i][k]は k回スキップして，i番目を使う確定した時の最大

    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] + A[i], dp[i-2][1] + A[i])

    print(max(res, dp[n-1][1]))
    exit()

res = sum(A[::2])-A[-1]
dp = [[0,0] for _ in range(n)]
#dp[i][k]は k回スキップして，i番目を使う確定した時の最大

dp[0][0] = A[0]
dp[1][1] = A[1]
dp[2][0] = A[0]+A[2]

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

#print(dp)    
res = max(res, dp[n-2][1])

dp = [[0,0,0] for _ in range(n)]
#dp[i][k]は k回スキップして，i番目を使う確定した時の最大

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

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

#print(dp)    
print(max(res, dp[n-1][2]))

Submission status: Runtime Error

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

AE = A[::2]
AO = A[1::2][::-1]

acumAE = [0] * (n // 2 + 1)
acumAO = [0] * (n // 2 + 1)

for i in range(n // 2):
  acumAE[i+1] = acumAE[i] + AE[i]
  acumAO[i+1] = acumAO[i] + AO[i] 

# print(acumAE, acumAO)

if n % 2 == 0:
  ans = - 10 ** 19
  for e, o in zip(acumAE, acumAO):
    ans = max(ans, e + o)

print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

inf = 10**18

@lru_cache(maxsize=10**5)
def solve(ind, cnt):
    if cnt == 0:
        return 0
    if ind >= N:
        return -inf
    res1 = solve(ind + 1, cnt)
    res2 = solve(ind + 2, cnt - 1)
    if res1 == -inf:
        return res2 + arr[ind]
    elif res2 == -inf:
        return res1
    res = max(res1, res2 + arr[ind])
    return res

N = int(input())
arr = [int(x) for x in input().split()]
print(solve(0, int(N / 2)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n = n_in()

A = l_in()

if n%2 == 0:
    res = sum(A[::2])
    dp = [[0,0] for _ in range(n)]
    #dp[i][k]は k回スキップして，i番目を使う確定した時の最大

    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][0] = A[1]+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] + A[i], dp[i-2][1] + A[i])

    print(max(res, dp[n-1][1]))
    exit()

res = sum(A[::2])-A[-1]
dp = [[0,0] for _ in range(n)]
#dp[i][k]は k回スキップして，i番目を使う確定した時の最大

dp[0][0] = A[0]
dp[1][1] = A[1]
dp[2][0] = A[1]+A[2]

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

#print(dp)    
res = max(res, dp[n-2][1])

dp = [[0,0,0] for _ in range(n)]
#dp[i][k]は k回スキップして，i番目を使う確定した時の最大

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

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

#print(dp)    
print(max(res, dp[n-1][2]))

Submission status: Runtime Error

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

left=[0]*N
right=[0]*N

left[0]=A[0]
left[1]=A[1]
for i in range(2,N):
    left[i]=A[i]+left[i-2]
right[-1]=A[-1]
right[-2]=A[-2]
for i in range(N-3,-1,-1):
    right[i]=A[i]+right[i+2]

ans=0
if N%2==0:
    ans=max(right[0],left[-1])
    for i in range(N-2):
        if i%2==0:
            continue
        ans=max(ans,left[i]+right[i+2])
    num=9/0
else:
    P=[0]*N
    Q=[0]*N
    P[-2]=A[-2]
    Q[-2]=A[-1]
    for i in range(-4,-N-1,-1):
        if i%2==0:
            P[i]=A[i]+max(P[i+2],Q[i+2])
            Q[i]=A[i+1]+Q[i+2]

    data=[0]*N
    for i in range(N):
        data[i]=max(P[i],Q[i])
    
    qqq=0
    for i in range(N-2):
        if i%2==0:
            #使わない
            ans=max(ans,qqq+data[i+1])
            qqq+=A[i]
    ans=max(ans,qqq)
    
print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

inf = 10**18

@lru_cache(maxsize=-1)
def solve(ind, cnt):
    if cnt == 0:
        return 0
    if ind >= N:
        return -inf
    res1 = solve(ind + 1, cnt)
    res2 = solve(ind + 2, cnt - 1)
    if res1 == -inf:
        return res2 + arr[ind]
    elif res2 == -inf:
        return res1
    res = max(res1, res2 + arr[ind])
    return res

N = int(input())
arr = [int(x) for x in input().split()]
print(solve(0, int(N / 2)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n = n_in()

A = l_in()

if n%2 == 0:
    res = sum(A[::2])
    dp = [[-1,-1] for _ in range(n)]
    #dp[i][k]は k回スキップして，i番目を使う確定した時の最大

    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][0] = A[1]+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] + A[i], dp[i-2][1] + A[i])

    print(max(res, dp[n-1][1]))
    exit()

res = sum(A[::2])-A[-1]
dp = [[0,0] for _ in range(n)]
#dp[i][k]は k回スキップして，i番目を使う確定した時の最大

dp[0][0] = A[0]
dp[1][1] = A[1]
dp[2][0] = A[1]+A[2]

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

#print(dp)    
res = max(res, dp[n-2][1])

dp = [[0,0,0] for _ in range(n)]
#dp[i][k]は k回スキップして，i番目を使う確定した時の最大

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

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

#print(dp)    
print(max(res, dp[n-1][2]))

Submission status: Runtime Error

Solution code:
A = list(map(int,input().split()))
B = sorted(enumerate(A), key=itemgetter(1),reverse=True)
##print(B)
ans = 0
cnt = 0
flag = [1 for _ in range(N)]
for i,j in B:
    if flag[i]:
        ans += j
        if i < N-1:
            flag[i+1] = 0
        if i > 0:
            flag[i-1] = 0
        flag[i] = 0
        cnt += 1
    if cnt == N//2:
        break

print(ans)

Submission status: Runtime Error

Solution code:
import sys

n, *a = map(int, sys.stdin.read().split())
a = [0] + a

s = a.copy()
for i in range(n):
    s[i+1] += s[i]
se = [None] * (n + 1); se[0] = 0
for i in range(0, n - 1, 2):
    se[i+2] = a[i+2] + se[i]
for i in range(1, n + 1, 2):
    se[i] = se[i-1]

def dfs(l, r, c):
    if c == 0: return 0
    if not ((r - l + 1) & 1):
        s1 = se[r] - se[l-1]
        s2 = s[r] - se[r] - (s[l-1] - se[l-1])
        return max(s1, s2)
    if c == (r - l + 2) // 2:
        return sum(a[l:r+1:2])
    return max(a[l] + dfs(l + 2, r, c - 1), a[r] + dfs(l, r - 2, c - 1), dfs(l + 1, r - 1, c))

def main():
    print(dfs(1, n, n // 2))

if __name__ ==  '__main__':
    main()

Submission status: Runtime Error

Solution code:
def find_max_sum(arr):
    incl = 0
    excl = 0

    for i in arr:
        new_excl = excl if excl > incl else incl
        incl = excl + i
        excl = new_excl

    return (excl if excl > incl else incl)

N = int(input())
ar = list(map(int, input().rstrip().split()))
print(selectHalf(ar))

Submission status: Runtime Error

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

def f(l,m):
    if l==[]:
        return -10**100
    if m==1:
        return max(l)
    if len(l)<=2:
        return -10**100
    return max(f(l[1:],m),l[0]+f(l[2:],m-1))

print(f(a,n//2))

Submission status: Runtime Error

Solution code:
from python import atcoder

N=input ()
for i in range (1,N+1):
      print (atcoder.12apr2020.answer)

Submission status: Runtime Error

Solution code:
# coding: utf-8
 
N  = int(input())
As = list(input().rstrip().split(" "))
sum1 = 0
sum2 = 0

Bs = list.sort(As, reverse=True)

paopao = int(round(N/2))

for i in range(paopao):
        if Bs[2i] > 0:
            sum1 += Bs[2i]
        else:
            break

for i in range(paopao):
        if Bs[2i+1] > 0:
            sum2 += Bs[2i+1]
        else:
            break

if sum1 > sum2:
    print(sum1)
else:
    print(sum2)

Submission status: Runtime Error

Solution code:
n=int(input())
l=list(map(int,input().split()))
INF=float('inf')
dp=[[-INF]*3 for i in range(n+1)]
dp[1][0]=l[0]
dp[2][1]=l[1]
dp[3][2]=l[2]
if n%2:
    for i,j in enumerate(l,1):
        dp[i][0]=max(dp[i-2][0]+j,dp[i][0])
        dp[i][1]=max(dp[i-2][1]+j,dp[i-3][0]+j,dp[i][1])
        dp[i][2]=max(dp[i-2][2]+j,dp[i-3][1]+j,dp[i-4][0]+j,dp[i][2])
    print(max(dp[-3][0],max(dp[-2]),max(dp[-1])))
else:
    print(max(sum(l[::2]),sum(l[1::2])))

Submission status: Runtime Error

Solution code:
N=int(input())
A=input()
if N%2==0:
  ans1=0
  ans2=0
  for i in range(N//2):
    ans1+=A[2*i]
  for i in range(N//2):
    ans2+=A[2*i+1]
  ans=max(ans1,ans2)
else:
  ans=0
  for i in range(N//2):
    ans+=A[2*i+1]
print(ans)

Submission status: Runtime Error

Solution code:
import sys

n, *a = map(int, sys.stdin.read().split())
a = [0] + a

s = a.copy()
for i in range(n):
    s[i+1] += s[i]
se = [None] * (n + 1); se[0] = 0
for i in range(0, n - 1, 2):
    se[i+2] = a[i+2] + se[i]
for i in range(1, n + 1, 2):
    s[i] = s[i-1]

def dfs(l, r, c):
    if c == 0: return 0
    if not ((r - l + 1) & 1):
        s1 = se[r] - se[l-1]
        s2 = s[r] - se[r] - (s[l-1] - se[l-1])
        return max(s1, s2)
    if c == (r - l + 2) // 2:
        return sum(a[l:r+1:2])
    return max(a[l] + dfs(l + 2, r, c - 1), a[r] + dfs(l, r - 2, c - 1), dfs(l + 1, r - 1, c))

def main():
    print(dfs(1, n, n // 2))

if __name__ ==  '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys
import numpy as np


def main():
    N = int(sys.stdin.readline().strip())
    A = np.array([int(x) for x in sys.stdin.readline().strip().split()])
    print(select_half(N//2, A))


def select_half(n, a):
    if len(a) % 2 == 0:
        return select_half_even(n, a)
    else:
        return select_half_odd(n, a)


def select_half_even(n, a):
    return max(np.sum(a[0::2]),
               np.sum(a[1::2]))


def select_half_odd(n, a):
    print(a)
    if len(a) == 1:
        return a[0]
    s_odd = select_half_odd(n-1, a[2:])
    s1 = a[0] + s_odd
    s2 = select_half_even(n, a[1:])
    # print("n = {}, a = {}".format(n, a))
    # print("s_odd = {}, s1 = {}, s2 = {}".format(s_odd, s1, s2))
    return max(s1, s2)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

n = n_in()

A = l_in()

if n%2 == 0:
    res = sum(A[::2])
    dp = [[-1,-1] for _ in range(n)]
    #dp[i][k]は k回スキップして，i番目を使う確定した時の最大

    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][0] = A[1]+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] + A[i], dp[i-2][1] + A[i])

    print(max(res, dp[n-1][1]))
    exit()

res = sum(A[::2])-A[-1]
dp = [[-1,-1] for _ in range(n)]
#dp[i][k]は k回スキップして，i番目を使う確定した時の最大

dp[0][0] = A[0]
dp[1][1] = A[1]
dp[2][0] = A[1]+A[2]

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

#print(dp)    
res = max(res, dp[n-2][1])

dp = [[-1,-1,-1] for _ in range(n)]
#dp[i][k]は k回スキップして，i番目を使う確定した時の最大

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

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

#print(dp)    
print(max(res, dp[n-1][2]))

Submission status: Runtime Error

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

def f(l,m):
    if l==[]:
        return -10**100
    if m==1:
        return max(l)
    return max(f(l[1:],m),l[0]+f(l[2:],m-1))

print(f(a,n//2))

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
a0=[a[0],a[0]]
a1=[0,a[1]]
a2=[0,0,a[2]]
for i in range(2,n):
    if i%2==0:
        a0.append(a0[i-2]+a[i])
        a1.append(a1[i-1])
        if i>=4: a2.append(max(a2[i-2],a1[i-3],a0[i-4])+a[i])
    else:
        a0.append(a0[i-1])
        a1.append(max(a1[i-2],a0[i-3])+a[i])
        a2.append(a2[i-1])

if n%2==1: print(max(a0[n-1],a1[n-1],a2[n-1]))
else: print(max(a0[n-1],a1[n-1]))

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
memo = [False]*(N+1)

s_idx = np.argsort(A)[::-1]
ans = 0
cnt = 0
i = 0
while cnt < N//2:
  idx = s_idx[i]
  if not memo[idx+1] and not memo[idx-1]:
    memo[idx] = True
    ans += A[idx]
    cnt += 1
  i += 1
print(ans)

Submission status: Runtime Error

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

mx = 0
def dfs(i,c,s):
  global mx
  #print(i,c,s)
  if c == n//2:
    mx = max(s,mx)
    return
  if i > n-1:
    return
  dfs(i+2,c+1,s+a[i])
  dfs(i+3,c+1,s+a[i])
  dfs(i+4,c+1,s+a[i])
  
dfs(0,0,0)
dfs(1,0,0)
dfs(2,0,0)

print(mx)

Submission status: Runtime Error

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

def dp(i,j,k):
    if j==0:
        return 0
    if i==0 and j==0 and k==0:
        memo[(i,j,k)] = 0
        return 0
    elif i==0 and j==1 and k==1:
        memo[(i,j,k)] = a[0]
        return a[0]
    if (i,j,k) in memo:
        return memo[(i,j,k)]
    else:
        if k==0:
            if i>=j:
                x = max(dp(i-1,j,0),dp(i-1,j,1))
            else:
                x=-999999999999999
        else:
            x = dp(i-1,j-1,0) + a[i]
        memo[(i,j,k)] = x
        return x
print(max(dp(n-1,n//2,0), dp(n-1,n//2,1)))

Submission status: Runtime Error

Solution code:
dp = {}
def dfs(l, n):
    if l < n * 2 or n == 0 or l <= 0:
        return float('-inf')
    if n == 1:
        return max(A[:l])
    if (l, n) not in dp:
        dp[(l, n)] = max(A[l-1] + dfs(l-2, n-1), dfs(l-1, n))
    return dp[(l, n)]

N = int(input())
A = list(map(int, input().split()))
dfs(N, N // 2)
print(dp[(N, N // 2)])

Submission status: Runtime Error

Solution code:
import sys

n, *a = map(int, sys.stdin.read().split())
a = [0] + a

s = a.copy()
for i in range(n):
    s[i+1] += s[i]
se = [None] * (n + 1); se[0] = 0
for i in range(0, n - 1, 2):
    se[i+2] = a[i+2] + se[i]
for i in range(1, n + 1, 2):
    s[i] = s[i-1]

def dfs(l, r):
    if r - l <= 1: return 0
    if not n & 1:
        s1 = se[r] - se[l-1]
        s2 = s[r] - se[r] - (s[l-1] - se[l-1])
        return max(s1, s2)
    return max(a[l] + dfs(l + 2, r), a[r] + dfs(l, r - 2))

def main():
    print(dfs(1, n))

if __name__ ==  '__main__':
    main()

Submission status: Runtime Error

Solution code:
from operator import itemgetter
N = int(input())
A = list(map(int,input().split()))
B = sorted(enumerate(A), key=itemgetter(1),reverse=True)

ans = 0
tmp = 0
cnt = 0

while cnt < N//2:
    if A[B[tmp][0]] < 1e10:##その数を選べる
        cnt += 1
        ans += B[tmp][1]
        if cnt >= N//2:
            break
        if B[tmp][0] > 0:
            A[B[tmp][0]-1] = 1e11
        if B[tmp][0] < N-1:
            A[B[tmp][0]+1] = 1e11
        A[B[tmp][0]] = 1e11
    tmp += 1

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
s = [0]*N
for i in range(N):
    s[i] = s[i-2]+A[i]

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

print(dp[-1])

Submission status: Runtime Error

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

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

print(mx)

Submission status: Runtime Error

Solution code:
n=int(input())
c=0
v=0
x=0
o=1
p=1
max=0
maxe=0
c=int(n/2)
l=[]
d=[]
k=0
h=0
for i in range(n):
      l.append(int(input())
for j in l[::2]:
      l.remove(i)
      d.append(i)
for i in l[::c]:
      v=c*p
      sum=0
      while k<v:
           sum+=l[k]
           k=k+1
      if sum>max:
           max=sum
      p=p+1
for j in d[::c]:
      x=c*o
      sume=0
      while h<x:
           sume+=d[h]
           h=h+1
      if sume>maxe:
           maxe=sum
      o=o+1
if max>maxe:
      print(max)
else:
     print(maxe)

Submission status: Runtime Error

Solution code:
n=int(input())
c=0
v=0
x=0
o=1
p=1
max=0
maxe=0
c=int(n/2)
l=[]
d=[]
k=0
h=0
for i in range(n):
      l.append(int(input())
for j in l[::2]:
      l.remove(i)
      d.append(i)
for i in l[::c]:
      v=c*p
      sum=0
      while k<v:
           sum+=l[k]
           k=k+1
      if sum>max:
           max=sum
      p=p+1
for j in d[::c]:
      x=c*o
      sume=0
      while h<x:
           sume+=d[h]
           h=h+1
      if sume>maxe:
           maxe=sum
      o=o+1
 if max>maxe:
      print(max)
else:
     print(maxe)

Submission status: Runtime Error

Solution code:
from operator import itemgetter
N = int(input())
A = list(map(int,input().split()))
B = sorted(enumerate(A), key=itemgetter(1),reverse=True)
ans = 0
tmp = 0
cnt = 0
while 1:
    if A[B[tmp][0]] < 1e10:
        cnt += 1
        ans += B[tmp][1]
        if cnt >= N//2:
            break
        if B[tmp][0] > 0:
            A[B[tmp][0]-1] = 1e11
        if B[tmp][0] < N-1:
            A[B[tmp][0]+1] = 1e11
        A[B[tmp][0]] = 1e11
    tmp += 1

print(ans)

Submission status: Runtime Error

Solution code:
dp = {}
def dfs(l, n):
    if l < n * 2:
        return float('-inf')
    if n == 1:
        return max(A[:l])
    if (l, n) not in dp:
        dp[(l, n)] = max(A[l-1] + dfs(l-2, n-1), dfs(l-1, n))
        # print((l, n), dp[(l, n)])
    return dp[(l, n)]

N = int(input())
A = list(map(int, input().split()))
dfs(N, N // 2)
print(dp[(N, N // 2)])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

@lru_cache(None)
def dfs(p, remain):

    n = len(arr)

    if remain == 0 or p >= n:
        return 0

    if remain == 1:
        return max(arr[p:])
        
    len_remain = n - (p + 1)

    t = -float('inf')
    if (remain - 1) * 2 + 1 <= len_remain:
        t = dfs(p + 1, remain)

    t2 = arr[p] + dfs(p + 2, remain - 1)

    return max(t, t2)

    


n = int(input())

arr = list(map(int, input().split()))

ans = dfs(0, n // 2)

print (ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
s = [0]*N
for i in range(N):
    s[i] = s[i-2]+A[i]

def f(n):
    if n==0:
        return 0
    elif n ==1:
        return max(A[0],A[1])
    elif n==2:
        return max(A[0],A[1],A[2])
    elif n%2==1:
        return max(A[n]+f(n-2),s[n-1])
    else:
        return max(A[n]+f(n-2),A[n-1]+f(n-3),s[n-2])

ans = f(N-1)
print(ans)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
n=int(input())
c=0
v=0
x=0
o=1
p=1
max=0
maxe=0
c=int(n/2)
l=[]
d=[]
k=0
s=0
for i in range(n):
      l.append(int(input())
for j in l[::2]:
      l.remove(i)
      d.append(i)
for i in l[::c]:
      v=c*p
      sum=0
      while k<v:
           sum+=l[k]
           k=k+1
      if sum>max:
           max=sum
      p=p+1
for j in d[::c]:
      x=c*o
      sume=0
      while h<x:
           sume+=d[s]
           s=s+1
      if sume>maxe:
           maxe=sum
      o=o+1
 if max>maxe:
      print(max)
else:
     print(maxe)

Submission status: Runtime Error

Solution code:
from operator import itemgetter
N = int(input())
A = list(map(int,input().split()))
B = sorted(enumerate(A), key=itemgetter(1),reverse=True)

ans = 0
tmp = 0
cnt = 0
while 1:
    if A[B[tmp][0]] < 1e10:
        ans += B[tmp][1]
        cnt += 1
        if cnt >= N//2:
            break
        if B[tmp][0] > 0:
            A[B[tmp][0]-1] = 1e10
        if B[tmp][0] < N-1:
            A[B[tmp][0]+1] = 1e10
        A[B[tmp][0]] = 1e10
    tmp += 1

print(ans)

Submission status: Runtime Error

Solution code:
dp = {}
def dfs(l, n):
    if l <= 0:
        return -10**9 - 10
    if n == 1:
        return max(A[:l])
    if (l, n) not in dp:
        dp[(l, n)] = max(A[l-1] + dfs(l-2, n-1), dfs(l-1, n))
    return dp[(l, n)]

N = int(input())
A = list(map(int, input().split()))
dfs(N, N // 2)
print(dp[(N, N // 2)])

Submission status: Runtime Error

Solution code:
from operator import itemgetter
N = int(input())
A = list(map(int,input().split()))
B = sorted(enumerate(A), key=itemgetter(1),reverse=True)

ans = 0
tmp = 0
cnt = 0
while cnt <= N//2:
    if A[B[tmp][0]] != 1e10:
        ans += B[tmp][1]
        if B[tmp][0] > 0:
            A[B[tmp][0]-1] = 1e10
        if B[tmp][0] < N-1:
            A[B[tmp][0]+1] = 1e10
        A[B[tmp][0]] = 1e10
        cnt += 1
        if cnt >= N//2:
            break
    tmp += 1

print(ans)