Problem:


Score : 600 points

Problem Statement

Given is an integer sequence A_1, ..., A_N of length N.

We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.

Find the maximum possible sum of the chosen elements.

Here \lfloor x \rfloor denotes the greatest integer not greater than x.

Constraints

2 \leq N \leq 2\times 10^5

|A_i|\leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the maximum possible sum of the chosen elements.

Sample Input 1

6
1 2 3 4 5 6

Sample Output 1

12

Choosing 2, 4, and 6 makes the sum 12, which is the maximum possible value.

Sample Input 2

5
-1000 -100 -10 0 10

Sample Output 2

0

Choosing -10 and 10 makes the sum 0, which is the maximum possible value.

Sample Input 3

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5000000000

Watch out for overflow.

Sample Input 4

27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49

Sample Output 4

295



Sample input:
6
1 2 3 4 5 6


Sample output:
12

Submission status: Wrong Answer

Solution code:
import sys, math
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = [0] + list(map(int, input().split()))
    """
    dp[i][j] = (1からi番目の数のうちどの２個も連続しないようにj個選んだ時の和の最大)
    と置くらしい。何故その発想になるんだ？？
    最初は左右で分けて尺取りみたいなことをすれば行けると思ったが、左右の分け目を１つずらしたら
    最適解がガラッと変わって困った　→　じゃあDP、って感じなのかなあ

    このままだとO(N^2)なので状態数を減らす。
    １．j個は連続しないようにとるので、j <= (1 + i) // 2は確定。(iは1-indexedなことに注意)
    ２．残った(N - i)から連続しないように(N // 2 - j)個選ぶには、(N // 2 - j) <= (1 + N - i) // 2、
    　　すなわち(i - 3) // 2 <= jが必要。
    　　（j = 0,1,とか考えてもいいが、最終的にdp[N][N // 2]を求めるのにこれらは寄与しない）
    以上より、(i - 3) // 2 <= j <= (i + 1) // 2の範囲のみでdpすれば十分。

    肝心の遷移だが、A = [3, 1, 4, 1, 5, 9, 2]を例にとると
            i\j|  0  1  2   3   4       dp[5][1] = max(A[5], dp[4][1])
            ----------------------      dp[5][2] = max(A[5] + dp[3][1], dp[4][2])
              1|  0  3                  dp[5][3] = A[5] + dp[3][2]
              2|  0  3
              3|  0  4  7               dp[6][2] = max(A[6] + dp[4][1], dp[5][2])
              4|     4  7               dp[6][3] = max(A[6] + dp[4][2], dp[5][3])
              5|     5  9  12
              6|        9  12           のように、最後の数をとるか取らないかで場合分けすればよい。
              7|        9  12  14       ただしiが奇数の場合、dp[i][(i + 1) // 2]は必ずA[i]を
                                        加えざるを得ないため場合分けは起きないことに注意。
    """

    # iの偶奇でdp[i]をeven, oddに分割してメモリ削減
    odd = [0, A[1], 0]
    even = [0, max(A[1], A[2])]
    for i in range(3, N + 1):
        if i % 2 == 0:
            even[0] = max(A[i] + even[0], odd[1])
            even[1] = max(A[i] + even[1], odd[2])
        elif i > 3:
            odd[0] = max(A[i] + odd[0], even[0])
            odd[1] = max(A[i] + odd[1], even[1])
            odd[2] = A[i] + odd[2]
        else:
            odd[0] = max(A[1:4])
            odd[1] = A[1] + A[3]
    if N % 2 == 0:
        print(even[1])
    else:
        print(odd[1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
li = list(map(int,input().split()))
sumOdd = [0]* 200005
sumEven = [0] * 200005

for i in range(1,n+1):
    sumOdd[i] = sumOdd[i-1]
    sumEven[i] = sumEven[i-1]
    if i%2 == 0:
        sumEven[i] += li[i-1]
    else:
        sumOdd[i] += li[i-1] 

if n % 2 == 0:
    print(max(sumOdd[n],sumEven[n]))
    exit()

# どこまで左にずらしたほうがいいか？
ma = -12345678901234
idxLeft = -1
for i in range(0,n+1,2):
    tmp = sumOdd[i] + (sumEven[n] - sumEven[i])
    if tmp > ma:
        ma = tmp
        idxLeft = i

# どこまで右にずらしたほうがいい？
ma = -12345678901234
idxRight = -1
for i in range(n,-1,-2):
    tmp = sumOdd[n] - sumOdd[i] + sumEven[i]
    if tmp > ma:
        ma = tmp
        idxRight = i+1

if idxLeft < idxRight:
    ans = sumEven[idxRight-1] - sumEven[idxLeft] + sumOdd[idxLeft] + sumOdd[n] - sumOdd[min(idxRight,n)]
    print(ans)
    exit()

mi = 1234567890123
for i in range(0,n,2):
    mi = min(mi,li[i])

print(sumOdd[n]-mi)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
list.sort(a, reverse=True)
ans=0
for i in range(n//2):
  ans += a[2*i]
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

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

ms = [ [0 for i in range(3)] for j in range(n) ]

ms[0][0] = 0
ms[0][1] = 0
ms[0][2] = a[0]

ms[1][0] = 0
ms[1][1] = max(a[0], a[1])

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


print(ms[n - 1][1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

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

k = n // 2

ms = [ [ 0 for j in range(k + 2) ] for i in range(n + 1) ]

for i in range(1, n + 1):
    for j in range(i // 2 - 1, (i + 1) // 2 + 1):
        ms[i][j] = max(ms[i - 2][j - 1] + a[i - 1], ms[i - 1][j])

print(ms[n][k])

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


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


def make4(initial, L, M, N, O):
    return [[[[initial for i in range(O)]
                for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def make3(initial, L, M, N):
    return [[[initial for n in range(N)]
                for m in range(M)]
                for l in range(L)]


def debug(table, *args):
    ret = []
    for name, val in table.items():
        if val in args:
            ret.append('{}: {}'.format(name, val))
    print(' | '.join(ret), file=sys.stderr)


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    A = LI()
    dp_use = [-IINF] * 3
    dp_not_use = [-IINF] * 3
    dp_not_use[0] = 0

    for i in range(N):
        dp_use_next = [-IINF] * 3
        dp_not_use_next = [-IINF] * 3

        for j in range(3):
            if j - 1 >= 0:
                dp_not_use_next[j] = max(dp_use[j], dp_not_use[j-1])
            else:
                dp_not_use_next[j] = dp_use[j]
            dp_use_next[j] = dp_not_use[j] + A[i]

        # print('dp_use    ', *[a if a > -10**10 else '-IINF' for a in dp_use_next])
        # print('dp_not_use', *[a if a > -10**10 else '-IINF' for a in dp_not_use_next])
        dp_use = dp_use_next
        dp_not_use = dp_not_use_next

    if N % 2 == 0:
        print(max(dp_use[0], dp_not_use[1]))
    else:
        print(max(dp_use[2], dp_not_use[1]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(x) for x in input().split()]

# dp(直前の値を取っている)(最大個数取っている)
dp00 = dp01 = dp10 = dp11 = 0

for i in range(n):
    if i % 2 == 0:
        dp10 = dp00 + a[i]
        dp00 = max(dp01, dp11)
        dp11 = dp01 + a[i]
    else:
        dp01 = dp11
        dp11 = dp00 + a[i]
        dp00 = max(dp00, dp10)
        if i == 3:
            dp10 = a[i]

if n % 2 == 0:
    print(max(dp01, dp11))
else:
    print(max(dp00, dp10))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [int(x) for x in input().split()]

# dp(直前の値を取っている)(最大個数取っている)
dp00 = 0
dp01 = -10**15
dp10 = -10**15
dp11 = a[0] 

for i in range(1, n):
    if i % 2 != 0:
        dp01 = max(dp01, dp11)
        dp11 = dp00 + a[i]
        dp00 = max(dp00, dp10)
    else:
        dp10 = dp00 + a[i]
        dp00 = max(dp01, dp11)
        dp11 = dp01 + a[i]

if n % 2 == 0:
    print(max(dp01, dp11))
else:
    print(dp10)

Submission status: Wrong Answer

Solution code:
Nin=int(input())
guki=Nin%2
N=Nin//2
A=list(map(int,input().split()))
summost=sum(A[1::2])
if guki==0:
  for a in range(0,N):
    if summost<sum(A[:2*a:2]+A[2*a+1::2]):
      summost=sum(A[:2*a:2]+A[2*a+1::2])
else:
  for a in range(0,N):
    for b in range(a,N):
      if summost<sum(A[:2*a:2]+A[2*a+1:2*b+1:2]+A[2*b+2::2]):
        summost=sum(A[:2*a:2]+A[2*a+1:2*b+1:2]+A[2*b+2::2])
print(summost)

Submission status: Wrong Answer

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

def bottom_up(c):
  dp=[None]*(len(c)+1)
  dp[0]=0
  dp[1]=c[0]
  for i in range(2,len(c)+1):
    dp[i]=max(dp[i-2]+c[i-1],dp[i-1])
  return dp

dp=bottom_up(c)
print(dp[-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
sys.setrecursionlimit(10**8)
INF = float("inf")

import math


def array(*args, initial=0):
    pre = "["*len(args)
    post = ""
    for a in args[::-1]:
        post += " for _ in range("+str(a)+")]"
    S = pre + str(initial) + post
    return eval(S)


def solve(N: int, A: "List[int]"):

    if N % 2 == 0:
        K = 2
    else:
        K = 3

    DP = array(N, K)
    DP[0][0] = A[0]
    for i in range(1, N):
        for k in range(K):
            DP[i][k] = DP[i-2][k]
            if k-1 >= 0:
                DP[i][k] = max(DP[i][k], DP[i-3][k-1])
            if k-2 >= 0:
                DP[i][k] = max(DP[i][k], DP[i-4][k-2])
            DP[i][k] += A[i]
    if N % 2 == 0:
        print(max(*DP[-1]))
    else:
        print(max(DP[-1][2], DP[-1][1], DP[-2][0]))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
sys.setrecursionlimit(10**8)
INF = float("inf")

import math


def array(*args, initial=0):
    pre = "["*len(args)
    post = ""
    for a in args[::-1]:
        post += " for _ in range("+str(a)+")]"
    S = pre + str(initial) + post
    return eval(S)


def solve(N: int, A: "List[int]"):

    if N % 2 == 0:
        K = 2
    else:
        K = 3

    DP = array(N, K)
    DP[0][0] = A[0]
    for i in range(1, N):
        for k in range(K):
            DP[i][k] = DP[i-2][k]
            if k-1 >= 0:
                DP[i][k] = max(DP[i][k], DP[i-3][k-1])
            if k-2 >= 0:
                DP[i][k] = max(DP[i][k], DP[i-4][k-2])
            DP[i][k] += A[i]
    print(max(*DP[-1]))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def find_max(a):
    n = len(a)

    if n <= 3:
        return max(a)

    dp = [[0] * (2 + n % 2) for _ in range(n)]

    for i in range(2 + n % 2):
        dp[i][i] = a[i]
        dp[i + 1][i] = a[i]

    for i in range(2, n):
        for j in range(2 + n % 2):
            for extra_space in range(j + 1):
                curr_sum = dp[i - (2 + extra_space)][j - extra_space] + a[i]
                if curr_sum > dp[i][j]:
                    dp[i][j] = curr_sum

    return dp[-1][1 + n % 2]


def main():
    _ = int(input())
    a = list(map(int, input().split()))

    print(find_max(a))


main()

Submission status: Wrong Answer

Solution code:

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

dp=[[-float('inf'),-float('inf'),-float('inf')] for i in range(n)]
# dp[i][0]:iまででまだ飛ばしてない
# dp[i][1]:一つ飛ばしてる
# dp[i][2]:２つ飛ばしてる
dp[0][0]=a[0]
dp[1][0]=a[1]
for i in range(2,n):
    dp[i][0]=dp[i-2][0]+a[i]
    if i>=3:
        dp[i][1]=max(dp[i-2][1]+a[i],dp[i-3][0]+a[i])
    if i>=4:
        dp[i][2]=max(dp[i-2][2]+a[i],dp[i-3][1]+a[i],dp[i-4][0]+a[i])

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

Submission status: Wrong Answer

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

dp=[[-float('inf'),-float('inf'),-float('inf')] for i in range(n)]
# dp[i][0]:iまででまだ飛ばしてない
# dp[i][1]:一つ飛ばしてる
# dp[i][2]:２つ飛ばしてる
dp[0][0]=a[0]
dp[1][0]=a[1]
for i in range(2,n):
    dp[i][0]=dp[i-2][0]+a[i]
    if i>=3:
        dp[i][1]=max(dp[i-2][1]+a[i],dp[i-3][0]+a[i])
    if i>=4:
        dp[i][2]=max(dp[i-2][2]+a[i],dp[i-3][1]+a[i],dp[i-4][0]+a[i])

print(max(dp[-1]))

Submission status: Wrong Answer

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



if n  == 2:
    tp = sum(arr[::2])
    print(max(sum(arr)-tp,tp))
elif n == 3:
    print(arr[0]+arr[2])
else:
    hoge = -(10**15)
    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]])

    # for l in buf:
    #     print(l)
    if n% 2 == 0:
        print(max(buf[-1][1],buf[-2][0]))
    else:
        print(max(buf[-1][2],buf[-2][1],buf[-3][0]))

Submission status: Wrong Answer

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



if n  == 2:
    tp = sum(arr[::2])
    print(max(sum(arr)-tp,tp))
elif n == 3:
    print(arr[0]+arr[2])
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]])

    # for l in buf:
    #     print(l)
    if n% 2 == 0:
        print(max(buf[-1][1],buf[-2][0]))
    else:
        print(max(buf[-1][2],buf[-2][1],buf[-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))
elif n == 3:
    print(arr[0]+arr[2])
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(max(buf[-1][2],buf[-2][1],buf[-3][0]))

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N%2==0:#偶数なら1回まで2こ飛ばしで無茶できる
    dp=[[-float("inf") for _ in range(2)] for _ in range(N+10)]#dpはj=0の時は無茶をしていない系列j=1の時は1回無茶をした系列である
    if N==2:#2の時は個別
        print(max(A[0],A[1]))
    else:#それ以外の時は
        for i in range(N):
            if i==0:            #i=0をとる時の任意の系列は無茶を確実にしていないのでdp[i][0]のみA[0]
                dp[0][0]=A[0]
            elif i==1:          #i=1をとる時の任意の系列は一回無茶をして取っているはずである、よってdp[i][1]のみA[1]
                dp[1][1]=A[1]
            elif i==2:          #i=2をとる時の任意の系列は一回も無茶せずに先頭からとっているのでdp[i][0]=A[0]+A[2]
                dp[2][0]=A[0]+A[2]
            else:                   #そのほかは再帰的に考える
                for j in range(2):
                    if j==0:                                                    #無茶しない系列を生成する時
                        dp[i][0]=max(dp[i][0],dp[i-2][0]+A[i])                  #そこまでの無茶しなかった系列に自らを足していけば良い
                    elif j==1:                                                  #一回無茶する系列を生成する時
                        dp[i][1]=max(dp[i][1],dp[i-2][1]+A[i],dp[i-3][0]+A[i])  #すでにある無茶した時の値(いらない？)と、前までの系列で無茶していて今回は無茶できないパターン、今回で無茶をするパターンのうち最大を用いて系列生成すれば良い
        print(max(dp[N-1]))                                                     #全てのパターンの中で最大が出るはず
else:#奇数なら計2回まで無茶できる(2飛ばし×2、3飛ばし×1まで許容)
    #print(A[0],A[1])
    dp=[[-float("inf") for _ in range(3)] for _ in range(N+10)]#dpはj=0の時は無茶をしない系列j=1は1回無茶をした系列、j=2は2回無茶をしている系列
    if N==3:#N=3の時は個別
        print(max(A[0],A[1],A[2]))
    else:#それ以外の時は
        for i in range(N):
            if i<4:
                if i==0:                                        #i=0をとる任意の系列は無茶を確実にしていないのでdp[i][0]のみA[0]
                    dp[0][0]=A[0]
                if i==1:                                        #i=1をとる任意の系列は確実に1回無茶をしているのでdp[i][1]のみA[1]
                    dp[1][1]=A[1]
                if i==2:                                        #i=2をとる時は2回分の無茶をしてA[2]を得る時(dp[i][2]=A[2])および1かいも無茶せずに撮っている時(dp[i][0]=A[2]+A[0])
                    dp[2][2]=A[2]
                    dp[2][0]=A[0]+A[2]
                if i==3:                                        #i=3をとる時は1回目で無茶をしてそのあと無茶していないパターン(dp[1][1]+A[3])といきなり1回無茶をしたパターン(dp[0][0]+A[3])があるのでその最大を
                    dp[3][1]=max(dp[1][1]+A[3],dp[0][0]+A[3])
            else:                                                                               #そのほかは再帰的に
                for j in range(3):
                    if j==0:                                                                    #無茶してない系列を生成する時、
                        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])                  #すでにある1回無茶した時の値(いらない？)と、前までの系列で1回無茶していて今回は無茶しないパターン、今回で初めて無茶をするパターンのうち最大を用いて系列生成すれば良い
                    else:                                                                       #2回無茶した系列を生成する時
                        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])  #すでにある2回無茶した時の値(いらない？)と、もう二回無茶していて無茶できないパターン、前までの系列で1回無茶していて今回も1回無茶するしないパターン、今回でいきなり2回無茶をするパターンのうち最大を用いて系列生成すれば良い
        print(max(dp[N-1]))                                                                     #全てのパターンの中の最大が出るはず

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
if N%2==0:
    dp=[[-float("inf") for _ in range(2)] for _ in range(N+10)]
    if N==2:
        print(max(A[0],A[1]))
    else:
        for i in range(N):
            if i==0:
                dp[i][0]=A[0]
            elif i==1:
                dp[i][1]=A[1]
            elif i==2:
                dp[i][0]=A[0]+A[2]
            else:
                for j in range(2):
                    if j==0:
                        dp[i][0]=max(dp[i][0],dp[i-2][0]+A[i])
                    elif j==1:
                        dp[i][1]=max(dp[i][1],dp[i-2][1]+A[i],dp[i-3][0]+A[i])
        print(max(dp[N-1]))
else:
    #print(A[0],A[1])
    dp=[[-float("inf") for _ in range(3)] for _ in range(N+10)]
    if N==3:
        print(max(A[0],A[1],A[2]))
    else:
        for i in range(N):
            if i<4:
                if i==0:
                    dp[i][0]=A[0]
                if i==1:
                    dp[i][1]=A[1]
                if i==2:
                    dp[i][2]=A[2]
                    dp[i][0]=A[0]+A[2]
                if i==3:
                    dp[i][1]=max(dp[1][1]+A[3],dp[0][0]+A[3])
            else:
                for j in range(3):
                    if j==0:#ここでも2こずつ規則よく飛ばすと決めた
                        dp[i][0]=max(dp[i][0],dp[i-2][0]+A[i])
                    elif j==1:#1回だけ無茶した
                        dp[i][1]=max(dp[i][1],dp[i-2][1]+A[i],dp[i-3][0]+A[i])
                    else:
                        dp[i][2]=max(dp[i][2],dp[i-2][2]+A[i],dp[i-3][1]+A[i],dp[i-4][0]+A[i])
        print(max(dp[N-1]))

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    t = [0]*n
    for i in range(n):
        t[i] = a[i]
        if 1 < i:
            t[i] += t[i-2]
    if n%2 == 0:
        x = -float("inf")
        for i in range(1, n-2, 2):
            x = max(x, t[i-1] + t[n-1] - t[i])
        print(max(t[n-1], t[n-2], x))
    else:
        x = t[n-2] #全て偶数index
        y = -float("inf")
        for i in range(0, n, 2):
            y = max(y, t[n-1] - a[i])
        z = -float("inf") #奇数|偶数
        for i in range(1, n-2, 2):
            buf = t[i-1] + (t[n-2] - t[i])
            z = max(z, buf)
        w = -float("inf")#偶数|奇数
        for i in range(2, n-1, 2):
            buf = t[i-1] + (t[n-1] - t[i])
            w = max(w, buf)
        s = [-1]*n
        s[0] = 0
        s[1] = 1
        for i in range(2, n):
            s[i] = s[i-2]
            if i%2 == 1:
                if t[s[i]] > t[i]:
                    s[i] = i
        v = -float("inf")
        for i in range(1, n, 2):
            index = s[i]
            if i == index:
                continue
            buf = t[n-1] - (t[i+1] - t[index-1])
            buf += t[i] - t[index]
            v = max(v, buf)
        print(max(x, y, z, w, v))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ai = [int(i) for i in input().split()]

is_odd = True

if n % 2 == 0:
    is_odd = False

if is_odd == True:
    dp = [[0 for i in range(3)] for j in range(n)]
else:
    dp = [[0 for i in range(2)] for j in range(n)]

if n == 3:
    print(max(ai[0]+ai[2],ai[1]))
    exit()
elif n == 2:
    print(max(ai[0],ai[1]))
    exit()

dp[1][0] = ai[0]
dp[1][1] = ai[1]

if is_odd == True:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
        dp[i][2] = max(dp[i-4][0]+ai[i],dp[i-3][1]+ai[i],dp[i-2][2]+ai[i])
    print(max(dp[n-3][0],dp[n-2][0],dp[n-1][1],dp[n-1][2]))
else:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
ai = [int(i) for i in input().split()]

is_odd = True

if n % 2 == 0:
    is_odd = False

if is_odd == True:
    dp = [[0 for i in range(3)] for j in range(n)]
else:
    dp = [[0 for i in range(2)] for j in range(n)]

if n == 3:
    print(max(ai[0]+ai[2],ai[1]))
    exit()
elif n == 2:
    print(max(ai[0],ai[1]))
    exit()

dp[1][0] = ai[0]
dp[1][1] = ai[1]

if is_odd == True:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
        dp[i][2] = max(dp[i-4][0]+ai[i],dp[i-3][1]+ai[i],dp[i-2][2]+ai[i])
    print(max(dp[n-2][0],dp[n-1][1],dp[n-1][2]))
else:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
ai = [int(i) for i in input().split()]

is_odd = True

if n % 2 == 0:
    is_odd = False

if is_odd == True:
    dp = [[0 for i in range(3)] for j in range(n)]
else:
    dp = [[0 for i in range(2)] for j in range(n)]

if n == 3:
    print(max(ai[0]+ai[2],ai[1]))
    exit()
elif n == 2:
    print(max(ai[0],ai[1]))
    exit()

dp[1][0] = ai[0]
dp[1][1] = ai[1]

if is_odd == True:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
        dp[i][2] = max(dp[i-4][0]+ai[i],dp[i-3][1]+ai[i],dp[i-2][2]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))
else:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
ai = [int(i) for i in input().split()]

is_odd = True

if n % 2 == 0:
    is_odd = False

if is_odd == True:
    dp = [[0 for i in range(3)] for j in range(n)]
else:
    dp = [[0 for i in range(2)] for j in range(n)]

if n == 3:
    print(max(ai[0]+ai[2],ai[1]))
    exit()
elif n == 2:
    print(max(ai[0],ai[1]))
    exit()
    

if is_odd == True:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
        dp[i][2] = max(dp[i-4][0]+ai[i],dp[i-3][1]+ai[i],dp[i-2][2]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1],dp[n-1][2]))
else:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1]))

Submission status: Wrong Answer

Solution code:
d=[0,0]
p=d[:]
for a in[*open(0)][1].split():a=int(a);d+=[t:=max(a+d[-2],(d,p)[len(d)&1][-1])];p+=a+p[-2],
print(t)

Submission status: Wrong Answer

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

# aを偶数奇数の要素で振り分け
a1=[]
a2=[]

for i in range(n):
    if i%2==0:
        a1.append(a[i])
    else:
        a2.append(a[i])

# 累積和も作っておく
a3=list(itertools.accumulate(a1))


x1=sum(a1)
x2=sum(a2)


if n%2==0:
    print(max(x1,x2))

else:
    # 奇数番目だけの要素を選んだ時の最大値
    ans1=sum(a1)-min(a1)
    # dp1[i]=奇数偶数奇数or偶数奇数と移動した時のi番目までのMAX
    dp1 = [-float('inf')] * (n // 2 + 1)
    dp1[0] = a1[0]
    # dp2[i]=奇数偶数or偶数のみと移動した時のi番目までのMAX
    dp2 = [-float('inf')] * (n // 2)
    dp2[0] = a2[0]
    for i in range(n // 2 - 1):
        dp2[i + 1] = max(a3[i] + a2[i + 1], dp2[i] + a2[i + 1])
        if i==0:
            dp1[i + 2] = dp2[i] + a1[i + 2]
        else:
            dp1[i + 2] = max(dp2[i] + a1[i + 2], dp1[i + 1] + a1[i + 2])
    print(max(dp1[-1], dp2[-1],ans1))

Submission status: Wrong Answer

Solution code:
C = -(10**15 + 7)


def main():
    from collections import defaultdict
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    A.sort()
    dp = defaultdict(lambda: C)
    for i in range(N+1):
        dp[(i, 0)] = 0
        if i != 0:
            dp[(i, 1)] = max(dp[(i-1, 1)], A[i-1])
    for i in range(2, N+1):
        for j in range(i//2-1, (i+1)//2 + 1):
            if j < 0:
                continue
            # A_i(1-index)でj個選ばなければいけない
            cur = max(dp[(i, j)], dp[(i-1, j)])
            cur = max(cur, dp[i-2, j-1] + A[i-1])
            dp[(i, j)] = cur
    print(dp[(N, K)])
    # for i in range(N+1):
    #     print(dp[(i, 0)], dp[(i, 1)], dp[(i, 2)], dp[i, 3])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
C = -(10**9 + 7)


def main():
    from collections import defaultdict
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    dp = defaultdict(lambda: C)
    for i in range(N+1):
        dp[(i, 0)] = 0
        if i != 0:
            dp[(i, 1)] = max(dp[(i-1, 1)], A[i-1])
    for i in range(2, N+1):
        for j in range(i//2-1, (i+1)//2 + 1):
            if j < 0:
                continue
            # A_i(1-index)でj個選ばなければいけない
            cur = max(dp[(i, j)], dp[(i-1, j)])
            cur = max(cur, dp[i-2, j-1] + A[i-1])
            dp[(i, j)] = cur
    print(dp[(N, K)])
    # for i in range(N+1):
    #     print(dp[(i, 0)], dp[(i, 1)], dp[(i, 2)], dp[i, 3])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
num = int(input())
a = list(map(int,input().split()))
if num%2 ==0:
  sum1 = 0
  sum2 = 0
  for i in range(0,num,2):
    sum1 += a[i]
  for t in range(1,num+1,2):
    sum2 += a[i]
  print(max([sum1,sum2]))
if num%2 ==1:
  sum3 = 0
  sum4 = 0
  sum5 = 0
  for i in range(0,num-1,2):
    sum3 += a[i]
  for i in range(1,num,2):
    sum4 += a[i]
  for i in range(2,num+1,2):
    sum5 += a[i]
  print(max([sum3,sum4,sum5]))

Submission status: Wrong Answer

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

# aを偶数奇数の要素で振り分け
a1=[]
a2=[]

for i in range(n):
    if i%2==0:
        a1.append(a[i])
    else:
        a2.append(a[i])

# 累積和も作っておく
a3=[0]+list(itertools.accumulate(a1))
a4=[0]+list(itertools.accumulate(a2))

x1=sum(a1)
x2=sum(a2)


if n%2==0:
    print(max(x1,x2))

else:
    # 奇数番目だけの要素を選んだ時の最大値
    ans1=sum(a1)-min(a1)
    # dp1[i]=奇数偶数奇数or偶数奇数と移動した時のi番目の要素でのMAX
    dp1 = [-float('inf')] * (n // 2 + 1)
    dp1[0] = a1[0]
    # dp2[i]=奇数偶数or偶数のみと移動した時のi番目の要素でのMAX
    dp2 = [-float('inf')] * (n // 2)
    dp2[0] = a2[0]
    for i in range(n // 2 - 1):
        dp2[i + 1] = max(a3[i + 1] + a2[i + 1], dp2[i] + a2[i + 1])
        if i <= 1:
            dp1[i + 2] = dp2[i] + a1[i + 2]
        else:
            dp1[i + 2] = max(dp2[i] + a1[i + 2], dp1[i + 1] + a1[i + 2])
    print(max(dp1[-1], dp2[-1],ans1))

Submission status: Wrong Answer

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

# aを偶数奇数の要素で振り分け
a1=[]
a2=[]

for i in range(n):
    if i%2==0:
        a1.append(a[i])
    else:
        a2.append(a[i])

# 累積和も作っておく
a3=[0]+list(itertools.accumulate(a1))
a4=[0]+list(itertools.accumulate(a2))

x1=sum(a1)
x2=sum(a2)


if n%2==0:
    print(max(x1,x2))

else:
    # 奇数番目だけの要素を選んだ時の最大値
    ans1=sum(a1)-min(a1)
    # 偶数番目だけを選んだ時
    ans2=sum(a2)
    if n<=5:
        print(max(ans1,ans2))
    else:
        # dp1[i]=奇数偶数奇数or偶数奇数と移動した時のi番目の要素でのMAX
        dp1 = [-float('inf')] * (n // 2 + 1)
        dp1[0]=a1[0]
        # dp2[i]=奇数偶数or偶数のみと移動した時のi番目の要素でのMAX
        dp2 = [-float('inf')] * (n // 2)
        dp2[0]=a2[0]
        for i in range(n // 2-1):
            dp2[i+1] = max(a3[i+1]+a2[i+1],dp2[i]+a2[i+1])
            if i<=1:
                dp1[i+2]=dp2[i]+a1[i+2]
            else:
                dp1[i+2] = max(dp2[i]+a1[i+2],dp1[i+1]+a1[i+2])
        print(max(dp1[-1],dp2[-1],ans1,ans2))

Submission status: Wrong Answer

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

# aを偶数奇数の要素で振り分け
a1=[]
a2=[]

for i in range(n):
    if i%2==0:
        a1.append(a[i])
    else:
        a2.append(a[i])

# 累積和も作っておく
a3=[0]+list(itertools.accumulate(a1))
a4=[0]+list(itertools.accumulate(a2))

x1=sum(a1)
x2=sum(a2)


if n%2==0:
    print(max(x1,x2))

else:
    # 奇数番目だけの要素を選んだ時の最大値
    ans1=sum(a1)-min(a1)
    # 偶数番目だけを選んだ時
    ans2=sum(a2)
    if n<=5:
        print(max(ans1,ans2))
    else:
        # 奇数→偶数→奇数のとき
        # dp1[i]=奇数偶数奇数と移動した時のi番目の要素でのMAX
        dp1 = [-float('inf')] * (n // 2 + 1)
        # dp2[i]=奇数偶数と移動した時のi番目の要素でのMAX
        dp2 = [-float('inf')] * (n // 2)

        for i in range(n // 2-1):
            dp2[i+1] = max(a3[i+1]+a2[i+1],dp2[i]+a2[i+1])
            if i>=1 and i<=n//2-1:
                dp1[i+2] = max(dp2[i]+a1[i+2],dp1[i+1]+a1[i+2])
        print(max(dp1[-1],dp2[-1]))