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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

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


n = I()
A = LI()
dp = [0] * n
if n % 2:
    dp = [[0] * n for _ in range(3)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for i in range(2, n):
        if i % 2 == 0:
            dp[0][i] = dp[0][i - 2] + A[i]
        if i % 2 and i >= 3:
            dp[1][i] = max(dp[1][i - 2], dp[0][i - 3]) + A[i]
        if i % 2 == 0 and i >= 4:
            dp[2][i] = max(dp[2][i - 2], dp[1][i - 3], dp[0][i - 4]) + A[i]
    print(max(dp[2][n - 1], dp[1][n - 2], dp[0][n - 3]))
else:
    for i in range(n):
        ret = A[i]
        if i >= 2:
            ret = max(ret, dp[i - 2] + A[i])
        elif i >= 3:
            ret = max(ret, dp[i - 3] + A[i])
        dp[i] = ret
    print('a')
    print(max(dp[-1], dp[-2]))

Submission status: Wrong Answer

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

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


n = I()
A = LI()
dp = [0] * n
if n % 2:
    dp = [[0] * n for _ in range(3)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for i in range(2, n):
        if i % 2 == 0:
            dp[0][i] = dp[0][i - 2] + A[i]
        if i % 2 and i >= 3:
            dp[1][i] = max(dp[1][i - 2], dp[0][i - 3]) + A[i]
        if i % 2 == 0 and i >= 4:
            dp[2][i] = max(dp[2][i - 2], dp[1][i - 3], dp[0][i - 4]) + A[i]
    print(max(dp[2][n - 1], dp[1][n - 2], dp[0][n - 3]))
else:
    for i in range(n):
        ret = A[i]
        if i >= 2:
            ret = max(ret, dp[i - 2] + A[i])
        elif i >= 3:
            ret = max(ret, dp[i - 3] + A[i])
        dp[i] = ret
    print(max(dp[-1], dp[-2]))

Submission status: Wrong Answer

Solution code:
def main():
    N=int(input())
    A=[int(_) for _ in input().split()]
    dp=[[0,0,0] for _ in range(N//2+1)]
    for i in range(N//2):
        dp[i+1][0]=dp[i][0]+A[i*2]
        dp[i+1][1]=max(dp[i][1],dp[i][0])+A[i*2+1]
        if N%2:
            dp[i+1][2]=max(dp[i][2],dp[i][1],dp[i][0])+A[i*2+2]
    for d in dp:
        print(d)
    if N%2:
        print(max(dp[-1]))
    else:
        print(max(dp[-1][:2]))

main()

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)

        cuml = [0] * (n + 1)
        cumr = [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]
            else:
                cumr[i] = cumr[i + 2] + a[i]
        
        for i in range(1,n - 2,2):
                ans = max(ans,cuml[i] + cumr[i + 2])
    
    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
                    if i == n - 4:
                        cumr2[i] = cumr2[i + 3] + a[i]
                    else:
                        cumr2[i] = max(cumr2[i + 2],cumr[i + 3]) + a[i]

        cumr.append(0)
        ans = -INF
        for i in range(n):
            ans = max(ans,cuml[i] + cumr[i + 2])
            if i <= n - 6 and i%2 == 1:
                ans = max(ans,cuml[i] + cumr2[i + 2])
            if i <= n - 4 and i%2 == 1:
                ans = max(ans,cuml[i] + cumr[i + 3])
    
    print(ans)

if __name__ =='__main__':
    main()

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)

        cuml = [0] * (n + 1)
        cumr = [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]
            else:
                cumr[i] = cumr[i + 2] + a[i]
        
        for i in range(1,n - 2,2):
                ans = max(ans,cuml[i] + cumr[i + 2])
    
    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
                    if i == n - 4:
                        cumr2[i] = cumr2[i + 3] + a[i]
                    else:
                        cumr2[i] = max(cumr2[i + 2],cumr[i + 3]) + a[i]

        cumr.append(0)
        ans = 0
        for i in range(n):
            ans = max(ans,cuml[i] + cumr[i + 2])
            if i <= n - 6 and i%2 == 1:
                ans = max(ans,cuml[i] + cumr2[i + 2])
            if i <= n - 4 and i%2 == 1:
                ans = max(ans,cuml[i] + cumr[i + 3])
    
    print(ans)

if __name__ =='__main__':
    main()

Submission status: Wrong Answer

Solution code:

import sys
import math
import itertools

N = int(input())
num = math.floor(N/2)
# print(num)

A = list(map(int, input().split()))
# print(A)
A_1 = [0]
A_2 = [0]
for i in range(N):
    if i % 2 == 0:
        A_1.append(A[i])
        A_2.append(0)
    if i % 2 == 1:
        A_2.append(A[i])
        A_1.append(0)
# print(A_1, A_2)

# A_1 = A[0::2]
# A_2 = A[1::2]

A_1 = list(itertools.accumulate(A_1))
A_2 = list(itertools.accumulate(A_2))

# print(A_1, A_2)

if N % 2 == 0:
    print(max(A_1[-1], A_2[-1]))
    sys.exit()

# 奇数の場合
# i の位置から切り替わる
ans = - float('inf')

for i in range(N+1):
    if i % 2 == 0:
        temp = A_1[i] + (A_2[-1] - A_2[i])
    else:
        temp = A_2[i] + (A_1[-1] - A_1[i])
    # print(temp)
    if temp > ans:
        ans = temp

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]
dp[0]=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:
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]
dp[0]=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)
print(dp[-2])

Submission status: Wrong Answer

Solution code:

import sys
import math
import itertools

N = int(input())
num = math.floor(N/2)
# print(num)

A = list(map(int, input().split()))
# print(A)
A_1 = [0]
A_2 = [0]
for i in range(N):
    if i % 2 == 0:
        A_1.append(A[i])
        A_2.append(0)
    if i % 2 == 1:
        A_2.append(A[i])
        A_1.append(0)
# print(A_1, A_2)

# A_1 = A[0::2]
# A_2 = A[1::2]

A_1 = list(itertools.accumulate(A_1))
A_2 = list(itertools.accumulate(A_2))

# print(A_1, A_2)

if N % 2 == 0:
    print(max(A_1[-1], A_2[-1]))
    sys.exit()

# 奇数の場合
# i の位置から切り替わる
ans = - float('inf')
for i in range(N):
    temp1 = A_1[i] + (A_2[-1] - A_2[i])
    temp2 = A_2[i] + (A_1[-1] - A_1[i])
    temp = max(temp1, temp2)
    if temp > ans:
        ans = temp

print(ans)

Submission status: Wrong Answer

Solution code:

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

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

    for j in reversed(range(2)):
        for i in reversed(range(n)):
            if j == 1 and i >= n-2:
                pass
            elif j == 1:
                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])
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:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

n = INT()
a = LIST()
if n % 2 == 1:
    ef = [0 for _ in range(n)]
    of = [0 for _ in range(n)]
    ee = [0 for _ in range(n)]
    oe = [0 for _ in range(n)]
    for i in range(n):
        ef[i] = ef[i - 1]
        of[i] = of[i - 1]
        if i % 2 == 0:
            ef[i] += a[i]
        else:
            of[i] += a[i]
    for i in reversed(range(n)):
        ee[i] = ee[(i + 1) % n]
        oe[i] = oe[(i + 1) % n]
        if i % 2 == 0:
            ee[i] += a[i]
        else:
            oe[i] += a[i]
    debug(ef)
    debug(of)
    debug(ee)
    debug(oe)
    ans = max(ef[-3], ee[2], of[-1])
    debug(ef[-3], ee[2], of[-1])
    for i in range(n):
        if i + 4 < n and i % 2 == 0:
            ans = max(ans, ef[i] + ee[i + 4])
        if i + 3 < n:
            if i % 2 == 0:
                ans = max(ans, ef[i] + oe[i + 3])
            else:
                ans = max(ans, of[i] + ee[i + 3])
    for i in range(n - 1):
        for j in range(i + 3, n - 2):
            ans = max(ans, ef[i] + of[j] - of[i + 1] + ee[j + 2])
    print(ans)
else:
    s = sum(a)
    ans1 = 0
    for i in range(0, n, 2):
        ans1 += a[i]
    ans2 = s - ans1
    print(max(ans1, ans2))

Submission status: Wrong Answer

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

n = INT()
a = LIST()
if n % 2 == 1:
    ef = [0 for _ in range(n)]
    of = [0 for _ in range(n)]
    ee = [0 for _ in range(n)]
    oe = [0 for _ in range(n)]
    for i in range(n):
        ef[i] = ef[i - 1]
        of[i] = of[i - 1]
        if i % 2 == 0:
            ef[i] += a[i]
        else:
            of[i] += a[i]
    for i in reversed(range(n)):
        ee[i] = ee[(i + 1) % n]
        oe[i] = oe[(i + 1) % n]
        if i % 2 == 0:
            ee[i] += a[i]
        else:
            oe[i] += a[i]
    debug(ef)
    debug(of)
    debug(ee)
    debug(oe)
    ans = max(ef[-3], ee[2], of[-1])
    debug(ef[-3], ee[2], of[-1])
    for i in range(n):
        if i + 4 < n and i % 2 == 0:
            ans = max(ans, ef[i] + ee[i + 4])
        if i + 3 < n:
            if i % 2 == 0:
                ans = max(ans, ef[i] + oe[i + 3])
            else:
                ans = max(ans, of[i] + ee[i + 3])
    
    print(ans)
else:
    s = sum(a)
    ans1 = 0
    for i in range(0, n, 2):
        ans1 += a[i]
    ans2 = s - ans1
    print(max(ans1, ans2))

Submission status: Wrong Answer

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

if N%2==0:
  n=N//2
  a_1=sum(A[::2])
  a_2=sum(A[1::2])
  print(max(a_1,a_2))
else:
  A_1=A[::2]
  A_2=A[1::2]
  ans=0
  for i in range(len(A_1)):
    val=sum(A_1[:i])
    val+=sum(A_2[i:])
    ans=max(ans,val)
  for j in range(len(A_1)):
    val=sum(A_2[:j])
    val+=sum(A_1[j+1:])
    ans=max(ans,val)
  print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

B = [{} for _ in range(N+1)]


for i in range(1,N+1):
  if i == 1:
    B[1][0] = 0
    B[1][1] = A[0]
  elif i == 2:
    B[2][1] = max(A[0],A[1])
    if N % 2 == 1:
      B[2][0] = 0
  else:
    if N % 2 == 0:
      for j in range(math.ceil((i-1)/2),(i+1)//2+1):
        m1 = B[i-2][j-1]+A[i-1] if j-1 in B[i-2] else 0
        m2 = B[i-1][j] if j in B[i-1] else 0
        B[i][j] = max(m1,m2)
    else:
      for j in range(math.ceil((i-2)/2),(i+1)//2+1):
        m1 = B[i-2][j-1]+A[i-1] if j-1 in B[i-2] else 0
        m2 = B[i-1][j] if j in B[i-1] else 0
        B[i][j] = max(m1,m2)
      

print(B[N][N//2])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(ai) for ai in input().split()]
if n % 2 == 0:
    print(max(sum(a[::2]), sum(a[1::2])))
else:
    s = [0,0,0]
    for i in range(n // 2):
        s = [max(s[q] for q in range(p+1)) + a[i*2+p] for p in range(3)]
    print(max(s))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

import math

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

B = [[0]*4]*N

for i in range(N):
  if i == 0:
    B[i][2] = A[0]
  elif i == 1:
    B[i][2] = max(A[0],A[1])
  else:
    B[i][1] = max(B[i-2][1]+A[i],B[i-1][math.ceil((i-1)/2)-math.ceil((i-2)/2)+1])
    B[i][2] = max(B[i-2][2]+A[i],B[i-1][math.ceil((i-1)/2)-math.ceil((i-2)/2)+2])
  

print(B[N-1][2+math.floor(N/2)-math.ceil(N/2)])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(ai) for ai in input().split()]
if n % 2 == 0:
    print(max(sum(a[::2]), sum(a[1::2])))
else:
    s = [0,0,0]
    for i in range(n // 2):
        i0 = i * 2
        i1 = i0 + 1
        i2 = i0 + 2
        snext = [0,0,0]
        snext[0] = s[0] + a[i0]
        snext[1] = max(s[0], s[1]) + a[i1]
        snext[2] = max(s[0], s[1], s[2]) + a[i2]
        s = snext
    print(max(s))

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]
    for i in range(2,n-2,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:
n=int(input());l=list(map(int,input().split()));p=[0]*n;d=[0]*n
for i in range(n):p[i]=l[i]+p[i-2];d[i]=max(p[i-1]*(i&1)+d[i-1]*(i&1),l[i]+d[i-2])
print(d[-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**6)

def solve(n,a):
    wa=0
    for i in range(n):
        if(i%2==0):
            wa+=a[i]
    kotae=wa
    for i in range(n//2):
        wa+=a[(n//2-i-1)*2+1]
        wa-=a[(n//2-i-1)*2]
        if(wa>kotae):
            kotae=wa
    return kotae

def dfs(n,a,k):
    global zen
    zen.append([n,k])
    if(k==1):
        return max(a)
    ari=a[n-1]+dfs(n-2,a[:n-2],k-1)
    if(n==k*2-1):
        return ari
    nasi=dfs(n-1,a[:n-1],k)
    return max(ari,nasi)

n=int(input())

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

if(n%2==0):
    print(solve(n,a))
else:
    data=[[a[0],a[0]],[max(a[:2]),max(a[:2])]]
    #data.append([max(a[:3]),sum(a[:3])-min(a[:3])])
    for i in range(2,n):
        if(i%2==1):
            ari=a[i]+data[i-2][0]
            nasi=data[i-1][1]
            saiyo=max(ari,nasi)
            data.append([saiyo,saiyo])
        else:
            ooi=a[i]+data[i-2][1]
            nasi=data[i-1][1]
            ari=a[i]+data[i-2][0]
            sukunai=max(ari,nasi)
            data.append([sukunai,ooi])
    print(data[n-1][0])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [{} for _ in range(N+1)]
INF = -float('inf')
for i in range(1,N+1):
    mid = i//2
    dp[i][mid-2],dp[i][mid-1],dp[i][mid],dp[i][mid+1],dp[i][mid+2]=INF,INF,INF,INF,INF
dp[1][1] = A[0]
dp[2][1] = max(A[1],dp[1][1])
dp[1][0],dp[2][0]=0,0

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [{} for _ in range(N+1)]
INF = -float('inf')
for i in range(1,N+1):
    mid = i//2
    dp[i][mid-2],dp[i][mid-1],dp[i][mid],dp[i][mid+1],dp[i][mid+2]=INF,INF,INF,INF,INF
dp[1][1] = A[0]
dp[2][1] = max(A[1],dp[1][1])

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
dp = [[0 for i in range(3)] for j in range(n+1)]
for i in range(1,n+1):
  ai = a[i-1]
  dp[i] = dp[i-1][:]
  if i%2:
    dp[i][0] += +ai
    dp[i][1] = max(dp[i-1][0],dp[i-1][1])
  if i%2 == 0:
    dp[i][1] += ai
    dp[i][2] = max(dp[i-1][1],dp[i-1][2])
  if i >= 3 and i%2:
    dp[i][2] += ai
if n%2 == 0:
  print(dp[-1][1])
else:
  print(max(dp[-1][1],dp[-1][2]))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**6)

def solve(n,a):
    wa=0
    for i in range(n):
        if(i%2==0):
            wa+=a[i]
    kotae=wa
    for i in range(n//2):
        wa+=a[(n//2-i-1)*2+1]
        wa-=a[(n//2-i-1)*2]
        if(wa>kotae):
            kotae=wa
    return kotae

def dfs(n,a,k):
    global zen
    zen.append([n,k])
    if(k==1):
        return max(a)
    ari=a[n-1]+dfs(n-2,a[:n-2],k-1)
    if(n==k*2-1):
        return ari
    nasi=dfs(n-1,a[:n-1],k)
    return max(ari,nasi)

n=int(input())

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

if(n%2==0):
    print(solve(n,a))
else:
    data=[[a[0],a[0]],[max(a[:2]),max(a[:2])]]
    data.append([max(a[:3]),sum(a[:3])-min(a[:3])])
    for i in range(3,n):
        if(i%2==1):
            ari=a[i]+data[i-2][0]
            nasi=data[i-1][1]
            saiyo=max(ari,nasi)
            data.append([saiyo,saiyo])
        else:
            ooi=a[i]+data[i-2][1]
            nasi=data[i-1][1]
            ari=a[i]+data[i-2][0]
            sukunai=max(ari,nasi)
            data.append([sukunai,ooi])
    print(data[n-1][0])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
dp = [[0 for i in range(3)] for j in range(n+1)]
for i in range(1,n+1):
  ai = a[i-1]
  dp[i] = dp[i-1][:]
  if i%2:
    dp[i][0] += +ai
    dp[i][1] = max(dp[i-1][0],dp[i-1][1])
  if i%2 == 0:
    dp[i][1] += ai
    dp[i][2] = max(dp[i-1][1],dp[i-1][2])
  if i >= 3 and i%2:
    dp[i][2] += ai
if n%2 == 0:
  print(dp[-1][1])
else:
  print(dp[-1][2])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [{} for _ in range(N+1)]
for i in range(1,N+1):
    mid = i//2
    dp[i][mid-2],dp[i][mid-1],dp[i][mid],dp[i][mid+1],dp[i][mid+2]=0,0,0,0,0
dp[1][1] = A[0]
dp[2][1] = max(A[1],dp[1][1])

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [{} for _ in range(N+1)]
for i in range(1,N+1):
    mid = i//2
    dp[i][mid-2],dp[i][mid-1],dp[i][mid],dp[i][mid+1],dp[i][mid+2]=0,0,0,0,0
dp[1][1] = A[0]
dp[2][1] = max(A[1],dp[1][1])

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

print(max(dp[-1]))

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
lim=n%2+2
dp=[[0]*lim for _ in range(n+100)]
for i in range(n):
  dp[i+1][0]=dp[i-1][0]+arr[i]
  dp[i+1][1]=max(dp[i-1][1]+arr[i],dp[i-2][0]+arr[i])
  if lim==3:
    dp[i+1][2]=max(dp[i-1][2]+arr[i],dp[i-2][1]+arr[i],dp[i-3][0]+arr[i])
print(max(dp[n][:lim]))

Submission status: Wrong Answer

Solution code:
n=int(input())
arr=list(map(int,input().split()))
lim=n%2+2
dp=[[0]*lim for _ in range(n+100)]
for i in range(n):
  dp[i+1][0]=dp[i-1][0]+arr[i]
  dp[i+1][1]=max(dp[i-1][1]+arr[i],dp[i-2][0]+arr[i])
  if lim==3:
    dp[i+1][2]=max(dp[i-1][2]+arr[i],dp[i-2][1]+arr[i],dp[i-3][0]+arr[i])
print(max(dp[-1][:lim]))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [{} for _ in range(N+1)]
for i in range(1,N+1):
    mid = i//2
    dp[i][mid-2],dp[i][mid-1],dp[i][mid],dp[i][mid+1],dp[i][mid+2]=0,0,0,0,0
dp[1][1] = A[0]
dp[2][1] = max(A[1],dp[1][1])

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

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [{} for _ in range(N+1)]
for i in range(1,N+1):
    mid = i//2
    dp[i][mid-2],dp[i][mid-1],dp[i][mid],dp[i][mid+1],dp[i][mid+2]=0,0,0,0,0
dp[1][1] = A[0]
dp[2][1] = max(A[1],dp[1][1])

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

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(2*1000000)

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

dp_dict = {}


def dp(i, j):
    #print(i, j)
    if i >= N:
        return (-1*1000000000)
    if (N//2)-j < (i)//2-1:
        #print(i, j)
        return (-1*1000000000)
    if j == 1:
        return A[i]
    if (i, j) in dp_dict:
        return dp_dict[(i, j)]
    else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        dp_dict[(i, j)] = temp
        return temp


select = N//2
if select == 1:
    print(max(A))
else:
    print(dp(0, select))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
dp = [[0]*5 for _ in range(N+1)]

dp[1][3] = A[0]
dp[2][2] = max(A[1],dp[1][3])

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

print(dp[-1][2])

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(2*1000000)

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

dp_dict = {}


def dp(i, j):
    #print(i, j)
    if i >= N:
        return (-1*1000000000)
    if (N//2)-j < (i)//2:
        print(i, j)
        return (-1*1000000000)
    if j == 1:
        return A[i]
    if (i, j) in dp_dict:
        return dp_dict[(i, j)]
    else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        dp_dict[(i, j)] = temp
        return temp


select = N//2
if select == 1:
    print(max(A))
else:
    print(dp(0, select))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
if n <= 3:
  print(max(a))
  exit()

a = tuple(a)
dp = [[-10**15]*3 for i in range(n)]

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

Submission status: Wrong Answer

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

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7


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

    DP = [defaultdict(int) for _ in range(N + 1)]
    DP[1][1] = A[0]

    for i in range(2, N + 1):
        a = math.floor((i - 1) / 2)
        b = math.floor((i + 1) / 2)
        for j in range(a, b + 1):
            DP[i][j] = max(DP[i - 1][j], DP[i - 2][j - 1] + A[i - 1])
    print(int(DP[N][math.floor(N / 2)]))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

else:
    dp = [[0 for j in range(n // 2 + 1)] for i in range(n + 1)]
    
    dp[1][1] = a[0]
    
    for i in range(2, n + 1):
        for j in range(0, 2):
            tmp = (i - 1) // 2 + j
            if tmp > n // 2:
                continue
            if tmp == 0:
                dp[i][tmp] = 0
            elif i % 2 == 1 and tmp * 2 > i:
                dp[i][tmp] = dp[i - 2][tmp - 1]
            else:
                dp[i][tmp] = max(dp[i - 1][tmp], dp[i - 2][tmp - 1] + a[i - 1])
            
    print(dp[n][n // 2])