Problem:


Score : 600 points

Problem Statement

Given is an integer sequence A_1, ..., A_N of length N.

We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.

Find the maximum possible sum of the chosen elements.

Here \lfloor x \rfloor denotes the greatest integer not greater than x.

Constraints

2 \leq N \leq 2\times 10^5

|A_i|\leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the maximum possible sum of the chosen elements.

Sample Input 1

6
1 2 3 4 5 6

Sample Output 1

12

Choosing 2, 4, and 6 makes the sum 12, which is the maximum possible value.

Sample Input 2

5
-1000 -100 -10 0 10

Sample Output 2

0

Choosing -10 and 10 makes the sum 0, which is the maximum possible value.

Sample Input 3

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5000000000

Watch out for overflow.

Sample Input 4

27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49

Sample Output 4

295



Sample input:
6
1 2 3 4 5 6


Sample output:
12

Submission status: Wrong Answer

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

if n%2==0:
    #偶数なら、0から始まるか1から始まるかでは・・・？
    sum1=0
    sum2=0

    for i in range(n):
        if i%2==0:
            sum1+=a[i]
        else:
            sum2+=a[i]

    print(max(sum1,sum2))

else:
    if n//2==1:
        print(max(a))
        exit()
    

    sum1=0
    sum2=0

    #iは桁数、jはそれまでに余計に飛ばした数
    #dp[i][j]
    dp=[[-10**9]*3 for _ in range(n)]

    for i in range(n):
        if i<2:
            dp[i][0]=a[i]

        if i>=2:
            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]])
    #print(dp)
    print(max([dp[-1][2],dp[-1][1],dp[-1][0]-a[0],dp[-1][0]-a[-1]]))

Submission status: Wrong Answer

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

if n%2==0:
    #偶数なら、0から始まるか1から始まるかでは・・・？
    sum1=0
    sum2=0

    for i in range(n):
        if i%2==0:
            sum1+=a[i]
        else:
            sum2+=a[i]

    print(max(sum1,sum2))

else:
    sum1=0
    sum2=0

    #iは桁数、jはそれまでに余計に飛ばした数
    #dp[i][j]
    dp=[[-10**9]*3 for _ in range(n)]

    for i in range(n):
        if i<2:
            dp[i][0]=a[i]

        if i>=2:
            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]])
    #print(dp)
    print(max([dp[-1][2],dp[-1][1],dp[-1][0]-a[0],dp[-1][0]-a[-1]]))

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dp=defaultdict(int)

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

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
su0=0
su1=0
inf=10**16
if(n%2==0):
    for i in range(0,n,2):
      su0+=l[i]
      if(i+1<n):
        su1+=l[i+1]
    print(max(su1,su0))
else:
    pos=[0]*n
    pre=[0]*n
    pre[-1]=l[-1]
    pre[-2]=l[-2]
    pos[0]=l[0]
    pos[1]=l[1]
    for i in range(2,n):
        pos[i]=pos[i-2]+l[i]
    for i in range(n-3,-1,-1):
        pre[i]=pre[i+2]+l[i]
    #pos=pos
    #pre=pre
    
    mx=max(pre[1],pos[-3],pre[2])
    #print(pos)
    #print(pre)
    for i in range(0,n,2):
        a=0
        b=0
        if(i-1>=0):
            a=pos[i-1]
        
        if(i+1<n):
            mx=max(mx,a+pre[i+1])
        else:
            mx=max(mx,a)
        if(i+2<n):
            mx=max(mx,a+pre[i+2])
        if(i-2>=0):
            b=pos[i-2]
        if(i+1<n):
            mx=max(mx,b+pre[i+1])
        else:
            #print(b)
            mx=max(mx,b)
        if(i+2<n):
            mx=max(mx,b+pre[i+2])
        #print(a,b,i,mx)
    print(mx)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().split()))
su0=0
su1=0
inf=10**16
if(n%2==0):
    for i in range(0,n,2):
      su0+=l[i]
      if(i+1<n):
        su1+=l[i+1]
    print(max(su1,su0))
else:
    pos=[0]*n
    pre=[0]*n
    pre[-1]=l[-1]
    pre[-2]=l[-2]
    pos[0]=l[0]
    pos[1]=l[1]
    for i in range(2,n):
        pos[i]=pos[i-2]+l[i]
    for i in range(n-3,-1,-1):
        pre[i]=pre[i+2]+l[i]
    #pos=pos
    #pre=pre
    
    mx=pre[1]
    #print(pos)
    for i in range(0,n,2):
        a=-inf
        b=-inf
        if(i-1>=0):
            a=pos[i-1]
        if(i+1<n):
            mx=max(mx,a+pre[i+1])
        else:
            mx=max(mx,a)
        if(i+2<n):
            mx=max(mx,a+pre[i+2])
        if(i-2>=0):
            b=pos[i-2]
        if(i+1<n):
            mx=max(mx,b+pre[i+1])
        else:
            #print(b)
            mx=max(mx,b,a)
        if(i+2<n):
            mx=max(mx,b+pre[i+2])
        #print(a,b,i,mx)
    print(mx)

Submission status: Wrong Answer

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

if n%2==0:
    print(max(sum(a[0::2]),sum(a[1::2])))
    exit()
inf = 10**20
dp=[[[-inf,-inf],[-inf,-inf]] for _ in range(n)]
dp+=[[[0,0],[0,0]]]
# 桁数、選んだか、上限か上限 -1 か
for i in range(n):
    if i%2==0:
        #01010 or 10100
        dp[i][0][0]=max(dp[i-1][1][1],dp[i-1][0][1])
        #10101
        dp[i][1][1]=dp[i-1][0][1]+a[i]
        #10001
        dp[i][1][0]=dp[i-1][0][0]+a[i]
        #dp[i][0][1]
    else:
        #1010
        dp[i][0][1]=dp[i-1][1][1]
        #0101
        dp[i][1][1]=dp[i-1][0][0]+a[i]

        #0100 or 0010
        dp[i][0][0]=max(dp[i-1][1][0],dp[i-1][0][0])
        #0001
        dp[i][1][0]=dp[i-1][0][0]+a[i]
print(max(dp[-2][0]+dp[-2][1]))

Submission status: Wrong Answer

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

if n%2==0:
    print(max(sum(a[0::2]),sum(a[1::2])))
    exit()
inf = 10**10
dp=[[[-inf,-inf],[-inf,-inf]] for _ in range(n)]
dp+=[[[0,0],[0,0]]]
# 桁数、選んだか、上限か上限 -1 か
for i in range(n):
    if i%2==0:
        #01010 or 10100
        dp[i][0][0]=max(dp[i-1][1][1],dp[i-1][0][1])
        #10101
        dp[i][1][1]=dp[i-1][0][1]+a[i]
        #10001
        dp[i][1][0]=dp[i-1][0][0]+a[i]
        #dp[i][0][1]
    else:
        #1010
        dp[i][0][1]=dp[i-1][1][1]
        #0101
        dp[i][1][1]=dp[i-1][0][0]+a[i]

        #0100 or 0010
        dp[i][0][0]=max(dp[i-1][1][0],dp[i-1][0][0])
        #0001
        dp[i][1][0]=dp[i-1][0][0]+a[i]
print(max(dp[-2][0]+dp[-2][1]))

Submission status: Wrong Answer

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

if N%2==0:
  a1 = sum(A[::2])
  a2 = sum(A[1::2])
  print(max(a1,a2))
else:
  a1 = sum(A[:-2:2])
  a2 = sum(A[1:-1:2])
  a3 = sum(A[2::2])
  print(max(a1,a2,a3))

Submission status: Wrong Answer

Solution code:
N = int(input())
*l, = map(int, input().split())

a = []

for i in range(N):
    a.append((l[i], i))
a.sort(reverse=True)

used = set()
ans = 0
cnt = 0
for i, j in a:
    if not j in used:
        used |= {j-1, j, j+1}
        ans += i
        cnt += 1
        if cnt == N//2:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
    print(max(sum(A[::2]), sum(A[1::2])))
else:
    dp = [[-float("inf")]*3 for i in range(n)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    for i in range(2, n):
        dp[i][0] = dp[i-2][0] + A[i]
        dp[i][1] = max(dp[i-2][1], dp[i-3][0] if i>=3 else float("-inf")) + A[i]
        dp[i][2] = max(dp[i-2][2], dp[i-3][1] if i>=3 else float("-inf"), dp[i-4][0] if i>=4 else float("-inf")) + A[i]
        if i == 2:
            dp[i][2] = A[2]

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

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float("inf")
mod = 10 ** 9 + 7

N = INT()
A = LIST()

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

print(dp[N][0] if N%2 == 0 else dp[N][1])

Submission status: Wrong Answer

Solution code:
def f(k):
    if k==1:
        return A[-1]
    return max(sum(A[1::2]),sum(A[2::2]),A[-k]+f(k-2))

N = int(input())
A = list(map(int,input().split()))
if N%2==0:
    a = max(sum(A[::2]),sum(A[1::2]))
else:
    a = f(N)
print(a)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
INF = 10**18

dp0 = 0
dp1 = -INF
dp2 = -INF

for i, a in enumerate(A):
    if i % 2 == 0:
        dp1 = max(dp1, dp0)
        dp0 += a
        dp2 += a
    else:
        dp2 = max(dp2, dp1)
        dp1 += a

if N % 2 == 1:
    print(dp2)
else:
    print(max(dp0, dp1))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
INF = 10**18

dp0 = 0
dp1 = -INF
dp2 = -INF

for i, a in enumerate(A):
    if i % 2 == 0:
        dp1 = max(dp1, dp0)
        dp0 += a
        dp2 += a
    else:
        dp2 = max(dp2, dp1)
        dp1 += a

if N % 2 == 1:
    print(dp2)
else:
    print(max(dp1, dp2))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N % 2 == 0:
        ans = max(sum(A[::2]), sum(A[1::2]))
        print(ans)
        return
    dp = [defaultdict(int) for _ in range(N)]
    dp[0][1] = A[0]
    dp[1][1] = max(A[0:2])
    for i in range(2, N):
        dp[i][i//2] = max(dp[i-2][i//2-1] + A[i], dp[i-1][i//2])
        dp[i][i//2+1] = max(dp[i-2][i//2] + A[i], dp[i-1][i//2+1])
    print(dp[N-1][N//2])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [defaultdict(int) for _ in range(N)]
    dp[0][1] = A[0]
    dp[1][1] = max(A[0:2])
    for i in range(2, N):
        dp[i][i//2] = max(dp[i-2][i//2-1] + A[i], dp[i-1][i//2])
        dp[i][i//2+1] = max(dp[i-2][i//2] + A[i], dp[i-1][i//2+1])
    print(dp[N-1][N//2])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    dp = [defaultdict(int) for _ in range(N)]
    dp[0][1] = A[0]
    dp[1][1] = max(A[0:2])
    for i in range(2, N):
        dp[i][i//2] = max(dp[i-2][i//2-1] + A[i], dp[i-1][i//2])
        dp[i][i//2+1] = dp[i-2][i//2] + A[i]
    print(dp[N-1][N//2])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

from collections import defaultdict
dp = [defaultdict(int) for _ in range(n)]

dp[0][0] = 0
dp[0][1] = a[0]

import math
for i in range(1, n):
    k1 = int(math.ceil((i + 1) / 2))
    k2 = k1 - 1

    dp[i][k1] = max(dp[i-1][k1], dp[i-2][k1-1] + a[i])
    dp[i][k2] = max(dp[i-1][k2], dp[i-2][k2-1] + a[i])

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

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
    ans1 = 0
    ans2 = 0
    for i in range(n):
        if i % 2 == 0:
            ans1 += A[i]
        else:
            ans2 += A[i]
    print(max(ans1, ans2))
    exit()
if n == 1:
    print(A[i])
    exit()

dp1 = [[-(10 ** 10)] * (3) for _ in range(n + 3)]
dp1[0][0] = 0
for i in range(n + 2):
    for j in range(3):
        # 　配るDP
        # 加えないパターン
        ni = i + 1
        nj = j + 1
        if ni <= n + 2 and nj <= 2:
            dp1[ni][nj] = max(dp1[ni][nj], dp1[i][j])
        # 　加えるパターン
        ni = i + 2
        nj = j
        if ni <= n + 1 and nj <= 2:
            dp1[ni][nj] = max(dp1[ni][nj], dp1[i][j] + A[i])
ans1 = dp1[n + 1][2]
dp2 = [[-(10 ** 10)] * (2) for _ in range(n + 3)]
dp2[1][0] = 0
for i in range(n + 2):
    for j in range(3):
        # 　配るDP
        # 加えないパターン
        ni = i + 1
        nj = j + 1
        if ni <= n + 2 and nj <= 1:
            dp2[ni][nj] = max(dp2[ni][nj], dp2[i][j])
        # 　加えるパターン
        ni = i + 2
        nj = j
        if ni <= n + 1 and nj <= 1:
            dp2[ni][nj] = max(dp2[ni][nj], dp2[i][j] + A[i])
ans2 = dp2[n-1][1]


ans3 = 0
for i in range(2, n):
    if i % 2 == 0:
        ans3 += A[i]


print(max(ans1, ans2, ans3))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
    ans1 = 0
    ans2 = 0
    for i in range(n):
        if i % 2 == 0:
            ans1 += A[i]
        else:
            ans2 += A[i]
    print(max(ans1, ans2))
    exit()
if n == 1:
    print(A[i])
    exit()
num = n // 2
dp1 = [[-(10 ** 10)] * (3) for _ in range(n + 3)]
dp1[0][0] = 0
for i in range(n + 2):
    for j in range(3):
        # 　配るDP
        # 加えないパターン
        ni = i + 1
        nj = j + 1
        if ni <= n + 2 and nj <= 2:
            dp1[ni][nj] = max(dp1[ni][nj], dp1[i][j])
        # 　加えるパターン
        ni = i + 2
        nj = j
        if ni <= n + 1 and nj <= 2:
            dp1[ni][nj] = max(dp1[ni][nj], dp1[i][j] + A[i])
ans1 = dp1[n + 1][2]
dp2 = [[-(10 ** 10)] * (2) for _ in range(n + 3)]
dp2[1][0] = 0
for i in range(n + 2):
    for j in range(3):
        # 　配るDP
        # 加えないパターン
        ni = i + 1
        nj = j + 1
        if ni <= n + 2 and nj <= 1:
            dp2[ni][nj] = max(dp2[ni][nj], dp2[i][j])
        # 　加えるパターン
        ni = i + 2
        nj = j
        if ni <= n + 1 and nj <= 1:
            dp2[ni][nj] = max(dp2[ni][nj], dp2[i][j] + A[i])
ans2 = dp2[n][1]


ans3 = 0
for i in range(2, n):
    if i % 2 == 0:
        ans3 += A[i]


print(max(ans1, ans2, ans3))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
    ans1 = 0
    ans2 = 0
    for i in range(n):
        if i % 2 == 0:
            ans1 += A[i]
        else:
            ans2 += A[i]
    print(max(ans1, ans2))
    exit()

num = n // 2
dp = [[-(10 ** 10)] * (3) for _ in range(n + 3)]
dp[0][0] = 0
for i in range(n + 2):
    for j in range(3):
        # 　配るDP
        # 加えないパターン
        ni = i + 1
        nj = j + 1
        if ni <= n + 2 and nj <= 2:
            dp[ni][nj] = max(dp[ni][nj], dp[i][j])
        # 　加えるパターン
        ni = i + 2
        nj = j
        if ni <= n + 1 and nj <= 2:
            dp[ni][nj] = max(dp[ni][nj], dp[i][j] + A[i])

ans = max(dp[n + 1][2], dp[n + 1][1])

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
    ans1 = 0
    ans2 = 0
    for i in range(n):
        if i % 2 == 0:
            ans1 += A[i]
        else:
            ans2 += A[i]
    print(max(ans1, ans2))
    exit()

num = n // 2
dp = [[-(10 ** 10)] * (3) for _ in range(n + 3)]
dp[0][0] = 0
for i in range(n + 2):
    for j in range(3):
        # 　配るDP
        # 加えないパターン
        ni = i + 1
        nj = j + 1
        if ni <= n + 2 and nj <= 2:
            dp[ni][nj] = max(dp[ni][nj], dp[i][j])
        # 　加えるパターン
        ni = i + 2
        nj = j
        if ni <= n + 1 and nj <= 2:
            dp[ni][nj] = max(dp[ni][nj], dp[i][j] + A[i])

ans = max(dp[n + 1][2], dp[n + 2][2])

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
    ans1 = 0
    ans2 = 0
    for i in range(n):
        if i % 2 == 0:
            ans1 += A[i]
        else:
            ans2 += A[i]
    print(max(ans1, ans2))
    exit()

num = n // 2
dp = [[-(10 ** 10)] * (3) for _ in range(n + 3)]
dp[0][0] = 0
for i in range(n + 1):
    for j in range(3):
        # 　配るDP
        # 加えないパターン
        ni = i + 1
        nj = j + 1
        if ni <= n + 1 and nj <= 2:
            dp[ni][nj] = max(dp[ni][nj], dp[i][j])
        # 　加えるパターン
        ni = i + 2
        nj = j
        if ni <= n + 1 and nj <= 2:
            dp[ni][nj] = max(dp[ni][nj], dp[i][j] + A[i])

ans = dp[n + 1][2]

print(ans)

Submission status: Wrong Answer

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

INF = 10 ** 18

if N % 2:
    dp = [[-INF for j in range(N)] for i in range(3)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for j in range(N):
        for i in range(3):
            if dp[i][j] == -INF:
                continue
            for k in range(3):
                if i + k < 3 and j + k + 2 < N:
                    dp[i + k][j + k + 2] = max(dp[i + k][j + k + 2], dp[i][j] + A[j + k + 2])
    print(max(max(dp[0][-3:]), max(dp[1][-2:]), max(dp[2][-1:])))
    
else:
    dp = [[-INF for j in range(N)] for i in range(2)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    for j in range(N):
        for i in range(2):
            if dp[i][j] == -INF:
                continue
            for k in range(2):
                if i + k < 2 and j + k + 2 < N:
                    dp[i + k][j + k + 2] = max(dp[i + k][j + k + 2], dp[i][j] + A[j + k + 2])
    print(max(max(dp[0][-2:]), max(dp[1][-1:])))

Submission status: Wrong Answer

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

INF = 10 ** 18

if N % 2:
    dp = [[-INF for j in range(N)] for i in range(3)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for j in range(N):
        for i in range(3):
            for k in range(3):
                if i + k < 3 and j + k + 2 < N:
                    dp[i + k][j + k + 2] = max(dp[i + k][j + k + 2], dp[i][j] + A[j + k + 2])
    print(max(max(dp[0][-3:]), max(dp[1][-2:]), dp[2][-1]))
else:
    dp = [[-INF for j in range(N)] for i in range(2)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    for j in range(N):
        for i in range(2):
            for k in range(2):
                if i + k < 2 and j + k + 2 < N:
                    dp[i + k][j + k + 2] = max(dp[i + k][j + k + 2], dp[i][j] + A[j + k + 2])
    print(max(max(dp[0][-2:]), dp[1][-1]))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N,*A = map(int, open(0).read().split())
dic1 = defaultdict(lambda :-10**20)
dic2 = defaultdict(lambda :-10**20)
for i in range(-1,N):
  dic1[(i,0)] = 0
  dic2[(i,0)] = 0
for i in range(N):
  for j in range(max(1,N//2-(N-i+1)//2), i//2+2):
    dic1[(i,j)] = max(dic1[(i,j)],dic2[(i-1,j-1)]+A[i])
  for j in range(N//2-(N-i)//2,(i-1)//2+2):
    dic2[(i,j)] = max(dic2[(i-1,j)],dic1[(i-1,j)])
print(dic1[(N-1,N//2)])

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())
A_list=list(map(int,input().split()))
if n%2==0:
    ans=max(sum(A_list[::2]),sum(A_list[1::2])) 
else:
    ans_list=list()
    for i in range(n):
        arr=[1,0]*int((n-1)/2)
        arr.insert(i,0)
        ans1=np.sum(np.array(A_list)*np.array(arr))
        ans_list.append(ans1)
        
        arr=[0,1]*int((n-1)/2)
        arr.insert(i,0)
        ans1=np.sum(np.array(A_list)*np.array(arr))
        ans_list.append(ans1)
    ans=max(ans_list)
    
print(ans)

Submission status: Wrong Answer

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

DP = [0,0,0]
m = N//2*2
if N%2 == 0:
    for i in range(0,m,2):
        DP[0] += A[i]
        DP[1] += A[i+1]
        DP[1] += max(DP[0],DP[1])

    print(DP[1])

else:
    for i in range(0,m,2):
        DP[0] += A[i]
        DP[1] += A[i+1]
        DP[2] += A[i+2]

        DP[1] = max(DP[0],DP[1])
        DP[2] = max(DP[1],DP[2])

    print(DP[2])

Submission status: Wrong Answer

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

if N%2 == 0:
    sum1 = sum(A[x*2] for x in range(N//2))
    sum2 = sum(A)-sum1
    print(max(sum1,sum2))
    exit()

DP = [0,0,0]
m = N//2*2
for i in range(0,m,2):
    DP[0] += A[i]
    DP[1] += A[i+1]
    DP[2] += A[i+2]

    DP[1] = max(DP[0],DP[1])
    DP[2] = max(DP[1],DP[2])

print(DP[2])

Submission status: Wrong Answer

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

if N%2 == 0:
    sum1 = sum(A[x*2] for x in range(N//2))
    sum2 = sum(A)-sum1
    print(max(sum1,sum2))
    exit()

DP = [0,0,0]
m = N//2*2
for i in range(0,m,2):
    DP[0] += A[i]
    DP[1] += A[i+1]
    DP[2] += A[i+2]

    DP[1] = max(DP[0],DP[1])
    DP[2] = max(DP[1],DP[2])

print(max(DP))

Submission status: Wrong Answer

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

if N%2 == 0:
    sum1 = sum(A[x*2] for x in range(N//2))
    sum2 = sum(A)-sum1
    print(max(sum1,sum2))
    exit()

B = [x for x in A]
C = [x for x in A]

for i in range(2,N):
    B[i] = B[i]+B[i-2]
    C[N-1-i] = C[N-1-i] + C[N-1-i+2]

D = [0]*(N-3)
for i in range(N-3):
    D[i] = B[i]+C[i+3]

E = [0]*(N-4)
for i in range(N-4):
    E[i] = B[i]+C[i+4]

F = [0]*((N-5)//2)
for i in range(len(F)):
    F[i] = B[i*2] + A[i*2+3] + C[i*2+6]
F
ls = B[:-1]+C[1:]+D+E+F
print(max(ls))

Submission status: Wrong Answer

Solution code:
N, *A = map(int, open(0).read().split())

v1 = 0
v2 = 0
v3 = 0
m = N // 2 *2 
if N % 2 == 0:
  for i in range(0, m, 2):
    v1 += A[i]
    v2 += A[i+1]
    v2 = max(v1,v2)
else:
  for i in range(0, m, 2):
    v1 += A[i]
    v2 += A[i+1]
    v3 += A[i+2]
    v2 = max(v1,v2)
    v3 = max(v2,v3)
#
print(max(v1,v2,v3))

Submission status: Wrong Answer

Solution code:
n=int(input())
A_list=list(map(int,input().split()))
if n%2==0:
    ans=max(sum(A_list[::2]),sum(A_list[1::2])) 
else:
    ans_list=list()
    for i in range(n):
        arr=[1,0]*int((n-1)/2)
        arr.insert(i,0)
        ans1=0
        for j in range(n):
            ans1+=A_list[j]*arr[j]
        ans_list.append(ans1)
        
        arr=[0,1]*int((n-1)/2)
        arr.insert(i,0)
        ans1=0
        for j in range(n):
            ans1+=A_list[j]*arr[j]
        ans_list.append(ans1)
    ans=max(ans_list)
    
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect


class Solver:
    def __init__(self, n, a_s):
        self.n = n
        self.a_s = [0] + a_s
        self.dp = self.make_empty_dp() # dp[consider till i][selected k][last 0/1] = max value

    def make_empty_dp(self):
        dp = [None] * (self.n + 1)
        for i, _ in enumerate(dp):
            dp[i] = [None] * 2 # ceil((i - 1) / 2) ~ ceil((i + 1) / 2)
            for k, _ in enumerate(dp[i]):
                dp[i][k] = [0, 0]
        return dp

    def run(self):
        for i, a in enumerate(self.a_s):
            if i % 2 == 0:
                self.take_even(i, a)
            else:
                self.take_odd(i, a)
        #print('self.dp') # debug
        #print(self.dp) # debug
        return self.get_ans()

    def take_even(self, i, a):
        #print('a') # debug
        #print(a) # debug
        self.dp[i][0][0] = max(self.dp[i - 1][0][0], self.dp[i - 1][0][1])
        self.dp[i][1][0] = self.dp[i - 1][1][1]
        self.dp[i][1][1] = self.dp[i - 1][0][0] + a

    def take_odd(self, i, a):
        #print('a') # debug
        #print(a) # debug
        self.dp[i][0][0] = max(self.dp[i - 1][1][0], self.dp[i - 1][1][1])
        self.dp[i][0][1] = self.dp[i - 1][0][0] + a
        self.dp[i][1][1] = self.dp[i - 1][1][0] + a

    def get_ans(self):
        last = self.dp[self.n]
        if self.n % 2 == 0:
            return max(last[0][0], last[1][0], last[1][1])
        else:
            return max(last[0][0], last[0][1], last[1][1])

if __name__ == '__main__':
    n = int(input())
    a_s = list(map(int, input().split()))
    ans = Solver(n, a_s).run()
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
m0 = 0
m1 = 0
m2 = 0

if n%2 == 0:
    for i,ai in enumerate(a):
        if i%2 == 0:
            m0 += ai
        else:
            m1 = max(m0,m1+ai)
    print(max(m0,m1))
else:
    for i,ai in enumerate(a):
        if i%2 == 0:
            m2 = max(m2+ai,m1,m0)
            if i < n-1:
                m0 += ai
        else:
            m1 = max(m0,m1+ai)
    print(max(m0,m1,m2))

Submission status: Wrong Answer

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

d = [lst[i] for i in range(0,n,2)]
e = [lst[i] for i in range(1,n,2)]

if len(e) == len(d):
    print(max(sum(d),sum(e)))
    
else:
    print(max(sum(e),sum(sorted(d)[1:])))

Submission status: Wrong Answer

Solution code:
n = int(input())

if n%2==0:
    tc = n//2
else:
    tc = n//2+1
d = [1,0]*tc   
lst = list(map(int, input().split()))
num = lst.index(max(lst))
f = d[num]
new = list(zip(lst,d))
new2 = [(i,j) for (i,j) in new if j == f]

final = []

for i,j in new2:
    final.append(i)


if n%2==0:
    print(sum(final))
else:
    print(sum(final[1:]))

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
#n=1000-1
#a=list(range(n))
import numpy as np
dp=np.zeros((3,n+1),np.int64)
dp[1,1]=a[0]
for i in range(2,n+1):
    l,r=i//2-1,(i+1)//2+1
    if i%3==2:
      now,pre,prepre=2,1,0
    elif i%3==0:
      now,pre,prepre=0,2,1
    elif i%3==1:
      now,pre,prepre=1,0,2
    if l==0:
        dp[now,l]=np.maximum(dp[pre,l],a[i-1])
        dp[now,l+1:r]=np.maximum(dp[pre,l+1:r],dp[prepre,l:r-1]+a[i-1])
    else:
        dp[now,l:r]=np.maximum(dp[pre,l:r],dp[prepre,l-1:r-1]+a[i-1])
print(dp[now,n//2])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
#n=1000-1
#a=list(range(n))
import numpy as np
dp=np.zeros((3,n+1),np.int64)
dp[1,1]=a[0]
for i in range(2,n+1):
    #l,r=max(1,n//2-(n-i+1)//2),(i+1)//2+1
    l,r=max(1,i//2-1),(i+1)//2+1
    if i%3==2:
      now,pre,prepre=2,1,0
    elif i%3==0:
      now,pre,prepre=0,2,1
    elif i%3==1:
      now,pre,prepre=1,0,2
    dp[now,l:r]=np.maximum(dp[pre,l:r],dp[prepre,l-1:r-1]+a[i-1])
print(dp[now,n//2])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
#n=1000-1
#a=list(range(n))
import numpy as np
dp=np.zeros((3,n+1),np.int64)
dp[1,1]=a[0]
for i in range(2,n+1):
    l,r=max(1,n//2-(n-i+1)//2),(i+1)//2+1
    if i%3==2:
      now,pre,prepre=2,1,0
    elif i%3==0:
      now,pre,prepre=0,2,1
    elif i%3==1:
      now,pre,prepre=1,0,2
    dp[now,l:r]=np.maximum(dp[pre,l:r],dp[prepre,l-1:r-1]+a[i-1])
print(dp[now,n//2])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
#n=1000-1
#a=list(range(n))
import numpy as np
dp=np.zeros((3,n+1),np.int64)
dp[1,1]=a[0]
for i in range(2,n+1):
    l,r=max(1,n//2-(n-i+1)//2),i//2+2
    if i%3==2:
      now,pre,prepre=2,1,0
    elif i%3==0:
      now,pre,prepre=0,2,1
    elif i%3==1:
      now,pre,prepre=1,0,2
    dp[now,l:r]=np.maximum(dp[pre,l:r],dp[prepre,l-1:r-1]+a[i-1])
print(dp[now,n//2])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
#n=100001
#a=list(range(n))
import numpy as np
dp=np.zeros((3,n+1),np.int64)
dp[:,0]=0
dp[1,1]=a[0]
for i in range(2,n+1):
    l,r=max(1,n//2-(n-i+1)//2-1),min(n,i//2+2)
    if i%3==2:
      now,pre,prepre=2,1,0
    elif i%3==0:
      now,pre,prepre=0,2,1
    elif i%3==1:
      now,pre,prepre=1,0,2
    dp[now,l:r]=np.maximum(dp[pre,l:r],dp[prepre,l-1:r-1]+a[i-1])
print(dp[now,n//2])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
#n=100001
#a=list(range(n))
import numpy as np
dp=np.zeros((3,n+1),np.int64)
dp[:,0]=0
dp[1,1]=a[0]
for i in range(2,n+1):
    l,r=max(1,n//2-(n-i+1)//2),min(n,i//2+1)
    if i%3==2:
      now,pre,prepre=2,1,0
    elif i%3==0:
      now,pre,prepre=0,2,1
    elif i%3==1:
      now,pre,prepre=1,0,2
    dp[now,l:r]=np.maximum(dp[pre,l:r],dp[prepre,l-1:r-1]+a[i-1])
print(dp[now,n//2])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
import math
dp=[[-math.inf]*(n+1) for _ in range(n+1)]
dp[0][0]=0
dp[1][0]=0
dp[1][1]=a[0]
for i in range(2,n+1):
    for j in range(n//2-(n-i+1)//2,i//2+1):
        dp[i][j]=max(dp[i-1][j],dp[i-2][j-1]+a[i-1])
        print(i,j)
print(dp[n][n//2])

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
if n%2==0:
    ev,od=0,0
    for i in range(n):
        if i%2==0:
            ev+=a[i]
        else:
            od+=a[i]
    print(max(od,ev))
    exit(0)

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

Submission status: Wrong Answer

Solution code:
import collections, sys
sys.setrecursionlimit(100005)
N = int(input())
A = [int(_) for _ in input().split()]
INF = float('inf')
memo = collections.defaultdict(lambda: INF)


def c(start, res):
    if memo[start, res] != INF:
        return memo[start, res]
    elif start >= N:
        memo[start, res] = -INF
    elif 2 * res - 1 > N - start:
        memo[start, res] = -INF
    elif start == N - 1:
        memo[start, res] = A[start]
    elif res:
        memo[start, res] = max(A[start] + c(start + 2, res - 1),
                               c(start + 1, res), c(start + 2, res))
    else:
        memo[start, res] = 0
    return memo[start, res]


print(c(0, N // 2))