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,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo


show_flg=False
show_flg=True

ans=0


n=I()
a=LI()+[0]*4

dp=[[0]*3for i in range(n+1+4)]
dp[0][0]=a[0]
dp[1][1]=a[1]
dp[2][2]=a[2]

for i in range(n):
    dp[i][2]=max([dp[i-2-j][2-j]+a[i] for j in range(3) if i-2-j>=0]+[dp[i][2]])
    dp[i][1]=max([dp[i-2-j][1-j]+a[i] for j in range(2) if i-2-j>=0]+[dp[i][1]])
    dp[i][0]=max([dp[i-2-j][j]+a[i] for j in range(1) if i-2-j>=0]+[dp[i][0]])

ans=max(dp[n-1][:]+dp[n-2][:2]+dp[n-3][:1])
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    INF = 10 ** 12
    N = int(input())
    A = list(map(int, input().split(' ')))
    K = 1 + N % 2  # 余分な×を入れられる個数
    # dp[i][j]: i個目までの要素で余分な×をj個使った際の最大値
    dp = [[- INF for _ in range(K + 1)] for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(K + 1):
            if j < K:
                # 余分な×を使う場合
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
            # 余分な×を使わない場合
            now = dp[i][j]
            if (i + j) % 2 == 0:
                # 基本はi % 2 == 0の時にA[i]を足していく
                # ただ、余分な×がj個入っていると、その分ずれる
                now += A[i]
            dp[i + 1][j] = max(dp[i + 1][j], now)
    print(dp[N][K])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

d = N // 2
A1,A2 = [],[]
for i in range(0,N,2):
    A1.append(A[i])
for i in range(1,N,2):
    A2.append(A[i])

A1.sort()
A2.sort()

A1.reverse()
A2.reverse()

A1cnt = 0
A2cnt = 0
for i in range(d):
    A1cnt += A1[i]

print(max(A1cnt,A2cnt))

Submission status: Wrong Answer

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

dp = [[0 for i in range(2)] for j in range(N+1)]

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

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

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())


def FLIST(n):
    res = [1]
    for i in range(1, n+1):
        res.append(res[i-1]*i % DVSR)
    return res


N = II()
AS = LI()
DP = {}
DP[(0, 0)] = 0

mm = -(10**18)
for i in range(N):
    NX = {}
    for ((cnt, isUsed), value) in DP.items():
        if isUsed:
            if cnt >= (i // 2 - 15):
                NX[(cnt, 0)] = max(value, NX.get((cnt, 0)) or mm)
        else:
            if cnt >= (i // 2 - 15):
                NX[(cnt, 0)] = max(value, NX.get((cnt, 0)) or mm)
            if cnt >= (i // 2 - 15):
                NX[(cnt+1, 1)] = max(value + AS[i],
                                     NX.get((cnt+1, 1)) or mm)
    DP = NX
    # print(NX)

res = 0
for ((cnt, _), value) in DP.items():
    if cnt == N//2:
        res = max(res, value)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())


def FLIST(n):
    res = [1]
    for i in range(1, n+1):
        res.append(res[i-1]*i % DVSR)
    return res


N = II()
AS = LI()
DP = {}
DP[(0, 0)] = 0

mm = -(10**18)
for i in range(N):
    NX = {}
    for ((cnt, isUsed), value) in DP.items():
        if isUsed:
            if cnt >= (i // 2 - 5):
                NX[(cnt, 0)] = max(value, NX.get((cnt, 0)) or mm)
        else:
            if cnt >= (i // 2 - 5):
                NX[(cnt, 0)] = max(value, NX.get((cnt, 0)) or mm)
            if cnt >= (i // 2 - 5):
                NX[(cnt+1, 1)] = max(value + AS[i],
                                     NX.get((cnt+1, 1)) or mm)
    DP = NX
    # print(NX)

res = 0
for ((cnt, _), value) in DP.items():
    if cnt == N//2:
        res = max(res, value)
print(res)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())


def FLIST(n):
    res = [1]
    for i in range(1, n+1):
        res.append(res[i-1]*i % DVSR)
    return res


N = II()
AS = LI()
DP = {}
DP[(0, 0)] = 0

mm = -(10**10)
for i in range(N):
    NX = {}
    for ((cnt, isUsed), value) in DP.items():
        if isUsed:
            if cnt >= (i // 2 - 5):
                NX[(cnt, 0)] = max(value, NX.get((cnt, 0)) or mm)
        else:
            if cnt >= (i // 2 - 5):
                NX[(cnt, 0)] = max(value, NX.get((cnt, 0)) or mm)
            if cnt >= (i // 2 - 5):
                NX[(cnt+1, 1)] = max(value + AS[i],
                                     NX.get((cnt+1, 1)) or mm)
    DP = NX
    # print(NX)

res = 0
for ((cnt, _), value) in DP.items():
    if cnt == N//2:
        res = max(res, value)
print(res)

Submission status: Wrong Answer

Solution code:
INF = 10**18

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

if N % 2 == 0:
    od = [0 for _ in range(N // 2 + 1)]
    ev = [0 for _ in range(N // 2 + 1)]
    for i in range(N):
        if i % 2 == 0:
            od[i // 2 + 1] = od[i // 2] + A[i]
        else:
            ev[~(i // 2 + 1)] = ev[~(i // 2)] + A[~i + 1]
    res = -INF
    for i in range(N // 2 + 1):
        res = max(res, od[i] + ev[i])
    print(res)

else:
    dp = [[[-INF for k in range(2)] for j in range(3)] for i in range(N + 1)]
    dp[0][0][0] = 0

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

    res = -INF

    for j in range(3):
        for k in range(2):
            if k == 0 and j == 2:
                continue
            res = max(res, dp[N][j][k])

    print(res)

Submission status: Wrong Answer

Solution code:
INF = 10**18

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

dp = [[[-INF for k in range(2)] for j in range(3)] for i in range(N + 1)]
dp[0][0][0] = 0

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

res = -INF

for j in range(3):
    for k in range(2):
        res = max(res, dp[N][j][k])

print(res)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
if n == 1:
    print(A[0])
    exit()
if n % 2 == 0:
    A1 = A[0::2]
    A2 = A[1::2]
    AA1 = list(accumulate([0] + A1))
    AA2 = list(accumulate([0] + A2[::-1]))
    ans = -(10 ** 10)
    for i in range(n // 2 + 1):
        temp = AA1[i] + AA2[n // 2 - i]
        ans = max(ans, temp)
else:
    # skip回数は0回か1回か2回
    dp = [[-(10 ** 10)] * (3) for _ in range(n + 2)]
    dp[0][0] = 0
    for i in range(n + 1):
        for j in range(3):
            # no skip
            ni = i + 2
            nj = j
            if ni < n + 2:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j] + A[i])
            # skip
            ni = i + 1
            nj = j + 1
            if nj < 3 and ni < n + 2:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j])
    ans = max(dp[-1][2], dp[-2][2])
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
    A1 = A[0::2]
    A2 = A[1::2]
    AA1 = list(accumulate([0] + A1))
    AA2 = list(accumulate([0] + A2[::-1]))
    ans = 0
    for i in range(n // 2 + 1):
        temp = AA1[i] + AA2[n // 2 - i]
        print(temp)
        ans = max(ans, temp)
else:
    # skip回数は0回か1回か2回
    dp = [[-(10 ** 20)] * (3) for _ in range(n + 2)]
    dp[0][0] = 0
    for i in range(n + 1):
        for j in range(3):
            # no skip
            ni = i + 2
            nj = j
            if ni < n + 2:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j] + A[i])
            # skip
            ni = i + 1
            nj = j + 1
            if nj < 3 and ni < n + 2:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j])
    ans = dp[-1][2]
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
    A1 = A[0::2]
    A2 = A[1::2]
    AA1 = list(accumulate([0] + A1))
    AA2 = list(accumulate([0] + A2[::-1]))
    ans = 0
    for i in range(n // 2 + 1):
        ans = max(ans, AA1[i] + AA2[n // 2 - i])
else:
    # skip回数は0回か1回か2回
    dp = [[-(10 ** 10)] * (3) for _ in range(n + 2)]
    dp[0][0] = 0
    for i in range(n + 1):
        for j in range(3):
            # no skip
            ni = i + 2
            nj = j
            if ni < n + 2:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j] + A[i])
            # skip
            ni = i + 1
            nj = j + 1
            if nj < 3 and ni < n + 2:
                dp[ni][nj] = max(dp[ni][nj], dp[i][j])
    ans = dp[-1][2]
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N % 2 == 0:
        return max(sum(A[::2]), sum(A[1::2]))

    M = N // 2
    Acum = [0]
    for i in range(M):
        Acum.append(A[i * 2] + Acum[-1])
    Acum.reverse()
    A.reverse()

    res = -10 ** 20
    OX = 0
    XO = 0
    for i in range(M):
        XX = max(OX, XO) + Acum[i]
        XO = max(OX, XO) + A[i * 2 + 1]
        OX = OX + A[i * 2]
        res = max(res, XX)

    return max(res, OX, XO)


if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N % 2 == 0:
        return max(sum(A[::2]), sum(A[1::2]))

    dp = [0] * 4
    for i in range(N // 2):
        newDP = [0] * 4
        ox = A[i * 2]
        xo = A[i * 2 + 1]
        newDP[0] = dp[0] + ox
        newDP[1] = max(dp[1], dp[3]) + ox
        newDP[2] = max(dp[0], dp[2]) + xo
        newDP[3] = max(dp[0], dp[2])
        if i == 0:
            newDP[1] = 0
        dp = newDP.copy()
    else:
        o = A[-1]
        dp[1] += o
        dp[3] += o
    return max(dp)


if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    if N % 2 == 0:
        return max(sum(A[::2]), sum(A[1::2]))

    dp = [0] * 4
    while len(A) >= 2:
        newDP = [0] * 4
        ox = A.pop()
        xo = A.pop()
        newDP[0] = dp[0] + ox
        newDP[1] = max(dp[1], dp[3]) + ox
        newDP[2] = max(dp[0], dp[2]) + xo
        newDP[3] = max(dp[0], dp[2])
        dp = newDP.copy()
    else:
        o = A.pop()
        dp[1] += o
        dp[3] += o
    return max(dp)


if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:

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

    dp = [0] * 5
    while len(A) >= 2:
        newDP = [0] * 5
        ox = A.pop()
        xo = A.pop()
        newDP[0] = dp[0] + ox
        newDP[1] = max(dp[1], dp[4]) + ox
        newDP[2] = max(dp[0], dp[2]) + xo
        newDP[3] = dp[3] + xo
        newDP[4] = max(dp[0], dp[2])
        dp = newDP.copy()
    else:
        o = A.pop()
        dp[1] += o
        dp[3] += o
        dp[4] += o
    return max(dp)


if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:

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

    dp = [0] * 5
    while len(A) >= 2:
        newDP = [0] * 5
        ox = A.pop()
        xo = A.pop()
        newDP[0] = dp[0] + ox
        newDP[1] = max(dp[1], dp[4]) + ox
        newDP[2] = max(dp[0], dp[2]) + xo
        newDP[3] = max(dp[1], dp[3]) + xo
        newDP[4] = max(dp[0], dp[2])
        dp = newDP.copy()
    else:
        o = A.pop()
        dp[1] += o
        dp[3] += o
        dp[4] += o
    return max(dp)


if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
from itertools import chain


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

    dp = [[0]*2 for _ in range(3)]
    A.reverse()
    while len(A) > 1:
        newDP = [[0] * 2 for _ in range(3)]
        ox = A.pop()
        xo = A.pop()
        newDP[0][0] = dp[0][0] + ox
        newDP[0][1] = max(dp[0][1], dp[2][0]) + ox
        newDP[1][0] = max(dp[0][0], dp[1][0]) + xo
        newDP[1][1] = max(dp[0][1], dp[1][1]) + xo
        newDP[2][0] = max(dp[0][0], dp[1][0])
        dp = newDP
    else:
        o = A.pop()
        dp[0][1] += o
        dp[1][1] += o
        dp[2][0] += o

    res = max(dp[0][0], dp[0][1], dp[1][0], dp[1][1], dp[2][0])
    return res


if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
from math import ceil, floor

# dp[a_i番まで見た。a_iを含む][a_i（を含む）までにいくつ採用しているか][i - 1を使ったかどうか] bool


def main():
    n = int(input())
    A = [0] + list(map(int, input().split()))
    dp = {}
    dp[(0, 0)] = 0
    dp[(1, 1)] = A[1]
    dp[(1, 0)] = 0
    for i in range(2, n + 1):
        for j in range(max(floor(n/2) - ceil((n-i)/2), 0), floor(i/2) + 1):
            # a_iを採用する場合
            if (i, j) in dp:
                dp[(i, j)] = max(dp[(i, j)], A[i] + dp[(i - 2, j - 1)]
                                 ) if (i - 2, j - 1) in dp else dp[(i, j)]
            else:
                dp[(i, j)] = A[i] + dp[(i - 2, j - 1)] if (i -
                                                           2, j - 1) in dp else float("inf")*-1
            # a_iを採用しない場合
            if (i - 1, j) in dp:
                dp[(i, j)] = max(dp[(i - 1, j)], dp[(i, j)])

    print(dp[(n, floor(n/2))])
    return


"""
7
0を取ったところ
#######
#0#0#0#
0#0#0##
0#0##0#
0#0###0
##0#0#0

4
0#0#
#0#0
0##0
"""
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def solve1():
    dp=[[-1]*2 for i in range(N+1)]
    dp[0][0]=0;dp[1][0]=A[0];dp[2][1]=A[1]
    for i in range(N):
        if dp[i+1][0]==-1:
            if i-1>=0:
                dp[i+1][0]=max(dp[i+1][0],dp[i-1][0]+A[i])
        if dp[i+1][1]==-1:
            if i-1>=0:
                dp[i+1][1]=max(dp[i+1][1],dp[i-1][1]+A[i])
            if i-2>=0:
                dp[i+1][1]=max(dp[i+1][1],dp[i-2][0]+A[i])
    print(max(dp[N][1],dp[N-1][0]))
    return
def solve2():
    dp=[[-1]*3 for i in range(N+1)]
    dp[0][0]=0;dp[1][0]=A[0];dp[2][1]=A[1];dp[3][2]=A[2]
    for i in range(N):
        if dp[i+1][0]==-1:
            if i-1>=0:
                dp[i+1][0]=max(dp[i+1][0],dp[i-1][0]+A[i])
        if dp[i+1][1]==-1:
            if i-1>=0:
                dp[i+1][1]=max(dp[i+1][1],dp[i-1][1]+A[i])
            if i-2>=0:
                dp[i+1][1]=max(dp[i+1][1],dp[i-2][0]+A[i])
        if dp[i+1][2]==-1:
            if i-1>=0:
                dp[i+1][2]=max(dp[i+1][2],dp[i-1][2]+A[i])
            if i-2>=0:
                dp[i+1][2]=max(dp[i+1][2],dp[i-2][1]+A[i])
            if i-3>=0:
                dp[i+1][2]=max(dp[i+1][2],dp[i-3][0]+A[i])
    print(max(dp[N][2],dp[N-1][1],dp[N-2][0]))
    return

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

if N%2==0:
    solve1()
else:
    solve2()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]

    from collections import defaultdict

    dp = defaultdict(lambda : -float('inf'))
    dp[(0, 0)] = 0
    dp[(1, 0)] = 0
    dp[(1, 1)] = a[0]

    for i in range(2, n + 1):
        max_j = i//2 if i % 2 == 0 else i//2 + 1
        min_j = n//2 - (n - i)//2 if (n - i) % 2 == 0 else n//2 - ((n - i)//2 + 1)
        for j in range(min_j, max_j + 1):
            dp[(i, j)] = max(dp[(i - 2, j)], dp[(i - 2, j - 1)] + a[i - 1])

    ans = -float('inf')
    for i in range(n//2, n + 1):
        ans = max(ans, dp[(i, n//2)])
    
    print(ans)
solve()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]

    from collections import defaultdict

    dp = defaultdict(lambda : -float('inf'))
    dp[(0, 0)] = 0
    dp[(1, 0)] = 0
    dp[(1, 1)] = a[0]

    for i in range(2, n + 1):
        max_j = i//2 if i % 2 == 0 else i//2 + 1
        min_j = n//2 - (n - i)//2 if (n - i) % 2 == 0 else n//2 - ((n - i)//2 + 1)
        for j in range(min_j, max_j + 1):
            dp[(i, j)] = max(dp[(i - 2, j)], dp[(i - 2, j - 1)] + a[i - 1])

    ans = -float('inf')
    for i in range(n//2, n + 1):
        ans = max(ans, dp[(i, 2//n)])
    
    print(ans)
solve()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]

    from collections import defaultdict

    dp = defaultdict(lambda : -float('inf'))
    dp[(0, 0)] = 0
    dp[(1, 0)] = 0
    dp[(1, 1)] = a[0]

    for i in range(2, n + 1):
        max_j = i//2 if i % 2 == 0 else i//2 + 1
        min_j = n//2 - (n - i)//2 if (n - i) % 2 == 0 else n//2 - ((n - i)//2 + 1)
        for j in range(min_j, max_j + 1):
            dp[(i, j)] = max(dp[(i - 2, j)], dp[(i - 2, j - 1)] + a[i - 1])

    print(dp[(n, n//2)])
solve()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]

    from collections import defaultdict

    dp = defaultdict(lambda : -float('inf'))
    dp[(0, 0)] = 0

    for i in range(1, n + 1):
        max_j = i//2 if i % 2 == 0 else i//2 + 1
        min_j = n//2 - (n - i)//2 if (n - i) % 2 == 0 else n//2 - ((n - i)//2 + 1)
        for j in range(min_j, max_j + 1):
            dp[(i, j)] = max(dp[(i - 2, j)], dp[(i - 2, j - 1)] + a[i - 1])
    print(dp[(i, j)])
solve()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]

    from collections import defaultdict

    dp = defaultdict(int)

    for i in range(1, n + 1):
        max_j = i//2 if i % 2 == 0 else i//2 + 1
        min_j = n//2 - (n - i)//2 if (n - i) % 2 == 0 else n//2 - ((n - i)//2 + 1)
        for j in range(min_j, max_j + 1):
            dp[(i, j, 0)] = max(dp[(i - 1, j, 0)], dp[(i - 1, j, 1)])
            dp[(i, j, 1)] = dp[(i - 1, j - 1, 0)] + a[i - 1]

    print(max(dp[(n, n//2, 0)], dp[(n, n//2, 1)]))
solve()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

from collections import defaultdict

dp = defaultdict(int)

for i in range(1, n + 1):
    max_j = i//2 if i % 2 == 0 else i//2 + 1
    min_j = n//2 - (n - i)//2 if (n - i) % 2 == 0 else n//2 - ((n - i)//2 + 1)
    for j in range(min_j, max_j + 1):
        dp[(i, j, 0)] = max(dp[(i - 1, j, 0)], dp[(i - 1, j, 1)])
        dp[(i, j, 1)] = dp[(i - 1, j - 1, 0)] + a[i - 1]
        
print(dp)

Submission status: Wrong Answer

Solution code:
from sys import stdin
n = int(stdin.readline())
nums = list(map(int, stdin.readline().split()))

# Gives TLE
def naive_2D_dp(n, nums):
    # let dp[i][j]: maximum sum of j elements chosen from the first i elements where no two are adjacent.

    # dp[i][j] = max(dp[i-2][j-1] + nums[i], dp[i-1][j]); maximum between selecting the ith element and not selecting it. If we select, we have to use dp[i-2][j-1] to prevent adjacent.

    dp = [[0]*(n//2 + 1) for i in range(n+1)]

    # sum of 0 to select 0 elements
    for i in range(1, n+1):
        dp[i][0] = 0

    # to select one out of one.
    dp[1][1] = nums[0]

    for i in range(1, n+1):
        for j in range(1, i//2 + 1):
            dp[i][j] = max(nums[i-1] + (dp[i-2][j-1] if i>1 and j>0 else 0), dp[i-1][j] if i>0 else 0)

    print(dp[n][n//2])


# Source: https://icode54.blogspot.com/p/dp-1-atcoder-beginner-contest-162.html
def oneD_dp(n, nums):
    # let dp[i] be the maximum sum after picking i/2 elements. Two cases: i is odd, i is even. In both we choose the max from selecting i, and not selecting i.


    # Case 1) i is even (pick exactly i/2 elements): dp[i] = max(dp[i-2] + nums[i], odd indices sum). 
    # 1 2 3 4 5 6. If you pick 6 (i) you check the max of (i-2). If you don't pick 6, to pick i/2 elements you ave to pick the odd indices : 1, 3, 5.

    # Case 2) i is odd (i/2 is same as (i-1)/2 if we don't pick): dp[i] = max(dp[i-2] + nums[i], dp[i-1])

    # odd indices prefix sum needed for even case.
    oddpref = [0]*(n+1)
    oddpref[1] = nums[0]

    for i in range(2, n+1, 2):
        if (i+1)%2:
            oddpref[i] += oddpref[i-2] + nums[i-1]
    
    dp = [0]*(n+1)
    dp[0] = 0
    dp[1] = 0
    for i in range(2, n+1):
        if i%2 == 0:
            dp[i] = max(dp[i-2] + nums[i-1], oddpref[i-1])
        else:
            dp[i] = max(dp[i-2] + nums[i-1], dp[i-1])
    print(dp[n])

oneD_dp(n, nums)

Submission status: Wrong Answer

Solution code:
from sys import stdin
n = int(stdin.readline())
nums = list(map(int, stdin.readline().split()))

# Gives TLE
def naive_2D_dp(n, nums):
    # let dp[i][j]: maximum sum of j elements chosen from the first i elements where no two are adjacent.

    # dp[i][j] = max(dp[i-2][j-1] + nums[i], dp[i-1][j]); maximum between selecting the ith element and not selecting it. If we select, we have to use dp[i-2][j-1] to prevent adjacent.

    dp = [[0]*(n//2 + 1) for i in range(n+1)]

    # sum of 0 to select 0 elements
    for i in range(1, n+1):
        dp[i][0] = 0

    # to select one out of one.
    dp[1][1] = nums[0]

    for i in range(1, n+1):
        for j in range(1, i//2 + 1):
            dp[i][j] = max(nums[i-1] + (dp[i-2][j-1] if i>1 and j>0 else 0), dp[i-1][j] if i>0 else 0)

    print(dp[n][n//2])


# Source: https://icode54.blogspot.com/p/dp-1-atcoder-beginner-contest-162.html
def oneD_dp(n, nums):
    # let dp[i] be the maximum sum after picking i/2 elements. Two cases: i is odd, i is even. In both we choose the max from selecting i, and not selecting i.


    # Case 1) i is even (pick exactly i/2 elements): dp[i] = max(dp[i-2] + nums[i], odd indices sum). 
    # 1 2 3 4 5 6. If you pick 6 (i) you check the max of (i-2). If you don't pick 6, to pick i/2 elements you ave to pick the odd indices : 1, 3, 5.

    # Case 2) i is odd (i/2 is same as (i-1)/2 if we don't pick): dp[i] = max(dp[i-2] + nums[i], dp[i-1])

    # odd indices prefix sum needed for even case.
    oddpref = [0]*(n+1)
    oddpref[1] = nums[0]

    for i in range(2, n):
        if (i+1)%2:
            oddpref[i] += oddpref[i-2] + nums[i]
    
    dp = [0]*(n+1)
    dp[0] = 0
    dp[1] = 0
    for i in range(2, n+1):
        if i%2 == 0:
            dp[i] = max(dp[i-2] + nums[i-1], oddpref[i-1])
        else:
            dp[i] = max(dp[i-2] + nums[i-1], dp[i-1])
    print(dp[n])

oneD_dp(n, nums)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dp=defaultdict(int)

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

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dp=defaultdict(int)

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