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: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()

if N%2 == 0:
  B = [0]
  W = [0]
  for i in range(N//2):
    B.append(B[-1]+A[i*2])
  for i in range(N//2):
    W.append(W[-1]+A[N-1-i*2])
  ans = [B[i]+W[N//2-i] for i in range(N//2+1)]
  print(max(ans))
else:
  A.append(-INF)
  dp = [[0,0,0,0] for i in range(N//2+2)]
  for i in range(N//2+1):
    a,b = A[i*2],A[i*2+1]
    dp[i+1][0] = dp[i][0] + a
    dp[i+1][1] = max(dp[i][0],dp[i][1]) + b
    dp[i+1][2] = max(dp[i][0],dp[i][1])
    if i != 0:
      dp[i+1][3] = max(dp[i][2],dp[i][3]) + a
  print(max(dp[-1][1:]))

Submission status: Accepted

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()

def odd(A):
    oddi=np.array(A[::2],dtype=np.int64)
    eveni=np.array(A[1::2],dtype=np.int64)
    left=np.cumsum(oddi[:-1]-eveni)
    left=np.insert(left,0,0)
    left=np.append(left,0)
    right=np.cumsum(oddi[:0:-1]-eveni[::-1])[::-1]
    right=np.insert(right,0,0)
    right=np.append(right,0)
    tmp=np.max(np.maximum.accumulate(left)+right)
    return tmp+np.sum(eveni)

def even(A):
    left=np.array([0]+A[::2],dtype=np.int64)
    right=np.array(A[1::2]+[0],dtype=np.int64)[::-1]
    return np.max(left.cumsum()+right.cumsum()[::-1])

def main():
    n=int(input())
    A=list(map(int, input().split()))
    if n%2==1:
        print(odd(A))
    else:
        print(even(A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

            dp[i+1][1] = max(dp[i][0], dp[i][1]) + A[2*i+1]

        print(max(dp[-1]))
    else:
        dp = [[0]*3 for _ in range(N//2 + 1)]
        for i in range(N//2):
            dp[i+1][0] = dp[i][0] + A[2*i]

            dp[i+1][1] = max(dp[i][0], dp[i][1]) + A[2*i+1]

            dp[i+1][2] = max(dp[i][0], dp[i][1], dp[i][2]) + A[2*i+2]

        print(max(dp[-1]))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

C = [0 for _ in range(N)] #奇数個、余裕あり
D = [0 for _ in range(N)] #偶数個
E = [0 for _ in range(N)] #奇数個、余裕なし

E[0] = a[0]

for i in range(1,N):
  if i % 2 == 0:#奇数個
    C[i] = max(C[i-2]+a[i],D[i-1])
    E[i] = E[i-2] + a[i]
  else:
    D[i] = max(D[i-2]+a[i],E[i-1])

if N % 2 == 0:
  print(D[N-1])
else:
  print(C[N-1])
  
#print(C)
#print(D)
#print(E)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	n=II()
	A=LI()

	X=[-10**10]*(n+1)
	Y=[-10**10]*(n+1)
	X[0]=0
	Y[1]=A[0]
	X[1]=0

	for i in range(2,n+1):
		if i%2==0:
			X[i]=max(Y[i-1],X[i-2]+A[i-1])
		else:
			X[i]=max(X[i-1],X[i-2]+A[i-1])
			Y[i]=Y[i-2]+A[i-1]
	print(X[n])




















if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
P,M,A,I=input,max,int,-10**9
n,a=A(P()),list(map(A,P().split()))
x,y,z=0,I,I
for i,L in enumerate(a):
 if i%2:z=M(y,z);y+=L
 else:y=M(x,y);x+=L;z+=L
print(M(y,z)if n%2else M(x,y))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
if N%2 == 0:
  dp = [[0]*2 for _ in range(N)] #0index
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  for i in range(2,N):
    dp[i][0] = dp[i-2][0]+A[i]
    if i-3>=0:
      dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
    else:
      dp[i][1] = max(dp[i-2][1],0)+A[i]
  ans = max(dp[-2][0],dp[-1][1])
  print(ans)
#i個目を使ってj(0-2)回多く飛んでいる。
else: #N%2 == 1:
  dp = [[0]*3 for _ in range(N)] #0index
  dp[0][0] = A[0]
  dp[1][1] = A[1]
  dp[2][2] = A[2]
  dp[2][0] = A[0]+A[2]
  #print(dp)
  for i in range(3,N):
    dp[i][0] = dp[i-2][0]+A[i]
    if i-3 >= 0:
      dp[i][1] = max(dp[i-2][1],dp[i-3][0])+A[i]
    else:
      dp[i][1] = max(dp[i-2][1],0)+A[i]
    if i-4 >= 0:
      dp[i][2] = max(dp[i-2][2],dp[i-3][1],dp[i-4][0])+A[i]
    elif i-3 >= 0:
      dp[i][2] = max(dp[i-2][2],dp[i-3][1],0)+A[i]
  #else:
  #  dp[i][2] = max(dp[i-2][2],0,0)+A[i]
  #print(dp[-1],dp[-2],dp[-3])

  ans = max(dp[-3][0],dp[-2][1],dp[-1][2])
  print(ans)
  exit()

Submission status: Accepted

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

if n%2 == 1:
    dp = [ [0]*4 for _ in range(n//2+1) ] 

    for i in range(n//2):
        dp[i+1][0] = dp[i][0] + al[i*2]
        dp[i+1][1] = max(dp[i][1]+al[i*2+1], dp[i][0]+al[i*2+1])
        dp[i+1][2] = max(dp[i][2]+al[i*2+2], dp[i][0]+al[i*2+2])
        dp[i+1][3] = max(dp[i][3]+al[i*2+2], dp[i][1]+al[i*2+2])
    ans = max(dp[-1])
    print(ans)

else:
    dp = [ [0]*2 for _ in range(n//2+1) ] 
    for i in range(n//2):
        dp[i+1][0] = dp[i][0] + al[i*2]
        dp[i+1][1] = max(dp[i][1]+al[i*2+1], dp[i][0]+al[i*2+1])
    ans = max(dp[-1])
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

N = int(input())
a = [0] + list(map(int, input().split()))

o = [a[2*i+1] for i in range(N//2)]
o = list(itertools.accumulate(o))

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

dp[0] = dp[1] = 0
dp[2] = max(a[1], a[2])
if N > 2: dp[3] = max([a[1], a[2], a[3]])

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

print(dp[N])

Submission status: Accepted

Solution code:

def resolve():
    INF = float("-inf")
    N = int(input())
    A = list(map(int, input().split()))

    skip = 1 + N % 2
    # i番目までの要素を見たときに、ｊ個選ばない時の最大値
    dp = [[INF] * (skip + 2) for _ in range(N + 1)]
    dp[0][0] = 0

    for i in range(N):
        for j in range(skip + 1):  # j: スキップする個数
            # 今見ている要素をスキップ
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
            now = dp[i][j]
            if (i + j) % 2 == 0:
                now += A[i]
            dp[i + 1][j] = max(dp[i + 1][j], now)

    print(dp[N][skip])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import copy

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

k = 1 + n%2
INF = 10**18
dp = [[-INF]*4 for i in range(n+5)]
dp[0][0] = 0

for i in range(n):
    for j in range(k+1):
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j])
        now = copy.deepcopy(dp[i][j])
        if (i+j) % 2 == 0:
            now += a[i]
        dp[i+1][j] = max(dp[i+1][j], now)
print(dp[n][k])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

x, y, z = A[0], A[1], 0
for i in range(2, N):
    if i % 2 == 0:
        z = z + A[i]
        y = max(y, x)
        x = x + A[i]
    else:
        z = max(y, z)
        y = y + A[i]
        x = x

if N % 2 == 0:
    print(max(x, y))
else:
    print(max(y, z))

Submission status: Accepted

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()

if n==2:
    print(max(a))
    exit()

dp=[[-inf]*3for i in range(n)]
dp[0][0]=a[0]
dp[1][1]=a[1]
dp[2][2]=a[2]
N=(n)//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 and (i)//2<=N]+[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 and (i+1)//2<=N]+[dp[i][1]])
    dp[i][0]=max([dp[i-2-j][j]+a[i] for j in range(1) if i-2-j>=0 and (i+1+1)//2<=N]+[dp[i][0]])

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

Submission status: Accepted

Solution code:
def main():
    import sys
    import numpy as np
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    a = list(map(int, input().split()))
    inf = 1e18
    k = n%2 + 1
    dp = np.full((n+1, k+2), -inf, dtype=int)
    dp[0,0] = 0
    for i in range(n):
        for j in range(k+1):
            dp[i+1, j+1] = max(dp[i+1,j+1],dp[i,j])
            now = dp[i,j]
            if (i+j)%2 == 0: now += a[i]
            dp[i+1,j] = max(dp[i+1,j],now)
    print(dp[n,k])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    INF = 10 ** 18
    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: Accepted

Solution code:
from itertools import accumulate
N, *A = map(int, open(0).read().split())

INF = 1 << 60
dp = [[-INF]*2 for _ in [0]*N]
dp[0][0] = 0

if N & 1:
    for i, a in enumerate(A):
        for j in range(i//2+1, i//2-1, -1):
            dp[j][0] = max(dp[j][0], dp[j][1])
            if j > 0:
                dp[j][1] = dp[j-1][0] + a
else:
    for i, a in enumerate(A):
        for j in range(i//2+1, (i+1)//2-1, -1):
            dp[j][0] = max(dp[j][0], dp[j][1])
            dp[j][1] = dp[j-1][0] + a

print(max(dp[N//2]))

Submission status: Accepted

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: Accepted

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 = -(10**18)
for ((cnt, _), value) in DP.items():
    if cnt == N//2:
        res = max(res, value)
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
INF = 10 ** 18
# -2 -1 0 1
#dp_use 見ている文字を使った dp_not_use 見ている文字を使わない
dp_use = [-INF] * 4
dp_not_use = [-INF] * 4
dp_not_use[0] = 0

for a in A:
    tmp_use = [-INF] * 4
    tmp_not_use = [-INF] * 4
    for current_diff in range(-2,2):
        if current_diff - 1 >= -2:
            tmp_use[current_diff] = dp_not_use[current_diff-1] + a
        if current_diff + 1 < 2:
            tmp_not_use[current_diff] = max(dp_use[current_diff+1],dp_not_use[current_diff+1]) 
    dp_use = tmp_use
    dp_not_use = tmp_not_use

diff = -1 + (N+1) % 2 
print(max(dp_use[diff],dp_not_use[diff]))

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

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

for i, a in enumerate(A, start=1):
    j = i // 2
    for x in range(j - 1, j + 2):
        dp[(i, x, 0)] = max(dp[(i - 1, x, 0)], dp[(i - 1, x, 1)])
        dp[(i, x, 1)] = dp[(i - 1, x - 1, 0)] + a

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

Submission status: Accepted

Solution code:
import numpy as np
import itertools

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

if N%2==0:
    left = np.cumsum([0]+A[::2])
    right = np.cumsum([0]+A[::-2])[::-1]
    ans = max(left+right)
else:
    left = np.cumsum([0] + A[:-1:2])
    mid_left = np.cumsum([0]+A[-2::-2])[::-1]
    mid_right = np.cumsum([0]+A[1::2])
    right = np.cumsum([0] + A[:1:-2])[::-1]

    left_sum = left+mid_left
    left_max = np.zeros(N//2+1, dtype=int)
    left_max[0] = left_sum[0]
    for i in range(1, N//2+1):
        left_max[i] = max(left_max[i-1], left_sum[i])
    left_max -= mid_left

    right_sum = right + mid_right
    right_max = np.zeros(N//2 + 1, dtype=int)
    right_max[-1] = right_sum[-1]
    for i in range(N//2-1, -1, -1):
        right_max[i] = max(right_max[i + 1], right_sum[i])
    right_max -= mid_right

    ans = max(left_max+right_max)


print(ans)

Submission status: Accepted

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(1, 3):
        for k in range(2):
            if k == 0 and j == 2:
                continue
            res = max(res, dp[N][j][k])

    print(res)

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from itertools import product
import sys
INF = 10**16
def main(N, A):
    dp = [[[-INF] * 2 for __ in range(3)] for _ in range(N + 1)]
    dp[0][1][0] = dp[0][2][0] = 0
    for i in range(1, N + 1):
        pi = ((i - 1) // 2 - 1, (i - 1) // 2, i // 2)
        ni = (i // 2 - 1, i // 2, (i + 1) // 2)
        for pii, nii, pk, nk in product(range(3), range(3), range(2), range(2)):
            pj, nj = pi[pii], ni[nii]
            if pj > nj or pj + 2 <= nj: continue
            if pj == nj and nk == 1: continue
            if pj < nj and nk == 0: continue
            if pk == 1 and nk == 1: continue
            if dp[i - 1][pii][pk] == -INF: continue
            dp[i][nii][nk] = max(dp[i][nii][nk], dp[i - 1][pii][pk] + (A[i - 1] if nk == 1 else 0))
    ans = -INF
    for k in range(2):
        ans = max(ans, dp[N][1][k])
    print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
inf = 10**18

x = N % 2 + 1
dp = [[-inf] * 4 for _ in range(N + 10)]
dp[0][0] = 0
for i, a in enumerate(A):
    for j in range(x + 1):
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j])
        now = dp[i][j]
        if (i + j) % 2 == 0:
            now += a
        dp[i + 1][j] = max(dp[i + 1][j], now)

print(dp[N][x])

Submission status: Accepted

Solution code:
from math import ceil, floor

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


def dp(i, j):
    if (i, j) in memo:
        return memo[(i, j)]
    else:
        return float("inf")*-1


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

    print(dp(n, floor(n/2)))
    return
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
INF=float('inf')
def solve1():
    dp=[[-INF]*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]==-INF:
            if i-1>=0:
                dp[i+1][0]=max(dp[i+1][0],dp[i-1][0]+A[i])
        if dp[i+1][1]==-INF:
            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=[[-INF]*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]==-INF:
            if i-1>=0:
                dp[i+1][0]=max(dp[i+1][0],dp[i-1][0]+A[i])
        if dp[i+1][1]==-INF:
            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]==-INF:
            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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    dp=[0 for _ in range(N+1)]
    dp[1]=0
    x=A[0]
    for i,a in enumerate(A[1:],2):
        if i%2!=0:
            dp[i]=max(a+dp[i-2],dp[i-1])
            x+=a
            continue
        dp[i]=max(a+dp[i-2],x)
    print(dp[-1])





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = list(map(int,input().split()))
dp = np.full((2, n//2 + 1), -10**18, dtype=np.int64)
"""
dp[i][j] := iは偶奇, jは何個決めるか
"""
dp[0][0] = 0
dp[1][0] = 0
for i in range(n):
	k = i % 2
	for j in [2, 1, 0]:
		if i//2+j <= n//2:
			if i//2-1+j >= 0:
				dp[k][i//2+j] = np.maximum(dp[1-k][i//2+j], dp[k][i//2-1+j]+a[i])

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