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:
    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]=max(A[0],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][0]=dp[1][0]+A[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())
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]=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]=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]=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]=dp[i-2][1]

        test2=dp[N-1][0]

        print(max(test1,test2))

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

if N % 2 == 0:
    even = A[::2]
    odd = A[1::2]
    assert len(even) == len(odd) == N // 2
    print(max(sum(even), sum(odd)))
    exit()


@lru_cache(maxsize=None)
def dp(i, numSkips):
    # Returns the best sum taking A[i] and allowing numSkips of changes in stride
    if numSkips < 0:
        return float("-inf")
    if i < 0:
        if numSkips == 2:
            return float("-inf")
        return 0
    best = A[i] + max(dp(i - 2 - skip, numSkips - skip) for skip in range(numSkips + 1))
    return best


# Warm cache
for i in range(N):
    dp(i, 0)
    dp(i, 1)
    dp(i, 2)

print(max(dp(N - 1, 2), dp(N - 2, 1), dp(N - 3, 0)))

Submission status: Wrong Answer

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



if n % 2 == 0:
    tp = sum(arr[::2])
    print(max(sum(arr)-tp,tp))
else:
    hoge = -(10**12)
    buf = [[hoge for i in range(3)] for j in range(n)]
    buf[0][0] = arr[0]
    buf[1][1] = arr[1]
    buf[2][2] = arr[2]
    buf[2][0] = arr[0]+arr[2]

    for i in range(3,n):
        buf[i][0] = buf[i-2][0] + arr[i]
        buf[i][1] = max(buf[i-3][0] + arr[i],buf[i-2][1]+arr[i])
        if i >= 4:
            buf[i][2] = max([buf[i-3][1] + arr[i],buf[i-4][0] + arr[i],buf[i-2][2]+arr[i]])
        else:
            buf[i][2] = max([buf[i-3][1] + arr[i],buf[i-2][2]+arr[i]])

    # print(buf)
    # for l in buf:
    #     print(l)
    print(max(buf[-1][2],buf[-2][1],buf[-3][0]))

Submission status: Wrong Answer

Solution code:
def even(N, A):
    dis = list()
    total_A_odd = 0
    for i in range(N):
        if i % 2 == 0:
            dis.append(A[i+1] - A[i])
            total_A_odd += A[i]

    M = len(dis)
    ruikeiwa = list()
    for j in range(M-1, -1, -1):
        if j == M-1:
            ruikeiwa.append(dis[j])
        else:
            ruikeiwa.append(ruikeiwa[-1]+dis[j])
    
    # print("dis = ",dis)
    # print("ruikeiwa= ", ruikeiwa)
    return max(ruikeiwa)+total_A_odd
    


N = int(input())

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

if N % 2 == 0:
    print(even(N ,A))
else:
    A1 = [0]*(N-1)
    for i in range(N-1):
        A1[i] = A[i]
    # print("1", A1)

    A2 = [0]*(N-1)
    for i in range(N-1):
        A2[i] = A[i+1]
    # print("2", A2)

    A3 = [0]*(N-1)
    for i in range(N):
        if i == 0:
            A3[0] = A[0]
        if i > 1:
            A3[i-1] = A[i]
    # print("3", A3)

    ans_A1 = even(N-1, A1)
    ans_A2 = even(N-1, A2)
    ans_A3 = even(N-1, A3)
    
    print(max(ans_A1, ans_A2, ans_A3))

Submission status: Wrong Answer

Solution code:
# dpでいけそう
n = int(input())
a = list(map(int, input().split()))
INF = 10**16

ans = -INF

a = [0, 0, 0, 0] + a
dp = [[-INF for _ in range(n+4)] for _ in range(3)]
dp[0][3] = 0
dp[0][2] = 0
for i in range(4, len(a)):
    dp[2][i] = max(dp[2][i], dp[1][i-3] + a[i], dp[0][i-4] + a[i], dp[2][i-2] + a[i])
    dp[1][i] = max(dp[1][i], dp[0][i-3] + a[i], dp[1][i-2] + a[i])
    dp[0][i] = max(dp[0][i], dp[0][i-2] + a[i])
ans = max(ans, max(dp[0][-3:-2]))
ans = max(ans, dp[1][n+1])
ans = max(ans, dp[2][n+2])

print(ans)

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

Submission status: Wrong Answer

Solution code:
from math import gcd

############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input().rstrip()))
def inlt():
    return(list(map(int,input().rstrip().split())))
def insr():
    s = input().rstrip()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().rstrip().split()))
################################################################
n = inp()
nums = [0] + inlt()
dp = [0 for i in range(n + 1)]
s = [0 for i in range(n + 1)]
s[1] = nums[1]
for i in range(3,n,2):
    s[i] = s[i - 2] + nums[i]
if n == 1:
    print(nums[0])
elif n == 2:
    print(max(nums[0],nums[1]))
elif n == 3:
    print(nums[0] + nums[1])
elif n == 4:
    print(max(nums[0] + nums[2],nums[0] + nums[3],nums[1] + nums[3]))
else:
    dp[1] = nums[1]
    dp[2] = max(nums[1],nums[2])
    dp[3] = max(nums[3],nums[1],nums[2])
    dp[4] = max(nums[1] + nums[3],nums[1] + nums[4],nums[2] + nums[4])
    for i in range(5,n + 1):
        if i % 2 == 0:
            dp[i] = max(dp[i - 2] + nums[i], s[i - 1]) #if n % 2 == 0 take sum else dp[i - 1]
        else:
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
    print(dp[n])
#print('No')
#print()

Submission status: Wrong Answer

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

dp = [0]*N

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

    if i%2==1:
        dp[i] = max(dp[i-2]+A[i],cum)

ans = dp[-1]


print(ans)
#print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
from functools import lru_cache

(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

if N % 2 == 0:
    even = A[::2]
    odd = A[1::2]
    assert len(even) == len(odd) == N // 2
    print(max(sum(even), sum(odd)))
    exit()


@lru_cache(maxsize=None)
def dp(i, numSkips):
    if numSkips < 0:
        return float("-inf")
    if i < 0:
        return 0
    best = A[i] + max(
        dp(i - 2, numSkips), dp(i - 3, numSkips - 1), dp(i - 4, numSkips - 2)
    )
    return best


# Warm cache
for i in range(N):
    dp(i, 0)
    dp(i, 1)
    dp(i, 2)

print(max(dp(N - 1, 2), dp(N - 2, 1), dp(N - 3, 0)))

Submission status: Wrong Answer

Solution code:


n = 0
a = []

def format_input(filename = None):
	global n
	global a
	if filename == None:
		n = int(input())
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 2 * 10**5)
		a = [rng(-1 * 10**9, 10**9) for i in range(n)]
		print(n)
		print(' '.join(list(map(str, a))))

def get_answer():
	odd = [0]
	even = [0]
	for i in range(n // 2):
		odd.append(odd[-1] + a[2*i])
		even.append(even[-1] + a[2*i+1])
	if n % 2 == 1:
		odd.append(odd[-1] + a[-1])

	print(odd)
	print(even)
	answer = -1 * 10**9 * n
	if n % 2 == 0:
		for i in range(n // 2 + 1):
			answer = max(answer, odd[i] - even[i] + even[-1])
	else:
		for i in range(n // 2 + 2):
			if i < n // 2 + 1:
				for j in range(i+1):
					answer = max(answer, odd[j] - even[j] + even[i] - odd[i+1] + odd[-1])
			else:
				for j in range(i):
					answer = max(answer, odd[j] - even[j] + even[-1])
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Wrong Answer

Solution code:
s = [input() for i in range(2)]
s[1]=s[1].split(" ")
n=0
j=0
count=0
for k in s[1]:
  m = int(k)
  if count%2 == 0:
    j+=m
  if count%2 != 0:
    n+=m
  count+=1
if n<j:
	print(j)
else:
	print(n)

Submission status: Wrong Answer

Solution code:
# dpでいけそう
n = int(input())
a = list(map(int, input().split()))
INF = 10**16

ans = -INF

a = [0, 0, 0, 0] + a
dp = [[-INF for _ in range(n+4)] for _ in range(3)]
dp[0][3] = 0
dp[0][2] = 0
for i in range(4, len(a)):
    dp[2][i] = max(dp[2][i], dp[1][i-3] + a[i], dp[0][i-4] + a[i], dp[2][i-2] + a[i])
    dp[1][i] = max(dp[1][i], dp[0][i-3] + a[i], dp[1][i-2] + a[i])
    dp[0][i] = max(dp[0][i], dp[0][i-2] + a[i])
ans = max(ans, max(dp[0][-3:-2]))
ans = max(ans, dp[1][-2])
ans = max(ans, dp[2][-1])

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]-acum1[0])+(acum2[-1]-acum2[i+3])
      ans=max(ans,tmp)
    print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
n=N//2
A=list(map(int,input().split()))
e=[]
es=0
o=[]
os=0
miniodd=1000000000
for p in range(N):
  if p%2==0:
    e.append(A[p])
    es+=A[p]
  else:
    o.append(A[p])
    os+=A[p]
    if miniodd>A[p]:
      miniodd=A[p]
if N%2==0:
  ans=max(es,os)
else:
  ma=0
  for i in range(N//2):
    a=0
    for j in range(i):
      a+=e[i]
    for h in range(N//2+1,N//2+1-i):
      a+=h[i]
    if ma<a:
      ma=a
  ans=max(ma,es,os-miniodd)
print(ans)

Submission status: Wrong Answer

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

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

if N==2:
  print(max(0,A[0],A[1]))
  exit()

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

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

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

print(max(a,b,c))

Submission status: Wrong Answer

Solution code:
n = int(input())

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

def num_left(pos):
	if pos % 2 == 0:
		return (n - pos) // 2 + 1
	else:
		return (n - pos - 1) // 2 + 1


if (n % 2) == 0:
	even = a[1::2]
	odd = a[0::2]

	print(max(sum(even), sum(odd)))

else: 
	d = [{} for i in range(n)]
	for i in range(n):

		if i < 2:
			d[i][0] = 0
			d[i][1] = a[i]

		else:			
			left = num_left(i + 2)
			#print("i = ", i, left)
			j = i - 2
			while j >= 0:
				max_count = max(d[j].keys())
				
				if max_count + left + 1	 < n // 2: 
					break

				else: 
					for count, v in d[j].items():
						#print(count, v)
						if count + left + 1 >= n // 2:
							if count + 1 in d[i]:
								d[i][count + 1] = max(d[i][count + 1], v + a[i])
							else:
								d[i][count + 1] = v + a[i]							
				j -= 1

			if 1 + left >= n // 2:
				d[i][0] = 0

	best = None
	for i in range(n):
		for count, result in d[i].items():
			if count == n // 2:
				if best is None:
					best = result
				else:
					best = max(best, result)

	#print(d)
	print(best)

Submission status: Wrong Answer

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

if len(A)%2==0:
    A1=sum(A[0::2])
    A2=sum(A[1::2])
    if(A1>A2):
        print(A1)
    else:
        print(A2)
else:
    B=[]
    for i in range(len(A)-1):
        B+=[sum((A[:i]+A[i+1:])[0::2])]
        B+=[sum((A[:i]+A[i+1:])[1::2])]
    print(max(B))

Submission status: Wrong Answer

Solution code:



def resolve():
    N = int(input())
    A= list(map(int,input().split()))
    if N % 2 ==0:
        x1 =sum(A[::2])
        x2 =sum(A[1::2])
        print(max(x1,x2))
        return

    inf = -float('inf')
    table = [[[inf,inf],[inf,inf],[inf,inf],[inf,inf]] for i in range(N)]

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

        if i % 2 == 0:

            table[i][1][1] = table[i-1][0][0]+v
            table[i][-1][0] = max(table[i-1][0])
            table[i][-1][1]= table[i-1][-2][0]+v

        else:
            table[i][-2][0] = max(table[i-1][-1])
            table[i][0][0] = max(table[i-1][1])
            table[i][0][1] = table[i-1][-1][0]+v



    print(max(table[-1][-1]))





if __name__ == "__main__":
    resolve()
    #unittest.main()

Submission status: Wrong Answer

Solution code:



def resolve():
    N = int(input())
    A= list(map(int,input().split()))
    if N % 2 ==0:
        x1 =sum(A[::2])
        x2 =sum(A[1::2])
        print(max(x1,x2))
        return

    inf = -float('inf')
    table = [[[inf,inf],[inf,inf],[inf,inf],[inf,inf]] for i in range(N)]

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

        if i % 2 == 0:

            table[i][1][1] = table[i-1][0][0]+v
            table[i][-1][0] = max(table[i-1][0])
            table[i][-1][1]= table[i-1][-2][0]+v

        else:
            table[i][-2][0] = max(table[i-1][-1])
            table[i][0][0] = max(table[i-1][1])
            table[i][0][1] = table[i-1][-1][0]+v


    for i in table:
        print(i)
    print(max(table[-1][-1]))





if __name__ == "__main__":
    resolve()
    #unittest.main()

Submission status: Wrong Answer

Solution code:
# dpでいけそう
n = int(input())
a = list(map(int, input().split()))
INF = 10**16

ans = -INF

a = [0, 0, 0, 0] + a
dp = [[-INF for _ in range(n+4)] for _ in range(3)]
dp[0][3] = 0
dp[0][2] = 0
for i in range(4, len(a)):
    dp[2][i] = max(dp[2][i], dp[1][i-3] + a[i], dp[0][i-4] + a[i], dp[2][i-2] + a[i])
    dp[1][i] = max(dp[1][i], dp[0][i-3] + a[i], dp[1][i-2] + a[i])
    dp[0][i] = max(dp[0][i], dp[0][i-2] + a[i])
ans = max(ans, max(dp[0][-3:-2]))
ans = max(ans, max(dp[1][-2:]))
ans = max(ans, dp[2][-1])

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
add = 0
sum_1=0
sum_2 =0
if n%2 == 0:
    a.sort()
    for i in range(1,n,2):
        add = add + a[i]
else :
    a.sort()
    for i in  range(1,n):
        if i %2 == 0:
            sum_1 = sum_1 + a[i]
        else:
            sum_2 = sum_2 + a[i]
print(max(sum_1,sum_2))

Submission status: Wrong Answer

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


ruiseki0 = [0] * (n + 10) 
for i in range(n):
    ruiseki0[i + 1] = ruiseki0[i]
    if i % 2 == 0:
        ruiseki0[i + 1] += a[i]
        
l = [0] * (n + 1)
for i in range(n + 1):
    l[i] = ruiseki0[i]
    if i % 2 == 0:
        if i == 0:
            l[i] = 0
        else:
            l[i] = max(l[i - 2] + a[i - 1], l[i])


a = a[::-1]
ruiseki0 = [0] * (n + 10) 
for i in range(n):
    ruiseki0[i + 1] = ruiseki0[i]
    if i % 2 == 0:
        ruiseki0[i + 1] += a[i]

r = [0] * (n + 1)
for i in range(n + 1):
    r[i] = ruiseki0[i]
    if i % 2 == 0:
        if i == 0:
            r[i] = 0
        else:
            r[i] = max(r[i - 2] + a[i - 1], r[i])
   
ans = - 10 ** 20
for i in range(n):
    if n - i - 2 < 0:
        break
    ans = max(ans, l[i] + r[n - i - 2])
    
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, ans)
if n % 2 == 1:
    ans = max(ans, sum(a)- ruiseki0[n])
print(ans)

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))
if(n%2==0):
    answera=0
    answerb=0
    for i in range(int(n/2)):
        answera+=a[2*i]
        answerb+=a[2*i+1]
    print(max(answera, answerb))
else:
    ff=0
    fb=0
    bf=0
    bb=0
    for i in range(int(n/2)-1):
        bf+=a[3+2*i]
        bb+=a[4+2*i]
    answerb=max(bb,bf)+a[0]
    answerc=max(bb,bf)+a[1]
    answerd=bb+a[2]       
    answera=max(answerb,answerc,answerd)
    for j in range(int(n/2)-2):
        ff+=a[2*j]
        fb+=a[2*j+1]
        bf-=a[2*j+5]
        bb-=a[2*j+6]
        answerb=ff+max(bf,bb)+a[2*j+2]
        answerc=max(ff,fb)+max(bf,bb)+a[2*j+3]
        answerd=max(ff,fb)+bb+a[2*j+4]
        answere=max(answerb,answerc,answerd)
        if(answere>answera):
            answera=answere
    j=int(n/2)-2
    ff+=a[2*j]
    fb+=a[2*j+1]
    answerb=ff+a[2*j+2]
    answerc=max(ff,fb)+a[2*j+3]
    answerd=max(ff,fb)+a[2*j+4]       
    answere=max(answerb,answerc,answerd)
    if(answere>answera):
        answera=answere
    print(answera)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
sum_e=[a[0]]
sum_o=[a[1]]
min_e=a[0]
for i in range(2,n):
  if i%2==0:
    sum_e.append(sum_e[-1]+a[i])
    min_e=min(min_e,a[i])
  else:
    sum_o.append(sum_o[-1]+a[i])
ans=-(10**15)
for i in range((n-1)//2-1):
  ans=max(ans,sum_e[i]+sum_o[-1]-sum_o[i])
  if(i+1<len(sum_e)):
    ans=max(ans,sum_o[i]+sum_e[-1]-sum_e[i+1])
    print(ans)
ans=max(ans,sum_o[-1])
if n%2==0:
  ans=max(ans,sum_e[-1])
else:
  ans=max(ans,sum_e[-1]-min_e)
print(ans)

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)]
    dp[0]=a[:3]
    for i in range(1,n-2):
        dp[i][0]=dp[i-1][0]+a[i]
        dp[i][1]=dp[i-1][1]+a[i+1]
        dp[i][2]=max(dp[i-1][0],dp[i-1][2])+a[i+2]
    print(max(dp[n-2]))

main()

Submission status: Wrong Answer

Solution code:
s = [input() for i in range(2)]
s[1]=s[1].split(" ")
n=0
j=0
for k in s[1]:
  m = int(k)
  if m%2 == 0:
    j+=m
  if m%2 != 0:
    n+=m
if n<j:
	print(j)
else:
	print(n)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=list(map(int,input().split()))
ans = 0
rui1 = [0]*N
rui1[0]=a[0]+10000000000
rui1[1] = rui1[0]
rui2 = [0]*N
rui2[0] = +10000000000
rui2[1] = a[1]+10000000000
if N%2==0:
    p=0
    q=0

    for i in range(N):
        if i%2==0:
            p+=a[i]
        else:
            q+=a[i]

    ans = max(p,q)
else:
    for i in range(N-2):
        if i%2==0:
            rui1[i+2]=rui1[i]+a[i+2]
            rui2[i+2]=rui2[i+1]
        else:
            rui2[i+2] = rui2[i]+a[i+2]
            rui1[i+2] = rui1[i+1]

    print(rui1)
    print(rui2)

    for i in range(N):
        if i == 0:
            ans = max(rui1[N-1]-rui1[1],rui2[N-1]-rui2[1])
            koho = ans
        if i == N-1:
            koho = max(rui1[N-2]-rui1[0],rui2[N-2]-rui2[0])
        else:
                
            p1 = max(rui1[i-1]-rui1[0],rui2[i-1]-rui2[0])
            q1 = max(rui1[N-1]-rui1[i+1],rui2[N-1]-rui2[i+1])
            koho = p1+q1
            if ans< koho:
                ans = koho

        
        print(koho)

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
n,*a=map(int,open(0).read().split())
if n%2==0:
	o=a[::2]
	e=a[1::2]
	o=[0]+list(accumulate(o))
	e=list(accumulate(e[::-1]))[::-1]+[0]
	ans=0
	for i in range(n//2+1):
		ans=max(ans,o[i]+e[i])
	print(ans)
	exit()
o=a[::2]
e=a[1::2]
o=[0]+list(accumulate(o))
e=list(accumulate(e[::-1]))[::-1]+[0]
dp=[-1e100]*n+[0]
for i in range(n):
	if i%2==1:
		dp[i]=max(o[i//2]+a[i-1],o[i//2]+a[i],dp[i-2]+a[i])
	elif i>0:
		dp[i]=max(dp[i-1],dp[i-2]+a[i])
print(dp[-2])

Submission status: Wrong Answer

Solution code:
n = int(input())
an = (input()).split()
a = []
n = n -1
while n > 1:
    if n > n-1:
        a.append(int(an[n]))
        n = n - 2
        break
    else:
        a.append(int(an[n-1]))
        n = n - 2
        break
print(sum(a))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

n= int(input())
vals= input()
a= list(map(int,vals.split()))
count=0
a.sort()
if n%2==0:
    for i in range(0,int(n/2)):
        count=count+a[2*i+1]
elif n%2==1:
    for j in range(1,int((n+1)/2)):
        count=count+a[2*j]
print(count)

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

    if N & 1:
        return max(b2, a1)
    else:
        return max(a0, b1)


print(main())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n = int(input())
lis = list(map(int,input().split()))
if n % 2 == 0:
  print(max(sum(lis[::2]),sum(lis[1::2])))
  exit()
if n == 3:
  print(max(lis))
  exit()
ans = sum(lis[1::2])
left = 0

right = sum(lis[1::2])
ans = max(ans,sum(lis[::2])-min(lis[0],lis[-1]))
for i in range(n//2):
  right -= lis[2 * i + 1]
  left += lis[2 * i]
  ans = max(ans,right + left)
left = sum(lis[1::2])
right = 0
for i in range(n//2):
  right += lis[-(2*i+1)]
  left -= lis[-(2*i)]
  ans = max(ans,right + left)
print(ans)

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[0]=[0,0,0]
    dp[1][0]=l[0]
    dp[2][1]=l[1]
    dp[3][2]=l[2]
    for i,j in enumerate(l,1):
        dp[i][0]=max(dp[i-2][0]+j,dp[i][0])
        dp[i][1]=max(dp[i-2][1]+j,dp[i-3][0]+j,dp[i][1])
        dp[i][2]=max(dp[i-2][2]+j,dp[i-3][1]+j,dp[i-4][0]+j,dp[i][2])
    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())
AA = list(map(int,input().split()))
AAA = []
for i in range(N):
  AAA.append([i,AA[i]])
AAs = sorted(AAA, key=lambda x: x[1], reverse=True)
AAA_copy = AAA.copy()
del(AAA_copy[AAs[0][0]])
ext_num = int(N/2)
maximum1 = 0
for i in range(ext_num):
  maximum1 += AAs[0][1]
  if AAs[0][0]==0:
    del(AAA[AAs[0][0]:AAs[0][0]+2])
  elif AAs[0][0]==len(AAA)-1:
    del(AAA[AAs[0][0]-1:AAs[0][0]+1])
  else:
    del(AAA[AAs[0][0]-1:AAs[0][0]+2])
  AAs = sorted(AAA, key=lambda x: x[1], reverse=True)
maximum2 = 0
AAA = AAA_copy
AAs = sorted(AAA, key=lambda x: x[1], reverse=True)
for i in range(ext_num):
  maximum2 += AAs[0][1]
  if AAs[0][0]==0:
    del(AAA[AAs[0][0]:AAs[0][0]+2])
  elif AAs[0][0]==len(AAA)-1:
    del(AAA[AAs[0][0]-1:AAs[0][0]+1])
  else:
    del(AAA[AAs[0][0]-1:AAs[0][0]+2])
  AAs = sorted(AAA, key=lambda x: x[1], reverse=True)
if maximum1 > maximum2:
  print(maximum1)
else:
  print(maximum2)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=A[:]
B.sort

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])-A[0]
  for j in range(N//2):
    a+=-A[N-j*2-3]+A[N-j*2-2]
    #print(-A[j*2+2]+A[2*j+1])
    #print(a)
    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つあき

  x=A.index(B[0])
  y=A.index(B[1])
  z=A.index(B[2])
  if(abs(x-y)>2):
    ans=max(ans,sum(A[:min(x,y):2])+sum(A[min(x,y):max(x,y):2])+sum(A[max(x,y)::2]))
  print(max(max(ans,b),c))

Submission status: Wrong Answer

Solution code:
#import re
import sys
input = sys.stdin.readline
#import heapq
#import bisect
#from collections import deque
#import math

def main():
    n = int(input())
    A = list(map(int, input().split()))
    memo = []
    former = 0
    latter = 0
    mini = 0
    for i in range(n):
        if i%2 == 0: 
            if A[i]<A[mini]:
                mini = i
    if n%2 == 1 and A[mini]<0:
        A[mini] = 0

    for i in range(n):
        if i == 0:
            val = A[0] - A[1]
        elif i == n-1:
            val = A[n-1] - A[n-2]
        else:
            val = A[i] - A[i-1] - A[i+1]
        
        if i%2 == 0:
            former+=val
        else:
            latter+=val
    print(max(former,latter))
    



    
if __name__ == '__main__':
    main()