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=input()
List=list(map(int,input().split()))
def find(List):
    if len(List)==1:
        return(int(List[0])
    else:
        if len(List)==2:
            if List[0]>=List[1]:
                return(int(List[0]))
            else:
                return(int(List[1]))
        else:
               if len(List)%2==0:
                List2=[]
                List3=[]
                for i in range(0,len(List)-2):
                    List2.append(List[i])
                for i in range(0,len(List)-3):
                    List3.append(List[i])
                sub1=int(int(List[len(List)-1])+find(List2))
                sub2=int(int(List[len(List)-2])+find(List3))
                if sub1 >= sub2:
                    return(sub1)
                else:
                    return(sub2)
            else:
                List2=[]
                List3=[]
                for i in range(0,len(List)-2):
                    List2.append(List[i])
                for i in range(0,len(List)-3):
                    List3.append(List[i])
                sub1=int(int(List[len(List)]-1)+find(List2))
                sub2=int(int(List[len(List)-2])+find(List3))
                sub3=0
                for i in range(0,len(List)//2):
                    sub3+=List[2*i]
                if sub1 >= sub2:
                    if sub1 >= sub3:
                        return(sub1)
                    else:
                        if sub3>=sub2:
                            return(sub3)
                        else:
                            return(sub2)
                else:
                    if sub2 >= sub3:
                        return(sub2)
                    else:
                        if sub3>=sub1:
                            return(sub3)
                        else:
                            return(sub1)
print(find(List))

Submission status: Runtime Error

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

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

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

main()

Submission status: Runtime Error

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

if N % 2 == 0:
    count_odd = 0
    count_even = 0
    for i, Ai in enumerate(A):
        if i % 2 == 0:
            count_odd += Ai
        else:
            count_even += Ai
    print(max([count_even, count_odd]))

else:
    A_min = min(A)
    index = 0
    for i, Ai in enumerate(A):
        if Ai == A_min:
            index = i
    
    count_odd = 0
    count_even = 0
    for k in range(i):
        if i % 2 == 0:
            count_odd += Ai
        else:
            count_even += Ai
    amount = max([count_event, count_odd])
    
    count_odd = 0
    count_even = 0
    for k in range(i, N):
        if i % 2 == 0:
            count_odd += Ai
        else:
            count_even += Ai
    amount += max([count_even, count_odd]) 
    print(amount)

Submission status: Runtime Error

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

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

else:
    pata, patb = [0], [0]
    for i in range(n):
        if i % 2 == 0:
            pata.append(pata[-1] + a[i])
        else:
            patb.append(patb[-1] + a[i])
    
    ans = max(sum(a[2::2]), sum(a[0:-1:2]))
    
    for i in range(0, n // 2 + 1):
        ans = max(ans, pata[i + 1] + patb[n // 2] - patb[i])
        
    for i in range(0, n // 2 + 1):
        ans = max(ans, patb[i + 1] + pata[n // 2 + 1] - pata[i + 1])
    
    print(ans)

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)<m:
        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:
N = int(input())
A = list(map(int, input().split(" ")))

even = A[0::2]
odd = A[1::2]

se = [0]
sum = 0
for e in even:
    sum += e
    se.append(sum)

so = [0]
sum = 0
for o in odd:
    sum += o
    so.append(sum)

ans = 0
half = int(N/2)
if N % 2 == 0:
    for i in range(half+1):
        ans = max(ans, se[i] + so[half] - so[i])
else:
    for i in range(half+1):
        ans = max(ans, se[i] + so[half] - so[i])
        ans = max(ans, so[i] + se[half+1] - se[i+1])
        ans = max(ans, se[half+1] + odd[i] - even[i] - even[i+1])
    ans = max(ans, se[-1] - min(even))

print(ans)

Submission status: Runtime Error

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N = int(input())
A = list(map(int, input().split()))
INF = 10**9 + 1

dp = [[-INF]*(N//2+1) for _ in range(N+1)]
dp[1][1] = max(-INF, A[0])

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

print(dp[-1][N//2])

Submission status: Runtime Error

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

    
b = a[:4]
e = [True]*4

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

Submission status: Runtime Error

Solution code:
# coding: utf-8
N = int(input())
a = list(map(int, input().split()))

def max_even(n, a): # aからn個選ぶ
    if len(a) <= 2:
        return max(a)
    else:
        return max(a[0]+max_even(n-1, a[2:]), a[1]+max_odd(n-1, a[3:]))

def max_odd(n, a): # aからn個選ぶ
    if len(a) <= 3:
        if n == 1:
            return max(a)
        elif len(a)==3 and a==2:
            return a[0]+a[2]
    else:
        return max(a[0]+max_odd(n-1, a[2:]), a[1]+max_even(n-1, a[3:]), a[2]+max_odd(n-1, a[2:]))


if N%2==0:
    ans = max_even(N//2, a)
else:
    ans = max_odd(N//2, a)
    
print(ans)

Submission status: Runtime Error

Solution code:
import sys
N = int(input())
A = list(map(int, input().split()))
if N % 2 == 0:
  print(max(sum([a for a in A[::2]]), sum([a for a in A[1::2]])))
  sys.exit(0)

memo = [False]*(N+1)

s_idx = sorted([(a, i) for i, a in enumerate(A)], key=lambda x:x[0], reverse=True)
print(s_idx)
ans = 0
cnt = 0
i = 0
while cnt < N//2:
  print(i)
  a, idx = s_idx[i]
  if not memo[idx+1] and not memo[idx-1]:
    memo[idx] = True
    ans += a
    cnt += 1
  i += 1
print(ans)

Submission status: Runtime Error

Solution code:
def solve(pick, idx, sum):

    if pick == 0: 
        return sum
    if idx >= n: return -float('inf')

    if (pick, idx) in dp: return dp[(pick, idx)]

    total = 0
    for i in range(idx, n):
        total = max(total, solve(pick-1, i+2, sum+A[i]))

    dp[(pick, idx)] = total
    return total

n = int(input())
A = list(map(int, input().split()))
dp = {}
pick = n//2+1
total = -float('inf')
for i, val in enumerate(A):
    total = max(total, solve(pick-1, i+2, val))
print(total)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int, input().split()))
b=0
c=0
d=[]
e=[]
if n%2==0:
    for i in range(n//2):
        b+=a.pop()
        c+=a.pop()
    print(max(b,c))
else:
    f=a.pop()
    g=a[0]
    for i in range(((n-1)//2)):
        print(a,(n-1//2))
        b+=a.pop()
        c+=a.pop()

    print(max(b,c,c-g+f))

Submission status: Runtime Error

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

if N % 2 == 0:
    count_odd = 0
    count_even = 0
    for i, Ai in enumerate(A):
        if i % 2 == 0:
            count_odd += Ai
        else:
            count_even += Ai
    print(max([count_even, count_odd]))

else:
    A_min = min(A)
    index = 0
    for i, Ai in enumerate(A):
        if Ai == A_min:
            index = i
    
    count_odd = 0
    count_even = 0
    for k in range(i):
        if i % 2 == 0:
            count_odd += Ai
        else:
            count_even += Ai
    amount = max([count_event, count_odd])
    
    count_odd = 0
    count_even = 0
    for k in range(i, N):
        if i % 2 == 0:
            count_odd += Ai
        else:
            count_even += Ai
    amount += max([count_event, count_odd]) 
    print(amount)

Submission status: Runtime Error

Solution code:
N = int(input())
AA = list(map(int,input().split()))
AAA = []
for i in range(N):
  AAA.append([i,AA[i]])
AAs = sorted(AAA, key=lambda x: x[1], reverse=True)
AAA_copy = AAA.copy()
del(AAA_copy[AAs[0][0]])
ext_num = int(N/2)
maximum1 = 0
for i in range(ext_num):
  maximum1 += AAs[0][1]
  if AAs[0][0]==0:
    del(AAA[AAs[0][0]:AAs[0][0]+2])
  elif AAs[0][0]==len(AAA)-1:
    del(AAA[AAs[0][0]-1:AAs[0][0]+1])
  else:
    del(AAA[AAs[0][0]-1:AAs[0][0]+2])
  AAs = sorted(AAA, key=lambda x: x[1], reverse=True)
maximum2 = 0
AAA = AAA_copy
for i in range(ext_num):
  maximum2 += AAs[0][1]
  if AAs[0][0]==0:
    del(AAA[AAs[0][0]:AAs[0][0]+2])
  elif AAs[0][0]==len(AAA)-1:
    del(AAA[AAs[0][0]-1:AAs[0][0]+1])
  else:
    del(AAA[AAs[0][0]-1:AAs[0][0]+2])
  AAs = sorted(AAA, key=lambda x: x[1], reverse=True)
if maximum1 > maximum2:
  print(maximum1)
else:
  print(maximum2)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

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

main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

dp=np.array([[0]*n for i in range((n//2)+1)])

def f(l,m):
    if l==[]:
        return -10**100
    if m==1:
        return max(l)
    if -(-len(l)//2)<m:
        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:
n = int(input())
a = list(map(int,input().split()))
b = [a]*n

a1 = []
a2 = []
if n%2 == 0:
    for i in range(int(n/2)):
        a1.append(a[2*i])
        a2.append(a[2*i +1])
    print(max(sum(a1),sum(a2)))

if n%2 == 1:
    for i in range(n):
        copy = a[i]
        del copy[i]
        for j in range(int((n-1)/2)):
            a1.append(copy[j*2])
            a2.append(copy[j*2+1])
            print(j)
    print(max(sum(a1),sum(a2)))

Submission status: Runtime Error

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

    for i in range(N):
        if i<3:
            if i==0:
                dp[i][0]=A[0]
            if i==1:
                dp[i][1]=A[0]
                dp[i][0]=A[1]
            if i==2:
                dp[i][2]=A[2]
                dp[i][1]=A[1]
                dp[i][0]=A[0]+A[1]
        else:
            for j in range(3):
                if j==0:#ここでも2こずつ規則よく飛ばすと決めた
                    dp[i][0]=max(dp[i][0],dp[i-2][0]+A[i])
                elif j==1:#1回だけ無茶した
                    dp[i][1]=max(dp[i][1],dp[i-2][1]+A[i],dp[i-3][0]+A[i])
                else:
                    dp[i][2]=max(dp[i][2],dp[i-2][2]+A[i],dp[i-3][1]+A[i],dp[i-4][0]+A[i])
print(max(dp[N-1]))

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(e) for e in input().split()]
ans = 0;
for i in range(n/2):
  ans += a(-1-(i*2))
print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
N=int(input())

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

dp=[[-10**9 for i in range(N)] for j in range(3)]
dp[0][0]=A[0]
dp[1][1]=A[1]
dp[2][2]=A[2]

for n in range(3):
    for index in range(N):
        if dp[n][index]!=-1:
            if n!=2 and index+3<N:
                dp[n+1][index+3]=max(dp[n+1][index+3],dp[n][index]+A[index+3])
            if n==0 and index+4<N:
                dp[n+2][index+4]=max(dp[n+2][index+4],dp[n][index]+A[index+4])
            if index+2<N:
                dp[n][index+2]=max(dp[n][index+2],dp[n][index]+A[index+2])

a=(dp[0][-1])
b=(dp[1][-1])
c=(dp[2][-1])

print(max(a,b,c))

Submission status: Runtime Error

Solution code:
import heapq

n = int(input())
a = list(map(lambda x: -1 * int(x), input().split))
heapq.heapify(a)

items = []
how_many = n // 2
for i in range(n // 2):
    items.append(heapq.heappop(a))
print(sum(items))

Submission status: Runtime Error

Solution code:
n = int(input())
A = list(map(int, input().split()))
k = n//2
if n%2==0:
    temp1 = 0
    temp2 = 0
    flag = False
    for a in A:
        if flag:
            temp2 += a
        else:
            temp1 += a
        flag = not flag
    result = max(temp1, temp2)
else:
    dp = [0 for i in range(n+1)]
    dp[1] = A[0]
    dp[2] = A[1]
    for i in range(3, n+1):
        dp[i]=max(dp[i-2], dp[i-3])+A[i-1]
    result = dp[-1]
print(dp,result)

Submission status: Runtime Error

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

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)
    sumv = 0
    cnt = 0
    neibs = [-100]
    u = n//2
    i = 0
    while cnt < u:
        idx = aa[i][0]
        d = bisect_left(neibs, idx)
        if d-1<0:
            l = -10
            r = -10
        else:
            l = neibs[d-1] if d != 1 else -10
            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)
        cnt += 1
        i += 1
    print(sumv)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
#二部探索

import numpy as np
n = int(input())
a = np.array(list(map(int, input().split())))
inda = np.argsort(-a)
lena = inda.size
judge = [True for i in range(lena+2)]
take = n//2
ans = 0
ind = 0
count = 0
while True:
    if judge[inda[ind]+2] and judge[inda[ind]]:
        ans += a[inda[ind]]
        count+=1
        judge[inda[ind] + 1] = False
        ind += 1
        if count==take:
            break
    else:
        ind+=1
print(ans)

Submission status: Runtime Error

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

if n < 1000:
    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[:4]
e = [True]*4

for i in range(1, n // 2):
    c = [0] * 4
    f = [False]*4
    d = -10**24
    for j in range(4):
        if 2 * i + j >= n:
            continue
        if not e[j]:
            continue
        d = max(d, b[j])
        c[j] = d + a[2 * i + j]
        f[j] = True
    e = f.copy()
    b = c.copy()
ans = -10 ** 24
for i in range(240):
    if e[i]:
        ans = max(ans, b[i])
print(e)
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
dp=[[0 for i in range(0,3)] for i in range(0,N)]
dp[0][2]=A[0]
dp[0][1]=A[0]
dp[0][0]=0
dp[1][2]=A[1]
dp[1][1]=max(A[1],A[0])
dp[1][0]=max(A[1],A[0])

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

test1=dp[N-1][0]

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

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

test2=dp[N-2][0]

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

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

test3=dp[N-3][0]

print(max(test1,test2,test3))

Submission status: Runtime Error

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

if N%2 == 0:
    sumA = 0
    sumB = 0
    for i in range(N):
        if i%2==0:
            sumA += A[i]
        else:
            sumB += A[i]
    print(max(sumA, sumB))
else:
    partSum = [0] * N
    partSum[0] = A[0]
    partSum[1] = A[1]
    #odd_part = [0] * N
    #even_part[0] = A[0]
    for i in range(2,N):
        partSum[i] = (partSum[i-2] + A[i])

    ans = partSum[N-2]
    # blockとblock+1は選択されない
    for block in range(N-1):
        #print("========================block=",block)
        tmp = 0
        if block%2 == 0:
            #left
            if block >= 2:
                tmp += max(partSum[block-1], partSum[block-2]) # TODO: outbounds
            #   print("left : ",tmp, " || " , partSum[block-1], partSum[block-2])
            #right
            tmp += (partSum[N-1] - partSum[block])
            #print("right : " , (partSum[N-1] - partSum[block]))
        else:
            #left
            tmp += partSum[block-1]
            #print("left: " , tmp)
            #right
            if block < N-2:
                tmp += max((partSum[N-2] - partSum[block]), (partSum[N-1] - partSum[block+1]))
            #print("right : " , max((partSum[N-2] - partSum[block]), (partSum[N-1] - partSum[block+1])), (partSum[N-2] - partSum[block]), (partSum[N-1] - partSum[block+1]))
        #print("ppp = ",tmp)
        ans = max(ans, tmp)
print(ans)

Submission status: Runtime Error

Solution code:
import math            
N = int(input())
A = list(map(int,input().split()))
if N % 2 == 0:
    ans = max(sum(A[::2]),sum(A[1::2]))
else:
    for i in range(N-N//2):
        num = sum(A[i::2])
        if num > ans:
            ans = num   
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np 

N = int(input())

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

m = N//2

# dp = np.zeros((N,m,2))
# dp = [[[0 for _ in range(2)] for _ in range(m+1)] for _ in range(N)]
dp = np.zeros((N,m+1,2))

dp[0,1,1] = a_list[0]
dp[0,:,0] = -10000000000000001


for i in range(1,N):
    dp[i,:,0] = np.max(dp[i-1,:,:],axis=1)
    j = min(i,m)
    if i==1:
        dp[i,1,1] = a_list[i]
    else:
        dp[i,1:1+j,1] = dp[i-1,:j,0] + a_list[i]

ans = np.max(dp[N-1,m,:])
print(int(ans))

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(x) for x in input().split()]

m = -10**9

if N % 2 == 0:
    a = sum(A)
    m = max(sum(A[0::2]), sum(A[1::2]))
else:
    for i in range(N):
        B = A.copy()
        del B[i]
        print(B[:i],B[i:])
        tmp1 = max(sum(B[0:i:2]),sum(B[1:i:2]))
        tmp2 = max(sum(B[i::2]),sum(B[i+1::2]))
        
        tmp = tmp1 + tmp2
        m = max(m,tmp)
        
print(m)

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) 
arr = [5, 5, 10, 100, 10, 5] 
print find_max_sum(arr)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import numpy as np

n = ni()
a = na()
x = n//2

dp = [[a[i]]*(x+1) for i in range(n)]

se = [2,3,4]

for i in range(n):
    for j in range(2,x+1):
        a = -100000000000
        for k in se:
            p = i-k
            if p >= 0:
                a = max(a,dp[p][j-1])
        dp[i][j] += a

print(dp[n-1][x])

Submission status: Runtime Error

Solution code:
import numpy as np 

N = int(input())

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

m = N//2

# dp = np.zeros((N,m,2))
# dp = [[[0 for _ in range(2)] for _ in range(m+1)] for _ in range(N)]
dp = np.zeros((N,m+1,2))

dp[0,1,1] = a_list[0]
dp[0,:,0] = -1000000000000000000001


for i in range(1,N):
    dp[i,:,0] = np.max(dp[i-1,:,:],axis=1)
    j = min(i,m)
    if i==1:
        dp[i,1,1] = a_list[i]
    else:
        dp[i,1:1+j,1] = dp[i-1,:j,0] + a_list[i]

ans = np.max(dp[N-1,m,:])
print(int(ans))

Submission status: Runtime Error

Solution code:
def solve(n,a):
    wa=0
    for i in range(n):
        if(i%2==0):
            wa+=a[i]
    kotae=wa
    for i in range(n//2):
        wa+=a[(n//2-i-1)*2+1]
        wa-=a[(n//2-i-1)*2]
        if(wa>kotae):
            kotae=wa
    return kotae

def dfs(n,a):
    if(n==3):
        return max(a)
    #kotae=solve(n-1,a[1:])+a[0]
    #kotae=max(kotae,solve(n-1,a[:n-1])+a[n-1])
    #kotae=max(kotae,dfs(n-2,a[1:n-1]))
    #print(kotae)
    kotae=dfs(n-2,a[2:])+a[0]
    kotae=max(kotae,dfs(n-2,a[:n-2])+a[n-1])
    temp=0
    for i in range(n//2):
        temp+=a[i*2+1]
    kotae=max(temp,kotae)
    return kotae

n=int(input())

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


if(n%2==0):
    print(solve(n,a))
else:
    print(dfs(n,a))

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)
    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] if d != 1 else -10
        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)
        cnt += 1
        i += 1
    print(sumv)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

selectnum=n//2


def maximum(number):
    n=len(number)
    now=0
    for i in range(0,len(number)-1,2):
        now+=number[i]
    if n%2==0:
        if n==2:
            return max(number[0],number[1])
        return max(maximum(number[:-2])+number[-1],now)
    else:
        if n==3:
            return max(number[0],number[1],number[2])
        return max(now,maximum(number[:-3])+number[-2],maximum(number[:-2])+number[-1])
        
    
    
    
print(maximum(a))