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:
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 2 * res - 1 > N - start:
        memo[start, res] = -INF
    elif start >= N:
        memo[start, res] = -INF
    elif res > 1:
        memo[start, res] = max(A[start] + c(start + 2, res - 1),
                               c(start + 1, res), c(start + 2, res))
    else:
        memo[start, res] = A[start]
    return memo[start, res]


print(c(0, 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 res > 1:
        memo[start, res] = max(A[start] + c(start + 2, res - 1),
                               c(start + 1, res), c(start + 2, res))
    else:
        memo[start, res] = A[start]
    return memo[start, res]


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

Submission status: Wrong Answer

Solution code:
#基本1つ飛ばしだが、パスも使える。
#奇数ならパス2回、偶数ならパス1回。
N = int(input())
A = [int(hoge) for hoge in input().split()]
DP = [[0]*3 for n in range(N)] #DP[n][y] = n桁目までみて、パスをy回使ったときの最大値

DP[0][0] = A[0]


for n in range(N):#n桁目までみる。
    #「選ぶ」か「パスを使う」かの2択。
    DP[n][0] = DP[n-2][0] + A[n]
    DP[n][1] = max((DP[n-2][1]+A[n],DP[n-1][0]))
    DP[n][2] = max((DP[n-2][2]+A[n],DP[n-1][1]))
if N%2:
    print(DP[n][2])
else:
    print(DP[n][1])

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
m_INF = -10 ** 19
dp = [[m_INF] * N for _ in range(N+2)]
dp[0] = [0] * N
dp[1] = [0] * N
# dp[i][j] := i番目までの数列のうちj個選んだ場合の最大値
for i in range(N):
    if i//2-1 >= 1:
        dp[i+2][i//2-1] = max(dp[i-1+2][i//2-1], dp[i-2+2][i//2-2] + A[i])
    if i//2 >= 1:
        dp[i+2][i//2] = max(dp[i-1+2][i//2], dp[i-2+2][i//2-1] + A[i])
    dp[i+2][i//2+1] = max(dp[i-1+2][i//2+1], dp[i-2+2][i//2] + A[i])

#print(dp)
print(dp[-1][math.floor(N/2)])

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
m_INF = -10 ** 19
dp = [[m_INF] * N for _ in range(N)]
for i in range(N):
    for j in range(1,N):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i])
        elif i//2+1 >= j:
            dp[i][j] = max(dp[i][j], dp[i-2][j-1] + A[i])

#print(dp)
print(dp[-1][math.floor(N/2)])

Submission status: Wrong Answer

Solution code:
def find(A):
    N = len(A)
    ans = [0]*N
    odd_sum = [0]*N
    even_sum = [0]*N
    for i in range(N):
        if i%2 == 0:
            if i-2>=0:
                even_sum[i] = even_sum[i-2] + A[i]
            else:
                even_sum[i] = A[i]
        else:
            if i-2>=0:
                odd_sum[i] = odd_sum[i-2] + A[i]
            else:
                odd_sum[i] = A[i]
    if N%2==0:
        return max(odd_sum[-1],even_sum[-2])
#     print(odd_sum)
#     print(even_sum)
    for i in range(1,N):
        length = i+1
        if length%2==0:
            ans[i] = max(A[i] + ans[i-2],odd_sum[i-1]+even_sum[i-1] )
        else:
            ans[i] = max(A[i] + ans[i-2],ans[i-1])
            
    #print(ans)
    return ans[-1]
    
input()   
print(find(list(map(int,input().strip().split()))))

Submission status: Wrong Answer

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

m = N//2

max_v = min(A)
x = 0
y = 0
x_ls =[]
y_ls = []
for i in range(m):
  x += A[i*2]
  x_ls.append(A[i*2])
  y += A[i*2+1]
  y_ls.append(A[i*2+1])
max_v = max(x,y)

if len(A)%2==1:
  z = x-A[0]+A[N-1]
  x_ls.append(A[-1])
  for i in range(m):
    z = max(z,x-A[m*2]+A[N-1])
  for i in range(m):
    for j in range(i+1,m):
      ls = x_ls[:i] + y_ls[i:j] + x_ls[j+1:]
      z = max(z,sum(ls))
  max_v = max(max_v,z)

print(max_v)

Submission status: Wrong Answer

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


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


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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
INF = 1001001001001001
c = n//2
dp = [[-INF]*3 for _ in range(c+1)]
dp[0][0] = 0
for i in range(c+1):
    for j in range(3):
        for k in range(3):
            if i+1<=c and j+k<3 and 2*i+j+k<n:
                dp[i+1][j+k] = max(dp[i+1][j+k], dp[i][j]+a[2*i+j+k])

ans = 0

for i in range(3):
    ans = max(ans,dp[c][i])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = list(map(int, readline().split())) + [-float('inf')] * 2
dp = [[-float('inf')] * 3 for _ in range(n + 4)]
for i in range(3):
    dp[0][i] = 0
for i, (bf, aa, af) in enumerate(zip(a, a[1:], a[2:])):
    dp[i + 4][2] = max(dp[i + 4][2], dp[i][0] + af)
    for j in range(1, 3):
        dp[i + 3][j] = max(dp[i + 3][j], dp[i][j - 1] + aa)
    for j in range(3):
        dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + bf)
if n % 2 == 0:
    print(max(dp[n + 1][1], dp[n][0]))
else:
    print(max(dp[n + 1][2], dp[n][1], dp[n - 1][0]))

Submission status: Wrong Answer

Solution code:
INF = 10**9

def solve(n, a):
    dp = [{j: [-INF, -INF] for j in range(i//2-1, (i+1)//2 + 1)} for i in range(n+1)]
    dp[0][0][False] = 0
    for i in range(n):
        for j in dp[i].keys():
            if (j+1) in dp[i+1]:
                dp[i+1][j+1][True] = max(dp[i+1][j+1][True], dp[i][j][False] + a[i])
            if j in dp[i+1]:
                dp[i+1][j][False] = max(dp[i+1][j][False], dp[i][j][False])
                dp[i+1][j][False] = max(dp[i+1][j][False], dp[i][j][True])
    return max(dp[-1][n//2])

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

Submission status: Wrong Answer

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

b = a[::2]
c = a[1::2]

s = [0]
j = 0
for i in b:
    s.append(i+s[j])
    j+=1
t = [0]
j = 0
for i in c:
    t.append(i+t[j])
    j+=1

q=[]
if n%2 ==0:
    q.append(max(sum(b),sum(c)))
else:
    for j in range(int(n)):
        if j%2 == 0:
            i = int(j/2)
            q.append(max(s[i]+s[int((n+1)/2)]-s[i+1],
                        s[i]+t[int((n-1)/2)]-t[i],
                        t[i]+s[int((n+1)/2)]-s[i+1],
                        t[i]+t[int((n-1)/2)]-t[i]))

        if j%2 == 1:
            i = int((j-1)/2)
            q.append(max(s[i+1]+t[int((n-1)/2)]-t[i+1],
                         t[i]+s[int((n+1)/2)]-s[i+1]))
            
print(max(q))

Submission status: Wrong Answer

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

b = a[::2]
c = a[1::2]

s = [0]
j = 0
for i in b:
    s.append(i+s[j])
    j+=1
t = [0]
j = 0
for i in c:
    t.append(i+t[j])
    j+=1

q=[]
if n%2 ==0:
    q.append(max(sum(b),sum(c)))
else:
    for j in range(int(n)):
        if j%2 == 0:
            i = int(j/2)
            q.append(max(s[i]+s[int((n+1)/2)]-s[i+1],
                        s[i]+t[int((n-1)/2)]-t[i],
                        t[i]+s[int((n+1)/2)]-s[i+1],
                        t[i]+t[int((n-1)/2)]-t[i]))

        if j%2 == 1:
            i = int((j-1)/2)
            q.append(max(s[i+1]+t[int((n-1)/2)]-t[i+1],t[i]+s[int((n+1)/2)]-s[i+1]))
            
print(max(q))

Submission status: Wrong Answer

Solution code:
INF = 10**9

def solve(n, a): 
    dp = [{} for i in range(n)]
    dp[0][0] = 0 
    dp[0][1] = a[0]
    dp[1][1] = a[1]
    for i in range(2, n): 
        s = n // 2 - (n-i+1) // 2
        t = (i+1) // 2
        for j in range(s, t+1):
            dp[i][j] = -INF
            if j in dp[i-1]:
                dp[i][j] = max([
                    dp[i][j], 
                    dp[i-1][j]
                ])  
            if (j-1) in dp[i-2]:
                dp[i][j] = max([
                    dp[i][j],
                    (dp[i-2][j-1] + a[i])
                ])  
            if (j-1) in dp[i-3]:
                dp[i][j] = max([
                    dp[i][j],
                    (dp[i-3][j-1] + a[i])
                ])  
    return dp[-1][n//2]

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

Submission status: Wrong Answer

Solution code:
#%%
N = int(input())
A = list(map(int,input().split()))
import sys

if N&1 == 0:
    ans = max(sum(A[::2]),sum(A[1::2]))
    print(ans)
    sys.exit()

INF = 10**20
K = 2
dp = [[[-INF]*(K+1) for _ in range(2)] for _ in range(N+1)]
dp[1][1][K] = A[0]
ans = -INF


for i in range(1, N):
    for k in range(K+1):
        if k<K:
            dp[i+1][0][k] = max(dp[i][1][k], dp[i][0][k+1])
        else:
            dp[i+1][0][k] = dp[i][1][k]
        
        dp[i+1][1][k] = dp[i][0][k] + A[i]

ans = max(ans, dp[N][1][0], dp[N][0][1])

A.reverse()
K = 1
dp = [[[-INF]*(K+1) for _ in range(2)] for _ in range(N+1)]
dp[1][1][K] = A[0]

for i in range(1, N):
    for k in range(K+1):
        if k<K:
            dp[i+1][0][k] = max(dp[i][1][k], dp[i][0][k+1])
        else:
            dp[i+1][0][k] = dp[i][1][k]
        
        dp[i+1][1][k] = dp[i][0][k] + A[i]
ans = max(ans, dp[N][0][0])

ans = max(ans, sum(A[1::2]))
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
m=n//2
if n%2==0:
    dp=[[0]*2 for _ in range(m)]
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    for i in range(1,m):
        for j in range(2*i,2*(i+1)):
            for k in range(2*(i-1),2*i):
                if j-k>1:
                    dp[i][j%2]=max(dp[i][j%2],dp[i-1][k%2]+a[j])
else:
    dp=[[0]*3 for _ in range(m)]
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    dp[0][2]=a[2]
    for i in range(1,m):
        for j in range(2*i,2*(i+1)+1):
            for k in range(2*(i-1),2*i+1):
                if j-k>1:
                    dp[i][j-2*i]=max(dp[i][j-2*i],dp[i-1][k-2*(i-1)]+a[j])
print(max(dp[-1]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
s0=0
s1=0
sl0=[0]
sl1=[0]
# sl0[i]:
for i in range(n):
      if i%2==0:
            s0+=a[i]
            sl0.append(s0)
      else:
            s1+=a[i]
            sl1.append(s1)
if n%2==0:
      print(max(sl1[-1],sl0[-1]))
      exit()
# あるaiを除いた時の最大を求め、そのうちの最大を答えとする。
# まずi=0,n-1を取り除く
ans=max(sl1[-1],sl0[-2],sl0[-1]-sl0[1])
# i=1を取り除くと左はi=0だけ右はi=2から
for i in range(1,n-1):
      #l=max(sum([a[2*j] for j in range(n//2+1) if 2*j<i]),sum([a[2*j+1] for j in range(n//2) if 2*j+1<i]))
      #r=max(sum([a[2*j] for j in range(n//2+1) if i<2*j]),sum([a[2*j+1] for j in range(n//2) if i<2*j+1]))
      l=a[:i]# i個
      r=a[i+1:]# n-i-1個
      if i%2==0:
            l=max(sum([l[j] for j in range(len(l)) if j%2==0]),sum([l[j] for j in range(len(l)) if j%2==1]))
            r=max(sum([r[j] for j in range(len(r)) if j%2==0]),sum([r[j] for j in range(len(r)) if j%2==1]))
            s=l+r
      else:
            s01=sum([l[j] for j in range(len(l)) if j%2==0])+sum([r[j] for j in range(len(r)) if j%2==1])
            s10=sum([l[j] for j in range(len(l)) if j%2==1])+sum([r[j] for j in range(len(r)) if j%2==0])
            #print('i:'+str(i)+',s01:'+str(s01)+',s10:'+str(s10))
            s=max(s10,s01)
            s=0
      ans=max(ans,s)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
if n%2 == 0:
    dp_l = [0]*(n//2+1)
    dp_r = [0]*(n//2+1)
    for i in range(n//2):
        dp_l[i+1] = A[2*i]
        dp_r[i+1] = A[2*i+1]
    for i in range(len(dp_l)-1):
        dp_l[i+1] += dp_l[i]
        dp_r[i+1] += dp_r[i]
    ans = 0
    for i in range(n//2+1):
        ans = max(ans,dp_r[n//2]-dp_r[i]+dp_l[i])
    print(ans)

Submission status: Wrong Answer

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

DP = [[-10**18 for i in range((N+1)//2)] for i in range(N)]

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

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

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

Submission status: Wrong Answer

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

DP = [[-10**9 for i in range((N+1)//2)] for i in range(N)]

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

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

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

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

Submission status: Wrong Answer

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

DP = [[-10**9 for i in range((N+1)//2)] for i in range(N)]

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

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

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
K = N % 2 + 1
A = tuple(map(int, input().split()))

table = [[0] * (K + 2) for _ in range(N + 1)]
for i in range(N):
    for j in range(K + 1):
        table[i + 1][j] = max(table[i][j] + (A[i] if not (i + j) % 2 else 0), table[i + 1][j])
        table[i + 1][j + 1] = max(table[i + 1][j + 1], table[i][j])
print(table[N][K])

Submission status: Wrong Answer

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

list1 = A[0::2]
list1 = filter(lambda x: x > 0, list1)
list2 = A[1::2]
list2 = filter(lambda x: x > 0, list2)

if sum(list1) > sum(list2):
    print(sum(list1))
else:
    print(sum(list2))

Submission status: Wrong Answer

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

list1 = A[0::2]
list2 = A[1::2]

if sum(list1) > sum(list2):
    ans = sum(list1)
else:
    ans = sum(list2)

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=[int(x) for x in input().split()]
print(max(sum(arr[::2]),sum(arr[1::2])))

Submission status: Wrong Answer

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

# oを選択 xを非選択とする　左から見て
# oxoxoxoxoxo に x を1つか2つ挿入することを考える
# 状態を4つ設定 (最後がxかoか)(挿入ずみのxの数)の形式でやる
# a=[1,2,3,4,5,6,7]
x0,x1,x2,o0,o1,o2=a[0],0,-10**18,-10**18,a[1],-10**18
for i in a[2:]:
    x0,x1,x2,o0,o1,o2=o0,max(o1,x0),max(o2,x1),x0+i,x1+i,x2+i
if n%2==0:
    print(max(x0,x1,o1))
else:
    print(max(x1,x2,o2))

Submission status: Wrong Answer

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

# oを選択 xを非選択とする　左から見て
# oxoxoxoxoxo に x を1つか2つ挿入することを考える
# 状態を4つ設定 (最後がxかoか)(挿入ずみのxの数)の形式でやる
#a=[1,2,3,4,5,6,7]
x0,x1,x2,o0,o1,o2=a[0],0,0,-10**30,a[1],-10**30
for i in a[2:]:
    x0,x1,x2,o0,o1,o2=o0,max(o1,x0),max(o2,x1),x0+i,x1+i,x2+i
if n%2==0:
    print(max(x0,x1,o1))
else:
    print(max(x1,x2,o2))

Submission status: Wrong Answer

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

# oを選択 xを非選択とする　左から見て
# oxoxoxoxoxo に x を1つか2つ挿入することを考える
# 状態を4つ設定 (最後がxかoか)(挿入ずみのxの数)の形式でやる
#a=[1,2,3,4,5,6,7]
x0,x1,x2,o0,o1,o2=a[0],0,0,-10**18,a[1],-10**18
for i in a[2:]:
    x0,x1,x2,o0,o1,o2=o0,max(o1,x0),max(o2,x1),x0+i,x1+i,x2+i
if n%2==0:
    print(max(x0,x1,o1))
else:
    print(max(x1,x2,o2))

Submission status: Wrong Answer

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

# oを選択 xを非選択とする　左から見て
# oxoxoxoxoxo に x を1つか2つ挿入することを考える
# 状態を4つ設定 (最後がxかoか)(挿入ずみのxの数)の形式でやる
x0,x1,x2,o0,o1,o2=a[0],0,0,-10**10,a[1],-10**10
for i in a[2:]:
    x0,x1,x2,o0,o1,o2=o0,max(o1,x0),max(o2,x1),x0+i,x1+i,x2+i
if n%2==0:
    print(max(x0,x1,o1))
else:
    print(max(x1,x2,o2))

Submission status: Wrong Answer

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

# oを選択 xを非選択とする　左から見て
# oxoxoxoxoxo に x を1つか2つ挿入することを考える
# 状態を4つ設定 (最後がxかoか)(挿入ずみのxの数)の形式でやる
x0,x1,x2,o0,o1,o2=a[0],0,-10**10,-10**10,a[1],-10**10
for i in a[2:]:
    x0,x1,x2,o0,o1,o2=o0,max(o1,x0),max(o2,x1),x0+i,x1+i,x2+i
if n%2==0:
    print(max(x0,x1,o1))
else:
    print(max(x1,x2,o2))

Submission status: Wrong Answer

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

# oを選択 xを非選択とする　左から見て
# oxoxoxoxoxo に x を1つか2つ挿入することを考える
# 状態を4つ設定 (最後がxかoか)(挿入ずみのxの数)の形式でやる
x0,x1,x2,o0,o1,o2=a[0],0,-10**10,-10**10,a[1],-10**10
for i in a[2:]:
    x0,x1,x2,o0,o1,o2=o0,max(o1,x0),max(o2,x1),x0+i,x1+i,x2+i
if n%2==0:
    print(max(x1,o1))
else:
    print(max(x2,o2))

Submission status: Wrong Answer

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

ans = 0

A_even = A[0::2] # 0,2,4... (奇数のときn+1個)
A_odd  = A[1::2] # 1,3,5... (奇数のときn個)

A_even_sum = [0 for i in range(len(A_even))]
A_odd_sum  = [0 for i in range(len(A_odd))]

for i in range(len(A_even)):
    if(i==0):
        A_even_sum[i] = A_even[i]
    else:
        A_even_sum[i] = A_even_sum[i-1] + A_even[i]

for i in range(len(A_odd)):
    if(i==0):
        A_odd_sum[i] = A_odd[i]
    else:
        A_odd_sum[i] = A_odd_sum[i-1] + A_odd[i]

if(N%2 == 0):
    # 偶数個の場合 例 [0 2 4] [1 3 5]
    n = int(N/2)

    # A_evenの(0からi-1まで)、A_oddから(iからn-1まで)を選択する
    ans = max(A_even_sum[n-1],A_odd_sum[n-1])
    if(n >= 2):
        for i in range(1,n):
            new_ans = A_even_sum[i-1] + A_odd_sum[n-1] - A_odd_sum[i-1]
            if(new_ans > ans):
                ans = new_ans
                
else:
    # 奇数個の場合 例 [0 2 4 6] [1 3 5]
    n = int((N-1)/2)
    
    # 1.A_evenのみから選択→最も小さい1個を除外したものが最適
    if(n == 1):
        ans = max(A)
    elif(n == 2):
        ans = max(A[0]+A[2],A[0]+A[3],A[0]+A[4],A[1]+A[3],A[1]+A[4],A[2]+A[4])
    else:
        ans = A_even_sum[n] - min(A_even)
    
    # 1-1. A_oddのみから全部選択
    ans = max(ans,A_odd_sum[n-1])
    
    # 2.A_even(0からn_s-1まで) → A_odd(n_sからn_eまで) → A_even(n_e+2からnまで) 
    # n_s≧1, n_e≦n-1, n_e＞n_s
    
    if(n >= 3):
        flag = 0
        ans2 = 0
        n_e_max = 0
        
        # 2-1.A_odd(0からn_eまで) → A_even(n_e+2からnまで) 
        # まず、いきなりoddからはじめる場合で、A_oddの終点を定める
        for n_e in range(n-1):
            new_ans2 = A_even_sum[n] - A_even_sum[n_e+1] + A_odd_sum[n_e]
            if(flag == 0):
                flag = 1
                n_e_max = n_e
                ans2 = new_ans2
            elif(new_ans2 >= ans2):
                n_e_max = n_e
                ans2 = new_ans2
        
        # 次に、n_sを変化させて考える
        for n_s in range(1,n_e_max+1):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e_max+1] + A_odd_sum[n_e_max] - A_odd_sum[n_s-1]
            if(new_ans2 >= ans2):
                ans2 = new_ans2
    
        # 2-2. A_even(0からn_s-1まで) → A_odd(n_sからn-1まで)
        for n_s in range(1,n):
            new_ans2 = A_even_sum[n_s-1] + A_odd_sum[n-1] - A_odd_sum[n_s-1]
            if(new_ans2 >= ans2):
                ans2 = new_ans2
                
        ans = max(ans,ans2)
        
print(ans)

Submission status: Wrong Answer

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

ans = 0

A_even = A[0::2] # 0,2,4... (奇数のときn+1個)
A_odd  = A[1::2] # 1,3,5... (奇数のときn個)

A_even_sum = [0 for i in range(len(A_even))]
A_odd_sum  = [0 for i in range(len(A_odd))]

for i in range(len(A_even)):
    if(i==0):
        A_even_sum[i] = A_even[i]
    else:
        A_even_sum[i] = A_even_sum[i-1] + A_even[i]

for i in range(len(A_odd)):
    if(i==0):
        A_odd_sum[i] = A_odd[i]
    else:
        A_odd_sum[i] = A_odd_sum[i-1] + A_odd[i]

if(N%2 == 0):
    # 偶数個の場合 例 [0 2 4] [1 3 5]
    n = int(N/2)

    # A_evenの(0からi-1まで)、A_oddから(iからn-1まで)を選択する
    ans = max(A_even_sum[n-1],A_odd_sum[n-1])
    if(n >= 2):
        for i in range(1,n):
            new_ans = A_even_sum[i-1] + A_odd_sum[n-1] - A_odd_sum[i-1]
            if(new_ans > ans):
                ans = new_ans
                
else:
    # 奇数個の場合 例 [0 2 4 6] [1 3 5]
    n = int((N-1)/2)
    
    # 1.A_evenのみから選択→最も小さい1個を除外したものが最適
    if(n == 1):
        ans = max(A)
    elif(n == 2):
        ans = max(A[0]+A[2],A[0]+A[3],A[0]+A[4],A[1]+A[3],A[1]+A[4],A[2]+A[4])
    else:
        ans = A_even_sum[n] - min(A_even)
    
    # 1-1. A_oddのみから全部選択
    ans = max(ans,A_odd_sum[n-1])
    
    # 2.A_even(0からn_s-1まで) → A_odd(n_sからn_eまで) → A_even(n_e+2からnまで) と選択する
    # n_s≧1, n_e≦n-1, n_e＞n_s
    
    if(n >= 3):
        flag = 0
        ans2 = 0
        n_e_max = 0
        
        # まず、いきなりoddからはじめる場合で、A_oddの終点を定める
        for n_e in range(n):
            new_ans2 = A_even_sum[n] - A_even_sum[n_e+1] + A_odd_sum[n_e]
            if(flag == 0):
                flag = 1
                n_e_max = n_e
                ans2 = new_ans2
            elif(new_ans2 >= ans2):
                n_e_max = n_e
                ans2 = new_ans2
        
        # 次に、n_sを変化させて考える
        for n_s in range(1,n_e_max+1):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e_max+1] + A_odd_sum[n_e_max] - A_odd_sum[n_s-1]
            if(new_ans2 >= ans2):
                ans2 = new_ans2
        
        ans = max(ans,ans2)
        
        
print(ans)

Submission status: Wrong Answer

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

ans = 0

A_even = A[0::2] # 0,2,4... (奇数のときn+1個)
A_odd  = A[1::2] # 1,3,5... (奇数のときn個)

A_even_sum = [0 for i in range(len(A_even))]
A_odd_sum  = [0 for i in range(len(A_odd))]

for i in range(len(A_even)):
    if(i==0):
        A_even_sum[i] = A_even[i]
    else:
        A_even_sum[i] = A_even_sum[i-1] + A_even[i]

for i in range(len(A_odd)):
    if(i==0):
        A_odd_sum[i] = A_odd[i]
    else:
        A_odd_sum[i] = A_odd_sum[i-1] + A_odd[i]

if(N%2 == 0):
    # 偶数個の場合 例 [0 2 4] [1 3 5]
    n = int(N/2)

    # A_evenの(0からi-1まで)、A_oddから(iからn-1まで)を選択する
    ans = max(A_even_sum[n-1],A_odd_sum[n-1])
    if(n >= 2):
        for i in range(1,n):
            new_ans = A_even_sum[i-1] + A_odd_sum[n-1] - A_odd_sum[i-1]
            if(new_ans > ans):
                ans = new_ans
                
else:
    # 奇数個の場合 例 [0 2 4 6] [1 3 5]
    n = int((N-1)/2)
    
    # 1.A_evenのみから選択→最も小さい1個を除外したものが最適
    if(n == 1):
        ans = max(A)
    elif(n == 2):
        ans = max(A[0]+A[2],A[0]+A[3],A[0]+A[4],A[1]+A[3],A[1]+A[4],A[2]+A[4])
    else:
        ans = A_even_sum[n] - min(A_even)
    
    # 1-1. A_oddのみから全部選択
    ans = max(ans,A_odd_sum[n-1])
    
    # 2.A_even(0からn_s-1まで) → A_odd(n_sからn_eまで) → A_even(n_e+2からnまで) と選択する
    # n_s≧1, n_e≦n-1, n_e＞n_s
    
    if(n >= 3):
        flag = 0
        ans2 = 0
        n_e_max = 0
        
        # まず、いきなりoddからはじめる場合で、A_oddの終点を定める
        for n_e in range(n):
            new_ans2 = A_even_sum[n] - A_even_sum[n_e+1] + A_odd_sum[n_e]
            if(flag == 0):
                flag = 1
                n_e_max = n_e
                ans2 = new_ans2
            elif(new_ans2 >= ans2):
                n_e_max = n_e
                ans2 = new_ans2
        
        # 次に、n_sを変化させて考える
        for n_s in range(1,n_e_max):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e_max+1] + A_odd_sum[n_e_max] - A_odd_sum[n_s-1]
            if(new_ans2 >= ans2):
                ans2 = new_ans2
        
        ans = max(ans,ans2)
        
        
print(ans)

Submission status: Wrong Answer

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

ans = 0

A_even = A[0::2] # 0,2,4... (奇数のときn+1個)
A_odd  = A[1::2] # 1,3,5... (奇数のときn個)

A_even_sum = [0 for i in range(len(A_even))]
A_odd_sum  = [0 for i in range(len(A_odd))]

for i in range(len(A_even)):
    if(i==0):
        A_even_sum[i] = A_even[i]
    else:
        A_even_sum[i] = A_even_sum[i-1] + A_even[i]

for i in range(len(A_odd)):
    if(i==0):
        A_odd_sum[i] = A_odd[i]
    else:
        A_odd_sum[i] = A_odd_sum[i-1] + A_odd[i]

if(N%2 == 0):
    # 偶数個の場合 例 [0 2 4] [1 3 5]
    n = int(N/2)

    # A_evenの(0からi-1まで)、A_oddから(iからn-1まで)を選択する
    ans = max(A_even_sum[n-1],A_odd_sum[n-1])
    if(n >= 2):
        for i in range(1,n):
            new_ans = A_even_sum[i-1] + A_odd_sum[n-1] - A_odd_sum[i-1]
            if(new_ans > ans):
                ans = new_ans
                
else:
    # 奇数個の場合 例 [0 2 4 6] [1 3 5]
    n = int((N-1)/2)
    
    # 1.A_evenのみから選択→最も小さい1個を除外したものが最適
    if(n == 1):
        ans = max(A)
    else:
        ans = A_even_sum[n] - min(A_even)
    
    # 1-1. A_oddのみから全部選択
    ans = max(ans,A_odd_sum[n-1])
    
    # 2.A_even(0からn_s-1まで) → A_odd(n_sからn_eまで) → A_even(n_e+2からnまで) と選択する
    # n_s≧1, n_e≦n-1, n_e＞n_s
    
    if(n >= 3):
        flag = 0
        ans2 = 0
        n_e_max = 0
        
        # まず、n_s=1とおいて、A_oddの終点を定める
        n_s = 1
        for n_e in range(2,n):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e+1] + A_odd_sum[n_e] - A_odd_sum[n_s-1]
            if(flag == 0):
                flag = 1
                n_e_max = n_e
                ans2 = new_ans2
            elif(new_ans2 >= ans2):
                n_e_max = n_e
                ans2 = new_ans2
        
        # 次に、n_sを変化させて考える
        for n_s in range(1,n_e_max):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e_max+1] + A_odd_sum[n_e_max] - A_odd_sum[n_s-1]
            if(new_ans2 >= ans2):
                ans2 = new_ans2
        
        ans = max(ans,ans2)
        
        
print(ans)

Submission status: Wrong Answer

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

ans = 0

A_even = A[0::2] # 0,2,4... (奇数のときn+1個)
A_odd  = A[1::2] # 1,3,5... (奇数のときn個)

A_even_sum = [0 for i in range(len(A_even))]
A_odd_sum  = [0 for i in range(len(A_odd))]

for i in range(len(A_even)):
    if(i==0):
        A_even_sum[i] = A_even[i]
    else:
        A_even_sum[i] = A_even_sum[i-1] + A_even[i]

for i in range(len(A_odd)):
    if(i==0):
        A_odd_sum[i] = A_odd[i]
    else:
        A_odd_sum[i] = A_odd_sum[i-1] + A_odd[i]

if(N%2 == 0):
    # 偶数個の場合 例 [0 2 4] [1 3 5]
    n = int(N/2)

    # A_evenの(0からi-1まで)、A_oddから(iからn-1まで)を選択する
    ans = max(A_even_sum[n-1],A_odd_sum[n-1])
    if(n >= 2):
        for i in range(1,n):
            new_ans = A_even_sum[i-1] + A_odd_sum[n-1] - A_odd_sum[i-1]
            if(new_ans > ans):
                ans = new_ans
                
else:
    # 奇数個の場合 例 [0 2 4 6] [1 3 5]
    n = int((N-1)/2)
    
    # 1.A_evenのみから選択→最も小さい1個を除外したものが最適
    if(n == 1):
        ans = max(A)
    else:
        ans = A_even_sum[n] - min(A_even)
    
    # 1-1. A_oddのみから全部選択
    ans = max(ans,A_odd_sum[n-1])
    
    # 2.A_even(0からn_s-1まで) → A_odd(n_sからn_eまで) → A_even(n_e+2からnまで) と選択する
    # n_s≧1, n_e≦n-2, n_e＞n_s
    
    if(n >= 3):
        flag = 0
        ans2 = 0
        n_e_max = 0
        
        # まず、n_s=1とおいて、A_oddの終点を定める
        n_s = 1
        for n_e in range(2,n-1):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e+1] + A_odd_sum[n_e] - A_odd_sum[n_s-1]
            if(flag == 0):
                flag = 1
                n_e_max = n_e
                ans2 = new_ans2
            elif(new_ans2 >= ans2):
                n_e_max = n_e
                ans2 = new_ans2
        
        # 次に、n_sを変化させて考える
        for n_s in range(1,n_e_max):
            new_ans2 = A_even_sum[n_s-1] + A_even_sum[n] - A_even_sum[n_e_max+1] + A_odd_sum[n_e_max] - A_odd_sum[n_s-1]
            if(new_ans2 >= ans2):
                ans2 = new_ans2
        
        ans = max(ans,ans2)
        
        
print(ans)