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 = [int(x) for x in input().split()]

sm_e = []
sm_o = []

e = 0
o = 0

for i in range(n):
    if i % 2 == 0:
        e += a[i]
        sm_e.append(e)
    else:
        o += a[i]
        sm_o.append(o)

tot_e = sm_e[-1]
tot_o = sm_o[-1]

m = len(sm_o)

if n % 2 == 0:
    ans = max(tot_e, tot_o)
    for i in range(m):
        ans = max(ans, sm_e[i] + tot_o - sm_o[i])
    for i in range(m-1):
        ans = max(ans, sm_o[i] + tot_e - sm_e[i+1])
    print(ans)
    exit()

ans = tot_o

for i in range(m):
    if i != m-1:
        ans = max(ans, sm_e[i]+tot_o-sm_o[i])
    else:
        ans = max(ans, tot_o-a[-1])

l = [0]*m
for i in range(m):
    l[i] = sm_e[i]-sm_o[i]

val = l[0]
tmp = 0

for i in range(m-1):
    ans = max(ans, sm_o[i] + tot_e - sm_e[i+1])
    if i != 0:
        if val < l[i]:
            val = l[i]
    ans = max(ans, sm_o[i] + tot_e - sm_e[i+1] + val)

for i in range(n):
    if i % 2 == 0:
        ans = max(ans, tot_e - a[i])

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
if n<=3:
  print(max(arr))
else:
  if n%2==0:
    ans=0
    tmp1=0
    tmp2=0
    acum1=[0]
    acum2=[0]
    for i in range(n):
      if i%2==0:
        tmp1+=arr[i]
        acum1.append(acum1[-1]+arr[i])
        acum2.append(acum2[-1]+0)
      else:
        tmp2+=arr[i]
        acum1.append(acum1[-1]+0)
        acum2.append(acum2[-1]+arr[i])
    ans=max(ans,tmp1,tmp2)
    for i in range(0,n-3,2):
      tmp=(acum1[i+1]-acum1[0])+(acum2[-1]-acum2[i+2])
      ans=max(ans,tmp)
    print(ans)
  else:
    ans=0
    tmp1=0
    tmp2=0
    tmp3=0
    acum1=[0]
    acum2=[0]
    for i in range(n):
      if i%2==0:
        tmp1+=arr[i]
        tmp3+=arr[i]
        acum1.append(acum1[-1]+arr[i])
        acum2.append(acum2[-1]+0)
      else:
        tmp2+=arr[i]
        acum1.append(acum1[-1]+0)
        acum2.append(acum2[-1]+arr[i])
    ans=max(ans,tmp1-arr[-1],tmp2,tmp3-arr[0])
    for i in range(0,n-3,2):
      tmp=(acum1[i+1]-acum1[0])+(acum2[-1]-acum2[i+2])
      ans=max(ans,tmp)
    for i in range(1,n-3,2):
      tmp=(acum2[i+1]-acum1[0])+(acum1[-1]-acum1[i+2])
      ans=max(ans,tmp)
    acummax=[0]
    for i in range(n-3,-1,-1):
      tmp=acum1[-1]-acum1[i+2]+acum2[i+1]
      acummax.append(max(acummax[-1],tmp))
    acummax=acummax[::-1]
    for i in range(0,n-3,2):
      tmp=acum1[i+1]-acum1[0]-acum2[i+2]+acummax[i+3]
      ans=max(ans,tmp)
    print(ans)

Submission status: Wrong Answer

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

get_DP  = [[0 for i in range(3)] for j in range(N)]
pass_DP = [[0 for i in range(3)] for j in range(N)]
for i in range(N):
    # 常にとるやつ
    if i%2 == 0:
        get_DP[i][0] = (pass_DP[i-1][0] if i>0 else 0) + S[i]
    else:
        pass_DP[i][0] = get_DP[i-1][0]
    if i >= 1:
        get_DP[i][1] = pass_DP[i-1][1] + S[i]
        pass_DP[i][1] = max(pass_DP[i-1][0], get_DP[i-1][1])
    if i >= 2:
        get_DP[i][2] = pass_DP[i-1][2] + S[i]
        pass_DP[i][2] = max(pass_DP[i-1][1], get_DP[i-1][2])
print(max(get_DP[-1]))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate as f
n,*a = [int(i) for i in open(0).read().split()]
a1 = list(f(a[::2],initial=0))
a2 = list(f(a[n-1::-2],initial=0))[::-1]
ans = max(x+y for x,y in zip(a1,a2[n&1:]))
if n&1: ans = max(ans, max(x+y+mid for x,y,mid in zip(a1,a2[1:],a[1::2])))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env pypy3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for s in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# d = collections.defaultdict(list)
import sys
sys.setrecursionlimit(15000)

n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
dp = [[None]*n for _ in range(n//2+1)]
dp[0] = [0]*n
dp[1][0] = a[0]
dp[1][1] = a[1]
ret = 0
if n % 2 == 0:
    for i in range(2,n):
        for j in range(1,n//2+1):
            if dp[j-1][i-2] != None:
                dp[j][i] = dp[j-1][i-2]+a[i]
                if j == n//2:
                    ret = max(ret,dp[j][i])
else:
    for i in range(2,n):
        for j in range(1,n//2+1):
            if dp[j-1][i-2] != None or dp[j-1][i-3] != None:
                if dp[j-1][i-2] != None and dp[j-1][i-3] != None:
                    dp[j][i] = max(dp[j-1][i-2],dp[j-1][i-3])+a[i]
                elif dp[j-1][i-2] != None:
                    dp[j][i] = dp[j-1][i-2]+a[i]
                elif dp[j-1][i-3] != None:
                    dp[j][i] = dp[j-1][i-3]+a[i]
                if j == n//2:
                    ret = max(ret,dp[j][i])
#print(dp)
print(ret)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin


def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    if n % 2 == 0:
        res_1 = 0
        res_2 = 0
        for i in range(n):
            if i % 2 == 0:
                res_1 += a[i]
            else:
                res_2 += a[i]
        print(max(res_1, res_2))
    else:
        v = [[None for j in range(3)] for i in range(n)]
        v[0][0] = a[0]
        v[1][1] = a[1]
        v[2][2] = a[2]
        for i in range(3, n):
            for j in range(3):
                c = []
                if j == 2:
                    if v[i-2][j] is not None:
                        c.append(v[i-2][j])
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                    if v[i-4][j-2] is not None:
                        c.append(v[i-4][j-2])
                elif j == 1:
                    if v[i-2][j] is not None:
                        c.append(v[i-2][j])
                    if v[i-3][j-1] is not None:
                        c.append(v[i-3][j-1])
                else:
                    if v[i-2][j] is not None:
                        c.append(v[i-2][j])
                if len(c) == 0:
                    continue
                v[i][j] = max(c) + a[i]
        c = [v[n-1][j] for j in range(3) if v[n-1][j] is not None]
        print(max(c))


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


main()

Submission status: Wrong Answer

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

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

ans = 0

def solve(A, N):
    m = 0
    mi = -2
    a = 0
    for i in range(0, N, 2):
        a += A[i] - A[i + 1]
        if a > m:
            m = a
            mi = i
    
    ans = 0
    if mi >= 0:
        ans += sum(A[0:mi+1:2])
    ans =  + sum(A[mi+3:N:2])
    print(ans)

if N % 2 == 0:
    solve(A, N)
else:
    dp = [[0, 0, 0] for i in range(N)]
    dp[0] = [A[0], 0, 0]

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

    print(max(dp[N - 1]))

Submission status: Wrong Answer

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

def main():
    n=int(input())
    a=list(map(int,input().split()))
    #print(a)
    
    if n%2==0:
        print(max(sum(a[::2]),sum(a[1::2])))
        sys.exit()

    if n==3:
        print(max(a))
        sys.exit()

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

main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    A = list(map(int, input().split()))
    a0, a1, a2, b0, b1, b2 = 0, 0, 0, 0, 0, 0
    for i, a in enumerate(A):
        a0, a1, a2, b0, b1, b2 = (
                b0,
                max(b1, a0),
                max(b2, a1),
                a0 + a,
                a1 + a if i >= 1 else a1,
                a2 + a if i >= 2 else a2)
 
    if n & 1:
        return max(b2, a1)

Submission status: Wrong Answer

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

odd_l = [0]
odd_l_tmp = 0
for i in range(N):
    if i % 2 == 0:
        odd_l_tmp += A[i]
        odd_l.append(odd_l_tmp)

odd_r = [0]
odd_r_tmp = 0
for i_inv in range(N):
    i = N - 1 - i_inv
    if i % 2 == 0:
        odd_r_tmp += A[i]
        odd_r.append(odd_r_tmp)

evn_l = [0]
evn_l_tmp = 0
for i in range(N):
    if i % 2 == 1:
        evn_l_tmp += A[i]
        evn_l.append(evn_l_tmp)
        
evn_r = [0]
evn_r_tmp = 0
for i_inv in range(N):
    i = N - 1 - i_inv
    if i % 2 == 1:
        evn_r_tmp += A[i]
        evn_r.append(evn_r_tmp)

ans = 'kanipanman'

def retAns(ans, ans_tmp):
    if ans == 'kanipanman':
        ret = ans_tmp
    else:
        ret = max(ans, ans_tmp)
    return ret

# mixed
for i in range(1, N // 2):
    ans_tmp = odd_l[i] + evn_r[N // 2 - i]
    # print("# mix(OE)", i, odd_l[i], evn_r[N // 2 - 1 - i], ans_tmp)
    ans = retAns(ans, ans_tmp)
    if N % 2 > 0:
        ans_tmp = evn_l[i] + odd_r[N // 2 - i]
        # print("# mix(EO)", i, evn_l[i], odd_r[N // 2 - 1 - i], ans_tmp)
        ans = retAns(ans, ans_tmp)

# odd only
if N % 2 > 0:
    sum_tmp = odd_l[-1]
    for i in range(N):
        if i % 2 == 0:
            ans_tmp = sum_tmp - A[i]
            # print("# odd (sep)", i, sum_tmp, A[i], ans_tmp)
            ans = retAns(ans, ans_tmp)

else:
    ans_tmp = odd_r[-1]
    # print("# odd", ans_tmp)
    ans = retAns(ans, ans_tmp)
    

# evn only
ans_tmp = evn_r[-1]
# print("# evn", ans_tmp)
ans = retAns(ans, ans_tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    sin = list(map(int, input().split()))
    a0, a1, a2, b0, b1, b2 = 0, 0, 0, 0, 0, 0
    for i, a in enumerate(sin):
        a0, a1, a2, b0, b1, b2 = (
                b0,
                max(b1, a0),
                max(b2, a1),
                a0 + a,
                a1 + a if i >= 1 else a1,
                a2 + a if i >= 2 else a2)
 
    if n & 1:
        return max(b2, a1)

Submission status: Wrong Answer

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

        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[::-1]
        dp=[[0 for i in range(0,3)] for i in range(0,N)]
        dp[0][2]=A[0]
        dp[0][1]=-float('inf')
        dp[0][0]=0
        dp[1][2]=-float('inf')
        dp[1][1]=max(A[1],A[0])
        dp[1][0]=-float('inf')

        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]

        test2=dp[N-1][0]

        test3=sum(A[i] for i in range(0,N) if i%2==1)

        print(max(test1,test2,test3))

    if N%2==0:
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=A[0]
        dp[0][0]=-float('inf')
        dp[1][1]=-float('inf')
        dp[1][0]=-float('inf')

        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]=dp[i-2][1]

        test1=dp[N-1][0]

        A=A[::-1]
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=A[0]
        dp[0][0]=-float('inf')
        dp[1][1]=-float('inf')
        dp[1][0]=-float('inf')

        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]=dp[i-2][1]

        test2=dp[N-1][0]

        test3=sum(A[i] for i in range(0,N) if i%2==0)
        test4=sum(A[i] for i in range(0,N) if i%2==1)

        print(max(test1,test2,test3,test4))

Submission status: Wrong Answer

Solution code:
def main():
    #from sys import stdin, setrecursionlimit
    #setrecursionlimit(10**9)
    #r = input()
    #n = int(input())
    #a, b = map(int, input().split())
    #s, y = input().split()
    #a = input().split()
    #a = list(map(int, input().split()))
    #a = [list(input().split()) for i in range(n)]
    #a = [int(input()) for i in range(n)]
    #a = [list(map(int, input().split())) for i in range(n)]
    #a = [int(s) - 1 for s in input().split()]
    #l=[int(input()) for _ in range(int(input()))]
    #res = 0
    n=int(input())
    a=sorted(list(map(int,input().split())))
    if n%2==0:
        print(sum(a[1::2]))
    else:
        print(sum(a[::2]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
if n<=3:
  print(max(arr))
else:
  if n%2==0:
    ans=0
    tmp1=0
    tmp2=0
    acum1=[0]
    acum2=[0]
    for i in range(n):
      if i%2==0:
        tmp1+=arr[i]
        acum1.append(acum1[-1]+arr[i])
        acum2.append(acum2[-1]+0)
      else:
        tmp2+=arr[i]
        acum1.append(acum1[-1]+0)
        acum2.append(acum2[-1]+arr[i])
    ans=max(ans,tmp1,tmp2)
    for i in range(0,n-3,2):
      tmp=(acum1[i+1]-acum1[0])+(acum2[-1]-acum2[i+2])
      ans=max(ans,tmp)
    print(ans)
  else:
    ans=0
    tmp1=0
    tmp2=0
    tmp3=0
    acum1=[0]
    acum2=[0]
    for i in range(n):
      if i%2==0:
        tmp1+=arr[i]
        tmp3+=arr[i]
        acum1.append(acum1[-1]+arr[i])
        acum2.append(acum2[-1]+0)
      else:
        tmp2+=arr[i]
        acum1.append(acum1[-1]+0)
        acum2.append(acum2[-1]+arr[i])
    ans=max(ans,tmp1-arr[-1],tmp2,tmp3-arr[0])
    for i in range(0,n-3,2):
      tmp=(acum1[i+1]-acum1[0])+(acum2[-1]-acum2[i+2])
      ans=max(ans,tmp)
    for i in range(1,n-3,2):
      tmp=(acum2[i+1]-acum1[0])+(acum1[-1]-acum1[i+2])
      ans=max(ans,tmp)
    acummax=[0]
    for i in range(n-3,-1,-1):
      tmp=acum1[-1]-acum1[i+2]+acum2[i+1]
      acummax.append(max(acummax[-1],tmp))
    acummax=acummax[::-1]
    for i in range(0,n-3,2):
      tmp=acum1[i+1]-acum1[0]-acum2[i+2]+acummax[i+1]
      ans=max(ans,tmp)
    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(500000)

MOD = 1000000007

def smax(a,b):
    if a>b:
        return a
    else:
        return b

def smin(a,b):
    if a<b:
        return a
    else:
        return b

def main():
    N = int(readline())
    A = list(map(int,readline().split()))
    if N%2==0:
        a = 0
        for i in range(N//2):
            a+=A[2*i]
        b = 0
        for i in range(N//2):
            b+=A[2*i+1]
        print(smax(a,b))
    else:
        A.append(0)
        DP = [[[-10**27]*2 for j in range(3)] for i in range(N+2)]
        DP[0][0][0] = 0
        for i in range(N+1):
            DP[i+1][0][0] = DP[i][0][1]
            DP[i+1][1][0] = smax(DP[i][0][0],DP[i][1][1])
            DP[i+1][2][0] = smax(DP[i][1][0],DP[i][2][1])
            DP[i+1][0][1] = DP[i][0][0]+A[i]
            DP[i+1][1][1] = DP[i][1][0]+A[i]
            DP[i+1][2][1] = DP[i][2][0]+A[i]
            #print(DP[i+1][1][0])
        print(DP[N+1][2][0])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n,*a = [int(i) for i in open(0).read().split()]
a1 = list(accumulate(a[::2],initial=0))
a2 = list(accumulate(a[n-1::-2],initial=0))[::-1]
ans = max(x+y for x,y in zip(a1,a2))
if n&1:
    ans = max(ans, max(x+y+mid for x,y,mid in zip(a1,a2[1:],a[1::2])))
print(ans)

Submission status: Wrong Answer

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+10)]
    if N==3:
        print(max(A[0],A[1],A[2]))
    else:
        for i in range(N):
            if i<4:
                if i==0:
                    dp[i][0]=A[0]
                if i==1:
                    dp[i][1]=A[1]
                if i==2:
                    dp[i][2]=A[2]
                    dp[i][0]=A[0]+A[2]
                if i==3:
                    dp[i][1]=max(dp[1][1]+A[3],dp[0][0]+A[3])
            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: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from math import floor
def solve(a):
    c=1
    co=len(a)//2
    ar=[]
    for i in range(len(a)):
        ar.append([a[i],i])
    ar.sort(reverse=True)
    x=ar[0][1]
    ss=ar[0][0]
    f=[ss]
    i=1
    #print(ar)
    while c<co and i<len(a):
        y=ar[i][1]
        if abs(y-x)!=1:
            ss+=ar[i][0]
            f.append(ar[i][0])
            x=y 
            c+=1
        i+=1
    return (ss)
def solve2(a):
    c=1
    co=len(a)//2
    ar=[]
    for i in range(len(a)):
        ar.append([a[i],i])
    ar.sort(reverse=True)
    x=ar[1][1]
    ss=ar[1][0]
    f=[ss]
    i=2
    #print(ar)
    while c<co and i<len(a):
        y=ar[i][1]
        if abs(y-x)!=1:
            ss+=ar[i][0]
            f.append(ar[i][0])
            x=y 
            c+=1
        i+=1
    return (ss)
n=int(input())
a=[int(x) for x in input().split()]
print(max(solve(a),solve2(a)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

if n % 2 == 0:
    print(max(sum(a_list[0::2]),sum(a_list[1::2])))
else: # 2パス使える
    dp = [[-float('inf') for _ in range(n)] for __ in range(3)]
    dp[2][-1] = a_list[-1]

    for j in reversed(range(3)):
        for i in reversed(range(n)):
            if j == 2 and i >= n-2:
                pass
            elif j == 2:
                dp[j][i] = dp[j][i+2] + a_list[i]
            elif i == n-2:
                dp[j][i] = dp[j+1][i+1]
            elif i > n-2:
                pass
            else:
                dp[j][i] = max(dp[j+1][i+1],dp[j][i+2] + a_list[i])
    print(dp[0][0])

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a0, a1, a2, b0, b1, b2 = 0, 0, 0, 0, 0, 0
    for i, a in enumerate(A):
        a0, a1, a2, b0, b1, b2 = (
                b0,
                max(b1, a0),
                max(b2, a1),
                a0 + a,
                a1 + a if i >= 1 else a1,
                a2 + a if i >= 2 else a2)

    if N & 1:
        return max(a2, b1)
    else:
        return max(a1, b0)


print(main())

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(500000)

MOD = 1000000007

def smax(a,b):
    if a>b:
        return a
    else:
        return b

def smin(a,b):
    if a<b:
        return a
    else:
        return b

def main():
    N = int(readline())
    A = list(map(int,readline().split()))
    if N%2==0:
        a = 0
        for i in range(N//2):
            a+=A[2*i]
        b = 0
        for i in range(N//2):
            b+=A[2*i+1]
        print(smax(a,b))
    else:
        DP = [[[-10**27]*2 for j in range(3)] for i in range(N+1)]
        DP[0][0][0] = 0
        for i in range(N):
            DP[i+1][0][0] = DP[i][0][1]
            DP[i+1][1][0] = smax(DP[i][0][0],DP[i][1][1])
            DP[i+1][2][0] = smax(DP[i][1][0],DP[i][2][1])
            DP[i+1][0][1] = DP[i][0][0]+A[i]
            DP[i+1][1][1] = DP[i][1][0]+A[i]
            DP[i+1][2][1] = DP[i][2][0]+A[i]
            #print(DP[i+1][1][0])
        print(smax(DP[N][2][1],DP[N][1][0]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N==2:
    print(max(A))
elif N==3:
    print(max(A))
else:
    if N%2==1:
        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[::-1]
        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]

        test2=dp[N-1][0]

        test3=sum(A[i] for i in range(0,N) if i%2==1)

        print(max(test1,test2,test3))

    if N%2==0:
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=A[0]
        dp[0][0]=-float('inf')
        dp[1][1]=-float('inf')
        dp[1][0]=-float('inf')

        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]=dp[i-2][1]

        test1=dp[N-1][0]

        A=A[::-1]
        dp=[[0 for i in range(0,2)] for i in range(0,N)]
        dp[0][1]=A[0]
        dp[0][0]=-float('inf')
        dp[1][1]=-float('inf')
        dp[1][0]=-float('inf')

        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]=dp[i-2][1]

        test2=dp[N-1][0]

        test3=sum(A[i] for i in range(0,N) if i%2==0)
        test4=sum(A[i] for i in range(0,N) if i%2==1)

        print(max(test1,test2,test3,test4))

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a0, a1, a2, b0, b1, b2 = 0, 0, 0, 0, 0, 0
    for i, a in enumerate(A):
        a0, a1, a2, b0, b1, b2 = (
                b0,
                max(b1, a0),
                max(b2, a1),
                a0 + a,
                a1 + a if i >= 1 else a1,
                a2 + a if i >= 2 else a2)
        print(a0, a1, a2, b0, b1, b2)

    if N & 1:
        return max(a2, b1)
    else:
        return max(a1, b0)


print(main())

Submission status: Wrong Answer

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

if n % 2 == 0:
    print(max(sum(a_list[0::2]),sum(a_list[1::2])))
else: # 2パス使える
    dp = [[-float('inf') for _ in range(n)] for __ in range(3)]
    dp[2][-1] = a_list[-1]

    for j in reversed(range(3)):
        for i in reversed(range(n)):
            if j == 2 and i >= n-2:
                pass
            elif j == 2:
                dp[j][i] = dp[j][i+2] + a_list[i]
            elif i == n-2:
                dp[j][i] = dp[j+1][i+1]
            elif i > n-2:
                pass
            else:
                print(j,i)
                dp[j][i] = max(dp[j+1][i+1],dp[j][i+2] + a_list[i])
    print(dp[0][0])

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect

sys.setrecursionlimit(10 ** 8)
# mem = {}

M = 10 ** 9 + 7


def gu(A):
    aa = sum([a for (i, a) in enumerate(A) if i % 2 == 0])
    bb = sum([a for (i, a) in enumerate(A) if i % 2 == 1])

    maxcc = -10000000000000000000
    for i in range(2, len(A), 2):
        cc = sum([a for (i, a) in enumerate(A[:i]) if i % 2 == 0]) + sum(
            [a for (i, a) in enumerate(A[i:]) if i % 2 == 1])
        maxcc = max(maxcc, cc)

    return max(aa, bb, maxcc)


def ki(A):
    return sum([a for (i, a) in enumerate(A) if i % 2 == 0])


def main():
    N = int(input())
    A = [int(a) for a in input().split()]

    if N % 2 == 0:
        print(gu(A))
        return

    max_v = -10000000000000

    for i in range(N - 1):
        if i % 2 == 0:
            aa = gu(A[:i])
            bb = ki(A[i + 2:])
            # print(aa + bb)
            max_v = max(max_v, aa + bb)
        else:
            aa = ki(A[:i])
            bb = gu(A[i + 2:])
            # print(aa + bb)
            max_v = max(max_v, aa + bb)
    print(max_v)


if __name__ == "__main__":
    # print(ki([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]))
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
from math import floor
def solve(a):
    c=1
    co=len(a)//2
    ar=[]
    for i in range(len(a)):
        ar.append([a[i],i])
    ar.sort(reverse=True)
    x=ar[0][1]
    ss=ar[0][0]
    f=[ss]
    i=1
    #print(ar)
    while c<co and i<len(a):
        y=ar[i][1]
        if abs(y-x)!=1:
            ss+=ar[i][0]
            f.append(ar[i][0])
            x=y 
            c+=1
        i+=1
    print(ss)
n=int(input())
(solve([int(x) for x in input().split()]))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
inf = float('inf')
ans = -1 *inf

if N % 2 == 0:
    S_odd = [0]*(N//2+1)
    S_even = [0]*(N//2+1)
    s_odd = 0
    s_even = 0
    for i in range(len(A)):
        if i%2 == 0:
            s_odd += A[i]
            S_odd[i//2+1] = s_odd
        else:
            s_even += A[i]
            S_even[i//2+1] = s_even
    
    s = 0
    for j in range(N//2+1):
        s = S_odd[j] + S_even[N//2]-S_even[j] 
        ans = max(ans,s)
else:
    S_odd = [0]*(N//2+2)
    S_even = [0]*(N//2+1)
    odd = []
    even = []
    s_odd = 0
    s_even = 0
    for i in range(len(A)):
        if i%2 == 0:
            s_odd += A[i]
            S_odd[i//2+1] = s_odd
            odd.append(A[i])
        else:
            s_even += A[i]
            S_even[i//2+1] = s_even
            even.append(A[i])
    
    s = 0
    ans = 0

    for j in range(N//2):
        for k in range(j,N//2):
            s = S_odd[j] + S_even[k]-S_even[j] +S_odd[N//2+1]-S_odd[k+1]
            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:
    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+10)]
    if N==3:
        print(max(A[0],A[1],A[2]))
    else:
        for i in range(N):
            if i<4:
                if i==0:
                    dp[i][0]=A[0]
                if i==1:
                    dp[i][1]=A[1]
                if i==2:
                    dp[i][2]=max(A[2],A[0])
                    dp[i][0]=A[0]+A[2]
                if i==3:
                    dp[i][1]=max(dp[1][1]+A[3],dp[0][0]+A[3])
            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: Wrong Answer

Solution code:
n=int(input())

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

select = n//2

ans = 0

memo = 0

start=0

for i in range(n):
    if i%2==1:
        continue
    
    if 1+i//2 < select:
        memo += t[i]
    if 1+i//2 == select:
        memo += t[i]
        ans = max(memo, ans)
    else:
        memo += t[i]
        memo -= t[start] 
        start += 2
        ans = max(memo, ans)


memo = 0

start=1
        
for i in range(n):
    if i%2==0:
        continue
    
    if 1+(i-1)//2 < select:
        memo += t[i]
    if 1+(i-1)//2 == select:
        memo += t[i]
        ans = max(memo, ans)
    else:
        memo += t[i]
        memo -= t[start] 
        start += 2
        ans = max(memo, ans)
print(ans)

Submission status: Wrong Answer

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

sums = 0
if N % 2 ==0:
  A1, A2 = 0, 0 
  for i in range(0, N - 1, 2):
    A1 += A[ i ] 
    A2 += A[ i + 1 ]
  sums = max( A1, A2 )
else:
  l1= []
  l2= []
  for i in range(0, N, 2):
    l1.append( A[ i ] )
    if i + 1 < len( A ):
      l2.append( A[ i + 1] )  
  print( l1, l2 )
  l1 = sorted( l1 )
  l2 = sorted( l2 )
  print( l1, l2 )
  sums = max( sum( l1[1:] ), sum( l2[1:] ) )
  print( l1[1:] ,l2 )
print( sums )