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:
    L1 = [0 for _ in range(N // 2 + 1)]
    L2 = [0 for _ in range(N // 2 + 1)]
    for i in range(N // 2):
        L1[i + 1] = L1[i] + A[i * 2]
        L2[N // 2 - 1 - i] = L2[N // 2 - i] + A[N - 1 - i * 2]
    res = 0
    for i in range(N // 2 + 1):
        res = max(res, L1[i] + L2[i])
else:
    NINF = -(10 ** 16)
    dp = [[NINF for j in range(3)] for i in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for i in range(N):
        if i - 2 >= 0:
            if dp[i - 2][0] != NINF:
                dp[i][0] = dp[i - 2][0] + A[i]
            if dp[i - 2][1] != NINF:
                dp[i][1] = dp[i - 2][1] + A[i]
            if dp[i - 2][2] != NINF:
                dp[i][2] = dp[i - 2][2] + A[i]
        if i - 3 >= 0:
            dp[i][1] = max(dp[i][1], dp[i - 3][0] + A[i])
            dp[i][2] = max(dp[i][2], dp[i - 3][1] + A[i])
        if i - 4 >= 0:
            dp[i][2] = max(dp[i][2], dp[i - 4][0] + A[i])

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

Submission status: Wrong Answer

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

if(n <= 3):
    print(max(a))
    exit()

left = [0] * (n+1)
right = [0] * (n+1)

left[1] = a[0]
left[2] = max(a[0],a[1])
for i in range(3,n+1):
    if(i%2==0):
        left[i]  = max(left[i-3] + max(a[i-2], a[i-1]),
                        left[i-2] + a[i-1])
    else:
        left[i] = left[i-2] + a[i-1]

right[-2] = a[-1]
right[-3] = max(a[-1],a[-2])
for i in range(n-3,-1,-1):
    if((n-i)%2==0):
        right[i]  = max(right[i+3] + max(a[i+1], a[i]),
                        right[i+2] + a[i])
    else:
        right[i] = right[i+2] + a[i]

ans = 0
for i in range(1,(n//2)+1):
    ans = max(ans, left[i] + right[i+2])

if(n%2==0):
    print(left[-1])
else:
    print(ans)

Submission status: Wrong Answer

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

INF = 10**17

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

dp = [[-INF]*3 for _ in range(N)]

for i, a in enumerate(A):
    if i == 0:
        dp[i][2] = a
    elif i == 1:
        dp[i][0] = max(a, dp[i-1][1])
    elif i == 2:
        dp[i][1] = a
        dp[i][2] = dp[0][2] + a
    elif (i+1)%2 == 0:
        dp[i][0] = max(dp[i-3][2], dp[i-2][0]) + a
    else:
        dp[i][1] = max([dp[i-4][2], dp[i-3][0], dp[i-2][1]]) + a
        dp[i][2] = dp[i-2][2] + a

if N%2 == 0:
    ans = dp[N-1][0]
else:
    ans = dp[N-1][1]
    # tmp = 0
    # for i in reversed(range(N)):
    #     if i%2 == 0 and i >= 2:
    #         tmp += A[i]
    #         ans = max(ans, dp[i-2][1]+tmp)

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
DP = [[-1e11 for _ in range(N)] for _ in range(N//2)]

for i in range(N//2):
    for j in range(N):
        if i == 0:
            DP[i][j] = A[j]
        elif j > i*2 and (N-i-1)*2 > j:
            DP[i][j] = A[j] + max(DP[i-1][:j-1])
print(DP[-1][-1])

Submission status: Wrong Answer

Solution code:
import math
n=int(input())
mi=int(math.floor(n/2))
li=sorted(list(map(int,input().split())),reverse=True)
ss=li[0:mi*2:2]
print(sum(ss))

Submission status: Wrong Answer

Solution code:
import numpy as np
num = int(input())
arr = np.array([int(i ) for i in input().split()], dtype='int64')
sortet_arr = np.sort(arr)[::-1]
idx_arr = np.argsort(arr)[::-1]
ans = 0
counta = 0
tmp = None
half = num // 2
for item, idx in zip(sortet_arr, idx_arr):
    if tmp != idx + 1 or tmp != idx - 1:
        ans += item
        tmp = idx
        counta += 1
        if counta >= half:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
i = int(input())
num = list(map(int,input().split()))
ans = []
for n in range(max(num),-1,-2):
	ans.append(n)
if len(ans) == int(len(num)/2):
	print(sum(ans))
else:
	print(suｍ(ans[-1:]))

Submission status: Wrong Answer

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

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

ans = 0
if n % 2 == 0:
    D = [[0,0] for i in range(n//2)]
    D[0][0] = A[0]
    D[0][1] = A[1]
    for i in range(1, n//2):
        D[i][0] = D[i-1][0] + A[i*2]
        D[i][1] = max(D[i-1][0],D[i-1][1]) + A[i*2+1]
    print(max(D[-1]))

else:

    

    D = [[0,0] for i in range(n//2)]
    D[0][0] = A[0]
    D[0][1] = A[1]
    for i in range(1, n//2):
        D[i][0] = D[i-1][0] + A[i*2]
        D[i][1] = max(D[i-1][0],D[i-1][1]) + A[i*2+1]


    S = [0] * n
    S[0] = A[0]
    S[1] = A[1]
    for i in range(2, n):
        S[i] = A[i] + S[i-2]
    

    for i in range(0, n-2, 2):
        le = max(D[i//2-1]) if i>0 else 0
        ri = S[-1] - S[i]
        # print(i,le,ri)
        ans = max(ans, le+ri)

    A = A[::-1]

    D = [[0,0] for i in range(n//2)]
    D[0][0] = A[0]
    D[0][1] = A[1]
    for i in range(1, n//2):
        D[i][0] = D[i-1][0] + A[i*2]
        D[i][1] = max(D[i-1][0],D[i-1][1]) + A[i*2+1]


    S = [0] * n
    S[0] = A[0]
    S[1] = A[1]
    for i in range(2, n):
        S[i] = A[i] + S[i-2]
    

    for i in range(0, n-2, 2):
        le = max(D[i//2-1]) if i>0 else 0
        ri = S[-1] - S[i]
        ans = max(ans, le+ri)

    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
al = []
g = []
k = []
g0 = 0
k0 = 0
for i in range(n):
    if i % 2 == 0:
        k0 += a[i]
        k.append(k0)
    else:
        g0 += a[i]
        g.append(g0)
if n % 2 == 0:
    al.append(g[n//2-1])
    al.append(k[n//2-1])
else:
    #print(g,k)
    al.append(g[-1])
    d = a[1]
    for i in range(n):
        if i % 2 == 0:
            al.append(k[-1]-a[i])
        else:
            now = (i-1)//2
            if i > 1 and i < n-2:
                #print(g[-1]-g[now],k[-1]-k[now+1],g[now-1],k[now-1],a[i])
                al.append(max(g[-1]-g[now],k[-1]-k[now+1])+max(d,k[now-1])+a[i])
                d = max(d+a[i],k[now-1]+a[i])
            elif i == 1:
                al.append(a[i]+max(g[-1]-g[now],k[-1]-k[now+1]))
            else:
                al.append(a[i] + max(g[now-1],k[now-1]))
#print(al)
print(max(al))

Submission status: Wrong Answer

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

lis_0 = A[::2]
lis_1 = A[1::2]
if N%2 == 0:
  print(max(sum(lis_0), sum(lis_1)))
else:
  rui_0 = [lis_0[0] for _ in range(len(lis_0))]
  rui_1 = [lis_1[0] for _ in range(len(lis_1))]
  for i in range(1, len(lis_1)):
    rui_0[i] = rui_0[i-1] + lis_0[i]
    rui_1[i] = rui_1[i-1] + lis_1[i]
  rui_0[-1] = rui_0[-2] + lis_0[-1]
  last1 = rui_1[-1]
  last0 = rui_0[-1]
  print(rui_0)
  print(rui_1)
  num = 0
  for j in range(1, len(rui_1)+1):
    for k in range(j+1, len(rui_1)+1):
      if k==len(rui_1):
        x = rui_0[j-1]+last1-rui_1[j-1]
      else:
        x = rui_0[j-1]+rui_1[k-1]-rui_1[j-1]+last0-rui_0[k]
      if num < x:
      	num = x
  print(max(sum(lis_1), sum(lis_0)-lis_0[0], sum(lis_0)-lis_0[-1], num))

Submission status: Wrong Answer

Solution code:
from itertools import accumulate,chain


def solve(A):
    N = len(A)
    oddacc = tuple(chain((0,),accumulate(A[1::2])))
    evenacc = tuple(chain((0,),accumulate(A[::2])))
    if N%2==0:
        return max(oddacc[i]+evenacc[-1]-evenacc[i] for i in range(N//2+1))

    # one 3 space
    res = max(oddacc[-1]-A[i*2+1] for i in range(N//2))
    # two 2 space
    def it():
        m = 0
        for i in reversed(range(N//2)):
            m = max(m+A[i*2+1], A[i*2+1]+evenacc[-1]-evenacc[i+2])
            yield m+evenacc[i]
    res = max(max(it()), res)
    return res

if __name__ == '__main__':
    N = map(int,input().split())
    A = tuple(map(int,input().split()))
    print(solve(A))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
if N % 2 == 0:
    L1 = [0 for _ in range(N // 2 + 1)]
    L2 = [0 for _ in range(N // 2 + 1)]
    for i in range(N // 2):
        L1[i + 1] = L1[i] + A[i * 2]
        L2[N // 2 - 1 - i] = L2[N // 2 - i] + A[N - 1 - i * 2]
    res = 0
    for i in range(N // 2 + 1):
        res = max(res, L1[i] + L2[i])
else:
    NINF = -(10 ** 15)
    dp = [[NINF for j in range(3)] for i in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for i in range(N):
        if i - 2 >= 0:
            if dp[i - 2][0] != NINF:
                dp[i][0] = dp[i - 2][0] + A[i]
            if dp[i - 2][1] != NINF:
                dp[i][1] = dp[i - 2][1] + A[i]
            if dp[i - 2][2] != NINF:
                dp[i][2] = dp[i - 2][2] + A[i]
        if i - 3 >= 0:
            dp[i][1] = max(dp[i][1], dp[i - 3][0] + A[i])
            dp[i][2] = max(dp[i][2], dp[i - 3][1] + A[i])
        if i - 4 >= 0:
            dp[i][2] = max(dp[i][2], dp[i - 4][0] + A[i])

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

Submission status: Wrong Answer

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

if(n <= 3):
    print(max(a))
    exit()

left = [0] * (n+1)
right = [0] * (n+1)

left[1] = a[0]
left[2] = max(a[0],a[1])
for i in range(3,n+1):
    if(i%2==0):
        left[i]  = max(left[i-3] + max(a[i-2], a[i-1]),
                        left[i-2] + a[i-1])
    else:
        left[i] = left[i-2] + a[i-1]

right[-2] = a[-1]
for i in range(n-3,-1,-1):
    if((n-i)%2==0):
        right[i]  = max(right[i+3] + max(a[i+1], a[i]),
                        right[i+2] + a[i])
    else:
        right[i] = right[i+2] + a[i]

ans = 0
for i in range(1,(n//2)+1):
    ans = max(ans, left[i] + right[i+2])

if(n%2==0):
    print(left[-1])
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
DP = [[-1e10 for _ in range(N)] for _ in range(N//2)]

for i in range(N//2):
    for j in range(N):
        if i == 0:
            DP[i][j] = A[j]
        elif j > i*2:
            DP[i][j] = A[j] + max(DP[i-1][:j-1])
print(DP[-1][-1])

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    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]
        ans = max(ans1,ans2)
    
    else:
        cuml = [0] * (n + 1)
        cumr = [0] * (n + 1)
        cumr2 = [0] * (n + 1)

        for i in range(n):
            if i == 0:
                cuml[i + 1] = a[i]
            else:
                cuml[i + 1] = cuml[i - 1] + a[i]
        
        for i in range(n - 1,-1,-1):
            if i == n - 1:
                cumr[i] = a[i]
                cumr2[i] = a[i]
            else:
                cumr[i] = cumr[i + 2] + a[i]
                if i%2 == 1:
                    if i == n - 2:
                        continue
                    else:
                        cumr2[i] = max(cumr2[i + 2],cumr[i + 3]) + a[i]
        
        tmp = 0
        ans = 0
        for i in range(n - 1):
            if i%2 == 1:
                tmp += a[i]
            ans = max(ans,cuml[i] + cumr[i + 2])
            if i <= n - 5 and i%2 == 1:
                ans = max(ans,cuml[i] + cumr2[i + 2])
            if 1 <= i <= n - 5 and i%2 == 1:
                ans = max(ans,cuml[i] + cumr[i + 3])
    
        ans = max(ans,tmp)
    print(ans)

if __name__ =='__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
l=list(map(int,input().rstrip().split()))
L=[]
k=[]
x=0
for i in range(n-1,-1,-2):
    L.append(l[i])
for j in range(n-2,-1,-2):
    k.append(l[j])
if(sum(L)>=sum(k)):
    if(len(L)!=n//2):
        L.remove(min(L))
    print(sum(L))
if(sum(k)>sum(L)):
    if(len(k)!=n//2):
        k.remove(min(k))
    print(sum(k))

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    if n % 2 == 0:
        print(max(sum(a[::2]), sum(a[1::2])))
        return
    dp = [[[-10**15]*3, [-10**15]*3] for _ in [0]*(n+1)]
    dp[0][0][0] = 0
    for i in range(n):
        # 使う場合
        dp[i+1][1][0] = max(dp[i+1][1][0], dp[i][0][0]+a[i])
        dp[i+1][1][1] = max(dp[i+1][1][1], dp[i][0][1]+a[i])
        dp[i+1][1][2] = max(dp[i+1][1][2], dp[i][0][2]+a[i])
        # 使わない場合
        dp[i+1][0][1] = max(dp[i+1][0][1], dp[i][0][0])
        dp[i+1][0][2] = max(dp[i+1][0][2], dp[i][0][1])
        # 更新
        dp[i+1][0][0] = max(dp[i+1][0][0], dp[i][1][0])
        dp[i+1][0][1] = max(dp[i+1][0][1], dp[i][1][1])
        dp[i+1][0][2] = max(dp[i+1][0][2], dp[i][1][2])
    print(max(dp[n][0][2], dp[n][1][2]))


main()

Submission status: Wrong Answer

Solution code:
def examA():
    N = SI()
    ans = "No"
    for s in N:
        if s=="7":
            ans = "Yes"
    print(ans)
    return

def examB():
    N = I()
    ans = 0
    for i in range(1,N+1):
        if i%3==0:
            continue
        if i%5==0:
            continue
        ans += i
    print(ans)
    return

def examC():
    def gcd(x, y):
        if y == 0:
            return x
        while (y != 0):
            x, y = y, x % y
        return x
    K = I()
    ans = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            cur = gcd(i,j)
            for k in range(1,K+1):
                ans += gcd(cur,k)
    print(ans)
    return

def examD():
    N = I()
    S = SI()
    R = [0]*(N+1)
    G = [0]*(N+1)
    B = [0]*(N+1)
    for i in range(N):
        s = S[i]
        R[i+1] += R[i]
        G[i+1] += G[i]
        B[i+1] += B[i]
        if s=="R":
            R[i+1] += 1
        elif s=="G":
            G[i+1] += 1
        elif s=="B":
            B[i+1] += 1
    ans = 0
    for l in range(N):
        Ls = S[l]
        for r in range(l+3,N):
            Rs = S[r]
            if (Ls=="R" and Rs=="B") or (Ls=="B" and Rs=="R"):
                ans += G[r] - G[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="G":
                        ans -= 1
            elif (Ls=="R" and Rs=="G") or (Ls=="G" and Rs=="R"):
                ans += B[r] - B[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="B":
                        ans -= 1
            elif (Ls=="G" and Rs=="B") or (Ls=="B" and Rs=="G"):
                ans += R[r] - R[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="R":
                        ans -= 1
    print(ans)
    return

def examE():
    N, K = LI()

    ans = 0
    print(ans)
    return

def examF():
    N = I()
    A = LI()

    if N%2==0:
        O = [0] * N
        E = [0] * N
        for i in range(N):
            O[i] += O[i - 1]
            E[i] += E[i - 1]
            if i % 2 == 0:
                O[i] += A[i]
            else:
                E[i] += A[i]
        #print(O,E)
        ans = max(O[-1],E[-1])
        print(ans)
        return

    def dfs(n,k):
        if (n+2)//2 <k:
            return -inf
        if k == 0:
            return 0
        if n==0:
            if k==1:
                return A[0]
            return -inf
        if n==1:
            if k==1:
                return max(A[0],A[1])
            return -inf
        res = max(A[n]+dfs(n-2,k-1),dfs(n-1,k))
        return res

    ans = dfs(N-1,N//2)
    #print(dfs(4,2))
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Wrong Answer

Solution code:
N = int(input())
A = input().split()
for i in range(N):
    A[i] = int(A[i])
A.sort(reverse=True)
x = 0
for j in range(int(N/2)):
    x += A[j*2]
print(x)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
odd = list(accumulate([0] + A[::2]))
even = list(accumulate([0] + A[::-1][::2]))
ans = max(odd[i] + even[N//2-i] for i in range(N//2))
if N % 2 == 1:
    dp = [0] * (N//2+1)
    for i in range(0, N-1, 2):
        dp[i//2+1] = max(odd[i//2+1], dp[i//2] + A[i+1])
    ans2 = max(dp[i] + even[N//2-i] for i in range(N//2))
    ans = max(ans, ans2)
print(ans)

Submission status: Wrong Answer

Solution code:
#!python3

INF = -(10 ** 15)

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


def main():
    if N % 2 == 0:
        a = sum([A[i] for i in range(0, N, 2)])
        b = sum([A[i + 1] for i in range(0, N, 2)])
        ans = max(a, b)
        print(ans)
        return
    dp = [[INF] * 3 for _ in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][0] = A[0] + A[2]
    dp[2][2] = A[2]
    
    for i in range(3, N):
        dp[i][0] = dp[i - 2][0] + A[i]
        dp[i][1] = max(dp[i - 2][1] + A[i], dp[i - 3][0] + A[i])
        if i > 3:
            a = dp[i - 2][2] + A[i]
            b = dp[i - 3][1] + A[i]
            c = dp[i - 4][0] + A[i]
            dp[i][2] = max(a, b, c)
    
    ans = max(dp[-1][2], dp[-2][1], dp[-3][0])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
an = list(map(int, input().split(" ")))
if n == 2:
    print(max(an))
elif n % 2 == 1:
    a = 0
    b = 0
    c = 0
    for i in range(0, n // 2):
        a += an[i]
        b += an[i + 1]
        c += an[i + 2]
    print(max(a, b, c))
else:
    a = 0
    b = 0
    for i in range(0, n // 2):
        a += an[i * 2]
        b += an[i * 2 + 1]
    print(max(a, b))

Submission status: Wrong Answer

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

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

else:
  ans=sum(A[::2])-A[N-1]
  a=sum(A[::2])-A[N-1]
  c=sum(A[2::2])
  for j in range(N//2):
    a=a-A[N-j*2-3]+A[N-j*2-2]
    c=c-A[j*2+2]+A[2*j+1]
    ans=max(ans,c)
    ans=max(ans,a)
    #print(c)
  #print(sum(A[::2])-A[N-1])
  #print(sum(A[1::2])
  b=sum(A[::2])-min(A[::2])#3つあき
  print(max(max(ans,b),c))

Submission status: Wrong Answer

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

INF = 10 ** 15
dp = [[-INF] * N for _ in range(3)]
dp[0][0] = As[0]
dp[0][1] = As[0]
dp[1][1] = As[1]

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


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

Submission status: Wrong Answer

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

s=0
for i in range(len(A)):
    s+=int(A[i])

ss=0
for i in range(int(len(A)//2)):
    ss+=int(A[2*i])

print(max(ss,s-ss))

Submission status: Wrong Answer

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

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

ans = 0
if n % 2 == 0:
    D = [[0,0] for i in range(n//2)]
    D[0][0] = A[0]
    D[0][1] = A[1]
    for i in range(1, n//2):
        D[i][0] = D[i-1][0] + A[i*2]
        D[i][1] = max(D[i-1][0],D[i-1][1]) + A[i*2+1]
    print(max(D[-1]))

else:

    

    D = [[0,0] for i in range(n//2)]
    D[0][0] = A[0]
    D[0][1] = A[1]
    for i in range(1, n//2):
        D[i][0] = D[i-1][0] + A[i*2]
        D[i][1] = max(D[i-1][0],D[i-1][1]) + A[i*2+1]


    S = [0] * n
    S[0] = A[0]
    S[1] = A[1]
    for i in range(2, n):
        S[i] = A[i] + S[i-2]
    

    for i in range(0, n, 2):
        le = max(D[i//2-1]) if i>0 else 0
        ri = S[-1] - S[i]
        ans = max(ans, le+ri)

    A = A[::-1]

    D = [[0,0] for i in range(n//2)]
    D[0][0] = A[0]
    D[0][1] = A[1]
    for i in range(1, n//2):
        D[i][0] = D[i-1][0] + A[i*2]
        D[i][1] = max(D[i-1][0],D[i-1][1]) + A[i*2+1]


    S = [0] * n
    S[0] = A[0]
    S[1] = A[1]
    for i in range(2, n):
        S[i] = A[i] + S[i-2]
    

    for i in range(0, n, 2):
        le = max(D[i//2-1]) if i>0 else 0
        ri = S[-1] - S[i]
        ans = max(ans, le+ri)

    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
if n%2:
  m=float("-inf")
  for i in range(n-1):
    m=max(m,sum(a[j] if j<i else a[j+1] for j in range(0,n-1,2)))
    m=max(m,s-m)
  print(m)
else:
  m=sum(a[i] for i in range(0,n,2))
  print(max(m,s-m))

Submission status: Wrong Answer

Solution code:
k=int(input())
l=list(map(int,input().split()))
odd=0
even=0
ct=0
c=0
le=[]
lo=[]
odd_mn=-1000000001
odd_mn1=-1000000001
even_mn=-1000000001
even_mn=-1000000001
for i in range(k):
  if i%2==0:
    if l[i]>=0:
      c+=1
      even+=l[i]
    if l[i]>even_mn and l[i]<0:
      even_mn=l[i]
      ind=i
    le.append(l[i])
  else:
    if l[i]>=0:
      odd+=l[i]
      ct+=1
    if l[i]>odd_mn and l[i]<0:
      odd_mn=l[i]
      ino=i
    lo.append(l[i])
if c==1:
  even+=even_mn
if ct==1:
  odd+=odd_mn
if c==0:
  even+=even_mn
  even_mn=-1000000001
  for i in range(len(le)):
    if l[i]>even_mn and ind!=i//2:
      even_mn=l[i]
  even+=even_mn
if ct==0:
  odd+=odd_mn
  odd_mn=-1000000001
  for i in range(len(lo)):
    if l[i]>odd_mn and ino!=(i//2+1):
      odd_mn=l[i]
  odd+=odd_mn

if odd>even:
  print(odd)
else:
  print(even)

Submission status: Wrong Answer

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

ele = n//2

if n%2==0:
    totsum1 = 0
    totsum2 = 0
    count = 0
    for i in range(0, n, 2):
        totsum1 += lst[i]
        totsum2 += lst[i+1]

        count += 1
        if count == ele:
            break
    print(max(totsum1, totsum2))
    
else:
    lst = [(i, num) for i, num in enumerate(lst)]
    lst = sorted(lst, key = lambda x: x[1], reverse=True)

    totsum = lst[0][1]
    indices = [lst[0][0]]

    for num in lst[1:]:
        if all((num[0]>i+1 or num[0]<i-1) for i in indices):
            indices.append(num[0])
            totsum += num[1]
        if len(indices) == ele:
            break

    print(totsum)

Submission status: Wrong Answer

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

le, lo, re, ro = [0], [0], [0], [0]

for i in range(n):
    if i % 2 == 0:
        le.append(le[-1] + a[i])
    else:
        lo.append(lo[-1] + a[i])

for i in range(n-1, -1, -1):
    if i % 2 == 0:
        re.append(re[-1] + a[i])
    else:
        ro.append(ro[-1] + a[i])

if n % 2 == 0:
    n //= 2
    ans = lo[n]
    for i in range(0, n + 1):
        ans = max(ans, le[i] + ro[n-i])

    print(ans)

else:
    n //= 2
    ans = 0
    for i in range(0, n+1):
        ans = max(ans, le[i] + ro[n-i])
        ans = max(ans, lo[i] + re[n-i])
        ans = max(ans, le[i] + re[n-i])
        if n-i >= 1:
            ans = max(ans, le[i] + ro[n-i] + re[1] - ro[1])
        if i > 0:
            ans = max(ans, lo[i] + re[n-i] + le[1] - lo[1])
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
dp = [[[-10**15, -10**15] for i in range(3)] for j in range(n+1)]

dp[0][0][0] = 0


for i in range(n):
    for j in range(3):
        for k in range(2):
            if j == 2:
                dp[i+1][2][0] = max(dp[i][2][1],dp[i+1][2][0])
                dp[i+1][2][1] = max(dp[i][2][0]+a[i],dp[i+1][2][1])
            elif j == 1:
                dp[i+1][1][0] = max(dp[i][1][1],dp[i+1][1][0])
                dp[i+1][1][1] = max(dp[i][1][0]+a[i],dp[i+1][1][1])
                dp[i+1][2][0] = max(dp[i][1][0],dp[i+1][2][0])
            else:
                dp[i+1][0][0] = max(dp[i][0][1],dp[i+1][0][0])
                dp[i+1][0][1] = max(dp[i][0][0]+a[i],dp[i+1][0][1])
                dp[i+1][1][0] = max(dp[i][0][0],dp[i+1][1][0])


ans = 0
if n % 2 == 0:
    for i in range(2):
        ans = max(dp[n][i])
else:
    for i in range(3):
        ans = max(dp[n][i])
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    a = LI()
    if n == 3:
        print(max(a))
        return
    dp = [[0] * 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]) + a[i]
        dp[i][2] = max(dp[i - 2][2], dp[i - 3][1]) + a[i]
    if n & 1:
        print(max(dp[-3][0], dp[-1][1], dp[-1][2]))
    else:
        print(max(dp[-1]))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())

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

S = [0]*N
S[0] = A[0]
S[1] = A[1]

for i in range(2,N):
    S[i] = S[i-2] + A[i]

if N%2 == 0:
    print(max(S[-1],S[-2]))
else:
    M = A[0]
    for i in range(1,N//2+1):
        M = min(M,A[2*i])

    mss = - M
    s = A[0]
    for i in range(N//2):
        s += A[2*i+1] - A[2*i+2]
        if s < 0:
            s = - A[2*i+2]
        elif mss < s:
            mss = s
        #print(i,mss)
    
    print(max(S[-1]+mss,S[-2]))

###
#print(S)
#print(M)
###

Submission status: Wrong Answer

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

odd = [0] * (N + 1)
odd_tmp = 0
for i in range(N):
    if i % 2 == 0: odd_tmp += A[i]
    odd[i + 1] = odd_tmp

evn = [0] * (N + 1)
evn_tmp = 0
for i_inv in range(N):
    i = N - 1 - i_inv
    if i % 2 == 1: evn_tmp += A[i]
    evn[i_inv + 1] = evn_tmp

ans = 0
for i in range(N + 1):
    if i % 2 == 1: continue
    ans_tmp = odd[i] + evn[-1 - i]
    # print("#", i, odd[i], evn[-1 - i], ans_tmp)
    ans = max(ans, ans_tmp)

print(ans)

Submission status: Wrong Answer

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

INF = 10 ** 15
dp = [[-INF] * N for _ in range(3)]
dp[0][0] = As[0]
dp[1][0] = As[0]
dp[0][1] = As[0]
dp[1][1] = As[1]

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
s_odd = []
s_eve = []
s_odd_a = []
s_eve_a = []
if n % 2 == 0:
    for i in range(0, n // 2):
        s_odd.append(a[i * 2])
        s_eve.append(a[i * 2 + 1])
    print(max(sum(s_odd), sum(s_eve)))
else:
    for i in range(0, n // 2):
        s_odd.append(a[i * 2])
        s_eve.append(a[i * 2 + 1])
        s_odd_a.append(a[(i + 1) * 2])
    print(max(sum(s_odd), sum(s_eve), sum(s_odd_a)))

Submission status: Wrong Answer

Solution code:
n = int(input())
k = int(2 * pow(10,5))
if 2 <= n <= k:
    A = list(map(int, input().split()))
    c = 0
    S = 0
    for i in range(n-1, -1, -2):
        if c == n//2:
            break
        else:
            S += A[i]
            c += 1
    print(S)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
preone,petw,res=0,0,0
for i in range(len(a)):
    if i==0:
        res=a[0]
    elif i==1:
        res=max(a[0],a[1])
    else:
        res=max(preone,a[i]+petw)
        
    petw = preone
    preone =res
print(res)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
a1 = sum(A[0::2])
a2 = sum(A[1::2])
a3 = sum(A[0+N//2::2])
a4 = sum(A[1+N//2::2])
a_lis = [a1,a2,a3,a4]
print(max(a_lis))

Submission status: Wrong Answer

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

INF = 10 ** 15
dp = [[-INF] * N for _ in range(3)]
dp[0][0] = As[0]
dp[1][0] = As[0]
dp[0][1] = As[0]
dp[1][1] = As[1]

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

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**18

n = int(input())
a = [int(item) for item in input().split()]


# dp[i-th][wait num][used / not used]
dp = [[[-100000] * 2 for _ in range(3)] for _ in range(n+1)]
dp[0][0][0] = 0

for i in range(n):
    # use in i
    for j in range(3):
        dp[i+1][j][1] = dp[i][j][0] + a[i]
    # rest in i
    for j in range(2):
        dp[i+1][j+1][0] = dp[i][j][0]
    # not use in i
    for j in range(3):
        dp[i+1][j][0] = max(dp[i][j][1], dp[i+1][j][0])

ans = -INF
if n % 2 == 0:
    ans = max(dp[-1][1][1], ans)
    ans = max(dp[-1][0][0], ans)
else:
    ans = max(dp[-1][2][1], ans)
    ans = max(dp[-1][1][0], ans)
print(ans)