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:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
import random

# sys.stdin = open('input')

def inp():
    re = map(int, raw_input().split())
    if len(re) == 1:
        return re[0]
    return re

def inst():
    return raw_input().strip()

def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x

def get(n, da):
    mx = 0
    for i in range(n):
        if i%2==1:
            mx += da[i]
    st = [0 for i in range(n)]
    dp = [0 for i in range(n)]
    st[0]=1
    dp[0]=da[0]
    for i in range(2,n):
        if i%2==0:
            st[i]=1
            dp[i]=dp[i-2]+da[i]
        else:
            st[i]=1
            dp[i] = dp[i-3]+da[i]
            if st[i-2]:
                dp[i] = max(dp[i], dp[i-2]+da[i])
    return max(mx, max(dp[n-1], dp[n-2]))

def my_main():
    n = inp()
    da = inp()
    if n%2==0:
        print get(n, da)
    else:
        nda = [da[i] for i in range(n) if i%2==0]
        mx = sum(nda) - min(nda)
        mx = max(mx, max(get(n-1, da[1:]), get(n-1, da[:-1])))
        st = [[0 for i in range(n)]for i in range(3)]
        dp = [[0 for i in range(n)]for i in range(3)]
        st[0][0]=1
        dp[0][0]=da[0]
        for i in range(2,n):
            if st[0][i-2]:
                st[0][i] = 1
                dp[0][i] = dp[0][i-2] + da[i]
            if i-3 >= 0 and st[0][i-3]:
                st[1][i] = 1
                dp[1][i] = dp[0][i-3] + da[i]
            if st[1][i-2]:
                st[1][i] = 1
                dp[1][i] = max(dp[1][i], dp[1][i-2] + da[i])
            if i-3>=0 and st[1][i-3]:
                st[2][i] = 1
                dp[2][i] = dp[1][i-3] + da[i]
            if st[2][i-2]:
                if st[2][i]:
                    dp[2][i] = max(dp[2][i], dp[2][i-2]+da[i])
                else:
                    st[2][i] = 1
                    dp[2][i] = dp[2][i-2]+da[i]
        print max(mx, dp[2][n-1])







my_main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
dp = [[0] * 4 for _ in range(200005)]
k = 1 + N % 2
for i in range(N + 1):
    for j in range(k + 1):
        dp[i][j] = - float('inf')
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)
ans = dp[N][k]
print(ans)

Submission status: Accepted

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


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


n = I()
A = LI()
dp = [[defaultdict(lambda:-INF) for _ in range(2)] for _ in range(n + 1)]
dp[0][0][0] = 0
for i in range(n):
    for j in range(2):
        for k, e in dp[i][j].items():
            if i // 2 <= k <= i // 2 + 1:
                dp[i + 1][0][k] = max(dp[i + 1][0][k], e)
            if i // 2 <= k + 1 <= i // 2 + 1 and j == 0:
                dp[i + 1][1][k + 1] = max(dp[i + 1][1][k + 1], e + A[i])

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

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
a=[int(i) for i in input().split()]
INF=float('inf')
dp0=defaultdict(lambda: -INF)
dp1=defaultdict(lambda: -INF)
dp0[(0,0)]=0
for i in range(1,n+1):
  for j in range(i//2-1,(i+1)//2+1):
    dp0[(i,j)]=max(dp0[(i-1,j)],dp1[(i-1,j)])
    dp1[(i,j)]=dp0[(i-1,j-1)]+a[i-1]
print(max(dp0[(n,n//2)],dp1[(n,n//2)]))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
INF = 1001001001001001
c = n//2
dp = [[-INF]*3 for _ in range(c+1)]
dp[0][0] = 0
for i in range(c+1):
    for j in range(3):
        for k in range(3):
            if i+1<=c and j+k<3 and 2*i+j+k<n:
                dp[i+1][j+k] = max(dp[i+1][j+k], dp[i][j]+a[2*i+j+k])

ans = -INF

for i in range(3):
    ans = max(ans,dp[c][i])

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
inf = -float('inf')
a = list(map(int, readline().split())) + [inf] * 2
dp = [[inf] * 3 for _ in range(n + 4)]
for i in range(3):
    dp[0][i] = 0
for i, (bf, aa, af) in enumerate(zip(a, a[1:], a[2:])):
    dp[i + 4][2] = max(dp[i + 4][2], dp[i][0] + af)
    for j in range(1, 3):
        dp[i + 3][j] = max(dp[i + 3][j], dp[i][j - 1] + aa)
    for j in range(3):
        if dp[i + 2][j] != inf or j == 0:
            dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + bf)
if n % 2 == 0:
    print(max(dp[n + 1][1], dp[n][0]))
else:
    print(max(dp[n + 1][2], dp[n][1], dp[n - 1][0]))

Submission status: Accepted

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

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

dp = [0]*n
c = a[0]
dp[1] = max(a[0],a[1])

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

print(dp[-1])

Submission status: Accepted

Solution code:
import sys

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

INF = 10**20
dp = [[[-INF]*2 for _ in range(2)] for _ in range(N+1)]


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

        else:
            dp[i+1][0][0] = max(dp[i][1][0], dp[i][1][1])
            dp[i+1][0][1] = dp[i][0][0] + A[i]
            dp[i+1][1][1] = dp[i][1][0] + A[i]

    ans = max(dp[N][0][0], dp[N][0][1])            

else:
    dp[0][1][0] = 0
    for i in range(N):
        if i&1:
            dp[i+1][1][0] = dp[i][1][1]
            dp[i+1][1][1] = dp[i][0][0] + A[i]            

        else:
            dp[i+1][0][0] = max(dp[i][1][0], dp[i][1][1])
            dp[i+1][1][1] = dp[i][1][0] + A[i]
    ans = max(dp[N][1][0], dp[N][1][1])

print(ans)

Submission status: Accepted

Solution code:
INF = 10**18

def solve(n, a):
    # 現在の位置 x 選んだ個数 x 直前を選んだかどうか
    dp = [{j: [-INF, -INF] for j in range(i//2-1, (i+1)//2 + 1)} for i in range(n+1)]
    dp[0][0][False] = 0
    for i in range(n):
        for j in dp[i].keys():
            if (j+1) in dp[i+1]:
                dp[i+1][j+1][True] = max(dp[i+1][j+1][True], dp[i][j][False] + a[i])
            if j in dp[i+1]:
                dp[i+1][j][False] = max(dp[i+1][j][False], dp[i][j][False])
                dp[i+1][j][False] = max(dp[i+1][j][False], dp[i][j][True])
    return max(dp[n][n//2])

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

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    dp = [[[-float("inf")]*2 for j in range(3)] for i in range(n+1)]
    #dp[index][i//2+j個選んだ][直前の値を採用したか否か]
    dp[0][0][0] = 0
    for i in range(n):
        x = a[i]
        if i%2 == 0:
            for j in range(-1, 2):
                dp[i+1][j][0] = max(dp[i][j][0], dp[i][j][1])
            for j in range(-1, 1):
                dp[i+1][j+1][1] = dp[i][j][0] + x
        else:
            for j in range(-1, 1):
                dp[i+1][j][0] = max(dp[i][j+1][0], dp[i][j+1][1])
            for j in range(-1, 2):
                dp[i+1][j][1] = dp[i][j][0] + x
    print(max(dp[n][0][0], dp[n][0][1]))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

dp = [0]*n
ep = [0]*n

dp[1] = max(a[:2])
dp[2] = max(a[:3])

ep[1] = a[0]
ep[2] = max(a[:2])

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

print(dp[-1])

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
dp=[0]#dp[i]=左からi番目までで(i//2)個選んだときの最大値
sum_odd=a[0]

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

Submission status: Accepted

Solution code:
import sys
input=lambda :sys.stdin.readline().rstrip()

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

k = 1+n%2
f_inf = float('inf')

dp = [[-f_inf for _ in range(4)] for _ in range(200005)]
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)

ans = dp[n][k]
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
m=n//2
if n%2==0:
    dp=[[-10**18]*2 for _ in range(m)]
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    for i in range(1,m):
        for j in range(2*i,2*(i+1)):
            for k in range(2*(i-1),2*i):
                if j-k>1:
                    dp[i][j%2]=max(dp[i][j%2],dp[i-1][k%2]+a[j])
else:
    dp=[[-10**18]*3 for _ in range(m)]
    dp[0][0]=a[0]
    dp[0][1]=a[1]
    dp[0][2]=a[2]
    for i in range(1,m):
        for j in range(2*i,2*(i+1)+1):
            for k in range(2*(i-1),2*i+1):
                if j-k>1:
                    dp[i][j-2*i]=max(dp[i][j-2*i],dp[i-1][k-2*(i-1)]+a[j])
print(max(dp[-1]))

Submission status: Accepted

Solution code:
from collections import defaultdict
N,*A = map(int, open(0).read().split())
dp_not = defaultdict(lambda :-10**18)
dp_take = defaultdict(lambda :-10**18)
dp_not[(0,0)] = 0
for i,x in enumerate(A,1):
  for j in range(N//2-(N-i+1)//2,(i+1)//2+1):
    dp_not[(i,j)] = max(dp_not[(i-1,j)],dp_take[(i-1,j)])
    dp_take[(i,j)] = dp_not[(i-1,j-1)] + x
print(max(dp_not[(N,N//2)], dp_take[(N,N//2)]))

Submission status: Accepted

Solution code:
from collections import defaultdict
N,*A = map(int, open(0).read().split())
dp_not = defaultdict(lambda :-10**18)
dp_take = defaultdict(lambda :-10**18)
dp_not[(0,0)] = 0
for i,x in enumerate(A,1):
  for j in ((i-1)//2,(i-1)//2+1):
    dp_not[(i,j)] = max(dp_not[(i-1,j)],dp_take[(i-1,j)])
    dp_take[(i,j)] = dp_not[(i-1,j-1)] + x
print(max(dp_not[(N,N//2)], dp_take[(N,N//2)]))

Submission status: Accepted

Solution code:
from collections import defaultdict

n=int(input())
a=list(map(int,input().split()))
#n=2*pow(10,5)
#a=range(1,pow(10,5)+1)
# dp[i][j]:i番目の数字の中からj個数字を取った時の最大。(i//2)-1<=j<=(i+1)//2
# 求めるのはdp[n][n//2]
dp=defaultdict(lambda:-pow(10,18))
dp[(1,1)]=a[0]
for i in range(2,n+1): #i番目の数字はa[i-1]
      for j in range(i//2-1,(i+1)//2+1):
            if j==1:
                  dp[(i,j)]=max(dp[(i-1,1)],a[i-1])
            elif j==0:
                  dp[(i,j)]=0
            else:
                  dp[(i,j)]=max(dp[(i-2,j-1)]+a[i-1],dp[(i-1,j)])
print(dp[(n,n//2)])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

DP = defaultdict(lambda: -10**18)

DP[(0,0)] = A[0]

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

print(DP[(N-1,N//2-1)])

Submission status: Accepted

Solution code:
N = int(input())
K = N % 2 + 1
A = tuple(map(int, input().split()))
table = [[-float("inf")] * (K + 2) for _ in range(N + 1)]
table[0][0] = 0
for i in range(N):
    for j in range(K + 1):
        table[i + 1][j] = max(table[i][j] + (A[i] if not (i + j) % 2 else 0), table[i + 1][j])
        table[i + 1][j + 1] = max(table[i][j], table[i + 1][j + 1])
print(table[N][K])

Submission status: Accepted

Solution code:
# for #!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict

def main():
	# for t in range(int(input())):
	n = int(input())
	l = [int(j) for j in input().split()]
	dp = dict()
	dp[0,0] = 0
	dp[2,1] = max(l[0], l[1])
	dp[1,1] = l[0]
	dp[2,2] = -1e14
	dp[1, 0] = 0
	for i in range(3,n+1):
		for j in [(i//2), (i+1)//2]:
			# print(i, j)
			# if (i+j)%2==1:
			dp[i, j] = dp[i-2, j-1]+l[i-1]
			if i>=2*j:
				dp[i, j] = max(dp[i-2, j-1]+l[i-1], dp[i-1, j])				
				
			# else:
			# dp[i, j] = dp[i-2, j-1]+l[i-1]

			# if dp[i, j]
	print(dp[n, (n)//2])
		


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = "x" in file.mode or "r" not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b"\n") + (not b)
			ptr = self.buffer.tell()
			self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode("ascii"))
		self.read = lambda: self.buffer.read().decode("ascii")
		self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
	main()

Submission status: Accepted

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    INF = -10**15
    
    dp = [[[INF,INF],[False,False]] for _ in range(N)]
    dp[0][0][0],dp[0][0][1],dp[0][1][1] = 0,a[0],True
    dp[1][0][0] = 0
    if a[0] < a[1]:
        dp[1][0][1],dp[1][1][1] = a[1],True
    else:
        dp[1][0][1] = a[0]
    
    for i in range(2,N):
        if i%2 != 0:
            dp[i][0][0] = dp[i-1][0][0]
            if dp[i][0][0] < dp[i-2][0][0]+a[i]:
                dp[i][0][0] = dp[i-2][0][0]+a[i]
                dp[i][1][0] = True
            dp[i][0][1] = dp[i-1][0][1]
            if dp[i-1][1][0] == False:
                if dp[i][0][1] < dp[i-1][0][0]+a[i]:
                    dp[i][0][1] = dp[i-1][0][0]+a[i]
                    dp[i][1][1] = True
            if dp[i][0][1] < dp[i-2][0][1]+a[i]:
                dp[i][0][1] = dp[i-2][0][1]+a[i]
                dp[i][1][1] = True
        else:
            dp[i][0][0] = dp[i-1][0][1]
            if dp[i-1][1][0] == False:
                if dp[i][0][0] < dp[i-1][0][0]+a[i]:
                    dp[i][0][0] = dp[i-1][0][0]+a[i]
                    dp[i][1][0] = True
            if dp[i][0][0] < dp[i-2][0][0]+a[i]:
                dp[i][0][0] = dp[i-2][0][0]+a[i]
                dp[i][1][0] = True
            dp[i][0][1] = dp[i-2][0][1]+a[i]
            if dp[i-1][1][1] == False:
                if dp[i][0][1] < dp[i-1][0][1]+a[i]:
                    dp[i][0][1] = dp[i-1][0][1]+a[i]
            dp[i][1][1] = True
    
    if N%2 == 0:
        print(dp[-1][0][1])
    else:
        print(dp[-1][0][0])
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
n=int(input())
a=list(map(int, input().split()))
dp=[0]*n
dp[0]=0
dp[1]=max(a[0],a[1])
curr=a[0]
for i in range(2,n):
  if i&1==1:
    curr+=a[i-1]
    dp[i]=max(curr,dp[i-2]+a[i])
  else: dp[i]=max(dp[i-2]+a[i],dp[i-1])
print(dp[n-1])

Submission status: Accepted

Solution code:
n=int(input())
a = list(map(int,input().split()))
x0,x1,x2,o0,o1,o2=a[0],-10**18,0,-10**18,a[1],-10**18
for i in a[2:]:
  x0,x1,x2,o0,o1,o2=o0,max(o1,x0),max(o2,x1),x0+i,x1+i,x2+i
print(max(x0,x1,o1)if n%2==0 else max(x1,x2,o2))

Submission status: Accepted

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

# oを選択 xを非選択とする　左から見て
# oxoxoxoxoxo に x を1つか2つ挿入することを考える
# 状態を4つ設定 (最後がxかoか)(挿入ずみのxの数)の形式でやる
#a=[1,2,3,4,5,6,7]
#n=len(a)
x0,x1,x2,o0,o1,o2=a[0],-10**18,0,-10**18,a[1],-10**18
for i in a[2:]:
    x0,x1,x2,o0,o1,o2=o0,max(o1,x0),max(o2,x1),x0+i,x1+i,x2+i
if n%2==0:
    print(max(x0,x1,o1))
else:
    print(max(x1,x2,o2))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
iseven=(n%2==0)

if n==2:
    print(max(a))
    exit()
dp = [[-float("inf") for _ in range(3)] for _ in range(n)]
dp[0][0]=a[0]
dp[1][1]=a[1]
if n>2:
    dp[2][2]=a[2]

for i in range(n):
    for k in range(3):
        if i+2<n:
            dp[i+2][k] = max(dp[i+2][k], dp[i][k] + a[i+2])
        if k<=1 and i+3<n:
            dp[i+3][k+1] = max(dp[i+3][k+1], dp[i][k] + a[i+3])
        if not iseven and k==0 and i+4<n:
            dp[i+4][k+2] = max(dp[i+4][k+2], dp[i][k] + a[i+4])


if iseven:
    ans=max([dp[-1][0],dp[-1][1]])
else:
    ans=max([dp[-3][0],dp[-2][1],dp[-1][2]])
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
if n%2==0:
    ans1=A[0];ans2=A[1]
    for i in range((n-2)//2):
        ans2 = max(ans1,ans2)+A[(i+1)*2+1]
        ans1 = ans1++A[(i+1)*2]
    print(max([ans1,ans2]))

else:
    ans1,ans2,ans3,=A[0],A[1],A[2]
    for i in range((n-2)//2):
        ans3 = max(ans3,ans2) + A[(i+2)*2]
        ans2 = max(ans1,ans2) + A[(i+2)*2-1]
        ans1 = ans1 + A[(i+1)*2]
    print(max([ans1,ans2,ans3]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    INF = float("inf")

    N, *A = map(int, open(0).read().split())

    dp_in = defaultdict(lambda: -INF)

    dp_out = defaultdict(lambda: -INF)
    dp_out[(0, 0)] = 0

    for i, a in enumerate(A, 1):
        p = i // 2
        for j in [p - 1, p, p + 1]:
            dp_in[(i, j)] = a + dp_out[(i - 1, j - 1)]
            dp_out[(i, j)] = max(dp_in[(i - 1, j)], dp_out[(i - 1, j)])

    print(max(dp_in[(N, N // 2)], dp_out[(N, N // 2)]))

main()

Submission status: Accepted

Solution code:
from collections import defaultdict

INF = float("inf")

N, *A = map(int, open(0).read().split())

dp_in = defaultdict(lambda: -INF)

dp_out = defaultdict(lambda: -INF)
dp_out[(0, 0)] = 0

for i, a in enumerate(A, 1):
    p = i // 2
    for j in [p - 1, p, p + 1]:
        dp_in[(i, j)] = a + dp_out[(i - 1, j - 1)]
        dp_out[(i, j)] = max(dp_in[(i - 1, j)], dp_out[(i - 1, j)])

print(max(dp_in[(N, N // 2)], dp_out[(N, N // 2)]))

Submission status: Accepted

Solution code:
from collections import defaultdict

INF = float("inf")

N, *A = map(int, open(0).read().split())

dp = defaultdict(lambda: -INF)
dp[(0, 0, False)] = 0

for i, a in enumerate(A, 1):
    p = i // 2
    for j in [p - 1, p, p + 1]:
        dp[(i, j, True)] = a + dp[(i - 1, j - 1, False)]
        dp[(i, j, False)] = max(dp[(i - 1, j, False)], dp[(i - 1, j, True)])

print(max(dp[(N, N // 2, True)], dp[(N, N // 2, False)]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    a = LI()
    if n == 3:
        print(max(a))
        return
    dp = [[-inf] * 3 for i in range(n + 1)]
    dp[0] = [0, 0, 0]
    dp[1][0] = a[0]
    dp[2][1] = a[1]
    for i in range(3, n+1):
        dp[i][0] = dp[i - 2][0] + a[i-1]
        dp[i][1] = max(dp[i - 2][1], dp[i - 3][0]) + a[i-1]
        dp[i][2] = max(dp[i - 2][2], dp[i - 3][1], dp[i - 4][0]) + a[i-1]
    if n & 1:
        print(max(dp[-3][0], dp[-2][1], dp[-1][2]))
    else:
        print(max(dp[-1][1], dp[-2][0]))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    a = LI()
    if n == 3:
        print(max(a))
        return
    dp = [[-inf] * 3 for i in range(n + 1)]
    dp[0] = [0, 0, 0]
    dp[1][0] = a[0]
    dp[2][1] = a[1]
    for i in range(3, n+1):
        dp[i][0] = dp[i - 2][0] + a[i-1]
        dp[i][1] = max(dp[i - 2][1], dp[i - 3][0]) + a[i-1]
        dp[i][2] = max(dp[i - 2][2], dp[i - 3][1], dp[i - 4][0]) + a[i-1]
    if n & 1:
        print(max(dp[-3][0], dp[-1][1], dp[-1][2]))
    else:
        print(max(dp[-1][1], dp[-2][0]))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007

def solve(N: int, A: "List[int]"):
    from collections import defaultdict
    M = N // 2
    def get_range(idx):
        r = (N - idx) // 2 + 1        
        return range(max(0, M-r), idx//2+1+1)
    
    dp_a = defaultdict(lambda:-float('inf'))
    dp_s = defaultdict(lambda:-float('inf'))
    dp_s[(0, -1)] = 0 
    for i in range(N):
        for j in get_range(i):
            dp_s[(j, i)] = max(dp_s[(j, i)], dp_a[(j, i-1)], dp_s[(j, i-1)])
            dp_a[(j, i)] = max(dp_a[(j, i)], dp_s[(j, i)], dp_s[(j-1, i-1)]+A[i])
    print(max(max(v for (j, i), v in dp_a.items() if j == M),
              max(v for (j, i), v in dp_s.items() if j == M)))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Accepted

Solution code:
from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))
m = n//2
INF = 10**18
dp = [defaultdict(lambda: -INF) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(i//2-1, (i+1)//2+1):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i-1])
        elif 0 <= i-2 and 0 <= j <= m:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+A[i-1])
print(dp[-1][m])

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))
m = n//2
INF = 10**18
dp = [defaultdict(lambda: -INF) for _ in range(n+1)]
for i in range(1, n+1):
    L = i//2-1
    R = (i+1)//2+1
    for j in range(L, R):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i-1])
        elif 0 <= i-2 and 0 <= j <= m:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+A[i-1])
print(dp[-1][m])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = list(map(int,input().split()))
dp0 = [0] * (n+11)
dp1 = [0] * (n+11)
dp2 = [0] * (n+11)
for i,ai in enumerate(A):
  dp2[i+11] = (max(dp0[i+7] + ai, dp1[i+8] + ai, dp2[i+9] + ai) if i >= 2 else 0)
  dp1[i+11] = (max(dp0[i+8] + ai, dp1[i+9] + ai) if i >= 1 else 0)
  dp0[i+11] = dp0[i+9] + ai 
if n % 2 == 0:
  print(max(dp0[n + 9], dp1[n + 10]))
else:
  print(max(dp0[n + 8], dp1[n + 9], dp2[n + 10]))

# debug
# print(dp0,dp1,dp2,sep="\n")

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
if N % 2 == 0:
    x, y, px, py = 0, 0, 0, -1<<100
    for a in A:
        x, y, px, py = px+a, max(x, py+a), x, y
    print(max(x, y))
else:
    x, y, z, px, py, pz = 0, 0, 0, 0, -1<<100, -1<<100
    for a in A:
        x, y, z, px, py, pz = px+a, max(x, py+a), max(y, pz+a), x, y, z
    print(max(y, z))

Submission status: Accepted

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, initial=-10**9)
    DP[0][0] = A[0]
    DP[1][1] = A[1]
    if K == 3:
        DP[2][2] = A[2]
    for i in range(1, N):
        for k in range(K):
            if i == k and i < K:
                continue
            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][1], DP[-2][0]))
    else:
        print(max(DP[-1][2], DP[-2][1], DP[-3][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: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
odds_or_even = N%2+2
inf = -float("inf")
dp = [[inf for _ in range(N+1)] for _ in range(odds_or_even)]
dp[0][0] = 0
for i in range(N):
    dp[0][i+1] = dp[0][i]+A[i]*((i+1)%2)
for j in range(1,odds_or_even):
    for i in range(N):
        dp[j][i+1] = max(dp[j-1][i],dp[j][i]+A[i]*((i+j+1)%2))

print(dp[odds_or_even-1][N])