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:
def main():
    import os
    import sys
    from io import BytesIO, IOBase
    
    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)

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

    from collections import defaultdict

    dp = defaultdict(lambda : -float('inf'))
    dp[(0, 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, 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)]))
main()

Submission status: Accepted

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)] = 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, 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: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
# at any partial solution, it is only possible to
# have either ceil(k/2) or ceil(k/2)-1 included values
# also, for the next solution, it matters if the current value was used or not.
# therefore, keep a partial 'max solution' for all 4 possibilities:
# ceil(k/2)-1, not included
# ceil(k/2)-1, included
# ceil(k/2), not included
# ceil(k/2), included
def solve(start_point):
  for idx, value in enumerate(a[start_point:]):
    idx = idx+start_point
    if idx%2!=0:
      partial_solution[idx][0] = max(partial_solution[idx-1][0], partial_solution[idx-1][1])
      partial_solution[idx][1] = a[idx] + max(partial_solution[idx-2][0], partial_solution[idx-2][1])
      partial_solution[idx][2] = max(partial_solution[idx-1][2], partial_solution[idx-1][3])
      partial_solution[idx][3] = a[idx] + partial_solution[idx-1][0]
    else:
      partial_solution[idx][0] = max(partial_solution[idx-1][2], partial_solution[idx-1][3])
      partial_solution[idx][1] = a[idx] + partial_solution[idx-1][0]
      partial_solution[idx][2] = float('-inf')
      partial_solution[idx][3] = a[idx] + partial_solution[idx-1][2]
  if n%2==0:
    return(max(partial_solution[n-1][2], partial_solution[n-1][3]))
  return(max(partial_solution[n-1][0], partial_solution[n-1][1]))
partial_solution = [[float('-inf') for _ in range(4)] for _ in range(len(a))]
partial_solution[0] = [0, float('-inf'), float('-inf'), a[0]]
# partial_solution[1] = [0, float('-inf'), a[0], a[1]]
# partial_solution[2] = [max(a[:2]), a[2], float('-inf'), a[0]+a[2]]
# partial_solution[3] = [max(a[:3]), a[3], a[0]+a[2], max(a[0]+a[3], a[1]+a[3])]
print(solve(start_point=1))

Submission status: Accepted

Solution code:

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

    # 取る 取らない 取る 取らない ... を貪欲にやっていくと 1 + n % 2 個余って、
    # 1 + n % 2 回飛ばせることがわかる
    skip = 1 + N % 2;

    # dp[i][j] := a[0, i) を j 要素無視して1つ飛びに取ったときの最大値
    dp = [[INF] * (skip + 1) for _ in range(N + 2)]
    dp[0][0] = 0
    for i in range(N + 1):
        for j in range(skip + 1):
            if j < skip:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j])
            if i < N:
                dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + A[i])
    # 1個選んだら1個選ばないのもセット
    # なので floor(n / 2) * 2 + skip == n + 1 に答えが入る
    print(dp[N + 1][skip])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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(3, n+1, 2):
        if i%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: Accepted

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:
            if i!=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(dp)
    print(max(dp[(n-1,n//2)],dp[(n-2,n//2)],dp[(n-3,n//2)]))

Submission status: Accepted

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

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

if n%2==0:
    

    #iは桁数、jはそれまでに余計に飛ばした数
    #dp[i][j]
    dp=[[-10**9]*2 for _ in range(n)]

    for i in range(n):
        if i<2:
            dp[i][0]=a[i]

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

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

else:
    

    #iは桁数、jはそれまでに余計に飛ばした数
    #dp[i][j]
    dp=[[-10**9]*3 for _ in range(n)]

    for i in range(n):
        if i<2:
            dp[i][0]=a[i]

        if i>=2:
            dp[i][0]=dp[i-2][0]+a[i]
        
        if i>=3:
            dp[i][1]=max(dp[i-2][1]+a[i],dp[i-3][0]+a[i])
            
        if i>=4:
            dp[i][2]=max([dp[i-2][2]+a[i],dp[i-3][1]+a[i],dp[i-4][0]+a[i]])
    #print(dp)
    print(max([dp[-1][2],dp[-1][1],dp[-1][0]-a[0],dp[-1][0]-a[-1]]))

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)
from pprint import pprint


def solve(N: int, A: "List[int]"):
    memo = [{} for _ in range(N + 1)]
    def rec(idx, rest, can_use=True):
        k = (rest, can_use)
        if rest * 2 >= N - idx + 2:
            return 0
        if rest == 0:
            return 0
        if k in memo[idx]:
            return memo[idx][k]

        ret = 0
        if not can_use:
            ret = rec(idx + 1, rest)
        elif rest * 2 > (N - idx):
            ret = A[idx] + rec(idx + 1, rest - 1, False)
        else:
            a = A[idx] + rec(idx + 1, rest - 1, False)
            b = rec(idx + 1, rest)
            ret = max(a, b)
        memo[idx][k] = ret
        return ret
    ret = rec(0, N // 2)
    print(ret)
    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()))

dp = [[-10**18 for i in range(N//2+1)] for j in range(2)]

dp[0][0] = 0
dp[1][1] = A[0]
dp[1][0] = 0

for i in range(2,N+1):
    high = min(N//2, i//2+10)
    low = max(0,i//2-10)
    for j in range(high,low,-1):
        dp[i%2][j] = max(dp[(i-1)%2][j], dp[i%2][j-1] + A[i-1])
print(dp[N%2][N//2])

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
*A, = map(int, input().split())
INF = 10**20
dp = defaultdict(lambda :-INF)
dp[(0,0,0)] = 0

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
*A, = map(int, input().split())
INF = 10**20
dp = [[defaultdict(lambda :-INF) for _ in range(N+1)] for _ in range(2)]
dp[0][0][0] = 0

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
dp = [[-10**20 for i in range(3)] for j in range(N+1)]
dp[0][1] = 0
dp[1][1] = 0
dp[1][2] = A[0]

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

Submission status: Accepted

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

ret = 0

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

print(ret)

Submission status: Accepted

Solution code:
# F - Select Half
N = int(input())
A = list(map(int,input().split()))

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

Submission status: Accepted

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

dic1 = {0:0}
dic2 = {0:0, 1:a[0]}

for i in range(1, n):
    mini = choice - (n-i+1)//2
    new = {}
    for j in range(mini, (i+2)//2+1):
        if j == 0:
            new[j] = 0
            continue
        if j in dic2:
            new[j] = max(dic2[j], dic1[j-1]+a[i])
        else:
            new[j] = dic1[j-1]+a[i]
    dic1 = dic2
    dic2 = new

print(dic2[choice])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
    dp = [[-float("inf")] * 2 for i in range(n)]
    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]
        dp[i][1] = max(dp[i - 2][1], dp[i - 3][0] if i >= 3 else float("-inf")) + A[i]

    # print(dp)
    print(max(dp[-1][1], dp[-2][0]))
else:
    dp = [[-float("inf")]*3 for i in range(n)]
    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]
        dp[i][1] = max(dp[i-2][1], dp[i-3][0] if i>=3 else float("-inf")) + A[i]
        dp[i][2] = max(dp[i-2][2], dp[i-3][1] if i>=3 else float("-inf"), dp[i-4][0] if i>=4 else float("-inf")) + A[i]
        if i == 2:
            dp[i][2] = A[2]

    # print(dp)
    print(max(dp[-1][2], dp[-2][1], dp[-3][0]))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float("inf")
mod = 10 ** 9 + 7

N = INT()
A = LIST()

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

print(dp[N][1])

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
dp = [[-10**18]*3 for _ in range(N)]
dp[0][0] = A[0]
dp[1][1] = A[1]

if N>=3:
    dp[2][2] = A[2]

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

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

Submission status: Accepted

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

dp0 = 0
dp1 = -INF
dp2 = -INF

for i, a in enumerate(A):
    if i % 2 == 0:
        dp1 = max(dp1, dp0)
        dp0 += a
        dp2 += a
    else:
        dp2 = max(dp2, dp1)
        dp1 += a

if N % 2 == 1:
    print(max(dp1, dp2))
else:
    print(max(dp0, dp1))

Submission status: Accepted

Solution code:
n = int(input())
a = [0]+list(map(int,input().split()))
dp = [[0]*2 for _ in range(n+1)]
dp[1][1] = a[1]
dp[2][1] = max(a[1],a[2])

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = LI()

    if n < 4:
        return max(a)

    dp = [[-inf] * 3 for _ in range(n)]
    for i in range(3):
        dp[i][i] = a[i]

    for i in range(n):
        c = a[i]
        di = dp[i]
        if i > 1:
            d2 = dp[i-2]
            for j in range(3):
                if di[j] < d2[j] + c:
                    di[j] = d2[j] + c
        if i > 2:
            d3 = dp[i-3]
            for j in range(2):
                if di[j+1] < d3[j] + c:
                    di[j+1] = d3[j] + c
        if i > 3:
            d4 = dp[i-4]
            for j in range(1):
                if di[j+2] < d4[j] + c:
                    di[j+2] = d4[j] + c

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

    r = -inf
    for i in range(3):
        r = max(r, dp[-1-i][2-i])

    return r

print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict


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

    def default():
        return -float("inf")
    dp = [defaultdict(default) for _ in range(N)]
    dp[0][0] = 0
    dp[0][1] = A[0]
    dp[1][0] = 0
    dp[1][1] = max(A[0], A[1])
    for i in range(2, N):
        dp[i][i//2] = max(dp[i-2][i//2-1] + A[i], dp[i-1][i//2])
        dp[i][i//2+1] = max(dp[i-2][i//2] + A[i], dp[i-1][i//2+1])
    print(dp[N-1][N//2])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

dp = [dict() for _ in range(n)]

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

import math
for i in range(2, n):
    k1 = int(math.ceil((i + 1) / 2))
    k2 = k1 - 1

    if i % 2 == 0:
        dp[i][k1] = dp[i-2][k1-1] + a[i]
    else:
        dp[i][k1] = max(dp[i-1][k1], dp[i-2][k1-1] + a[i])

    dp[i][k2] = max(dp[i-1][k2], dp[i-2][k2-1] + a[i])

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

Submission status: Accepted

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

INF = 10 ** 18

if N % 2:
    dp = [[-INF for j in range(N)] for i in range(3)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    for j in range(N):
        for i in range(3):
            if dp[i][j] == -INF:
                continue
            for k in range(3):
                if i + k < 3 and j + k + 2 < N:
                    dp[i + k][j + k + 2] = max(dp[i + k][j + k + 2], dp[i][j] + A[j + k + 2])
    print(max(max(dp[0][-3:-1]), max(dp[1][-2:]), max(dp[2][-1:])))
    
else:
    dp = [[-INF for j in range(N)] for i in range(2)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    for j in range(N):
        for i in range(2):
            if dp[i][j] == -INF:
                continue
            for k in range(2):
                if i + k < 2 and j + k + 2 < N:
                    dp[i + k][j + k + 2] = max(dp[i + k][j + k + 2], dp[i][j] + A[j + k + 2])
    print(max(max(dp[0][-2:]), max(dp[1][-1:])))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(1000000)

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

memo = {}
def sub_max(n, m):
    if((n, m) in memo):
        return memo[(n, m)]
    
    if(m == 1 and n >= 1):
        memo[(n, m)] = max(A[-n:])
        return memo[(n, m)]

    if(m > math.ceil(n/2)):
        memo[(n, m)] = -float('inf')
        return -float('inf')
    
    res = -float('inf')
    for i in range(3):
        res = max(res, A[-n + i] + sub_max(n - i - 2, m - 1))
    memo[(n, m)] = res
    return res

print(sub_max(N, N//2))
# print(memo)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
k = 1 + n%2
dp = [[-float('inf')] * (k + 2) for i in range(n + 1)]
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])

Submission status: Accepted

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

DP = [0,0,0]
m = N//2*2
if N%2 == 0:
    for i in range(0,m,2):
        DP[0] += A[i]
        DP[1] += A[i+1]
        DP[1] = max(DP[0],DP[1])

    print(DP[1])

else:
    for i in range(0,m,2):
        DP[0] += A[i]
        DP[1] += A[i+1]
        DP[2] += A[i+2]

        DP[1] = max(DP[0],DP[1])
        DP[2] = max(DP[1],DP[2])

    print(DP[2])

Submission status: Accepted

Solution code:
def solve():
    INF = float('inf')

    def max2(x, y): return x if x >= y else y

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

    dp = [[[-INF]*(2) for j in range(3)] for i in range(N+1)]
    dp[0][2][0] = dp[0][2][1] = 0
    for i, A in enumerate(As):
        if i&1:
            for k in range(2):
                for j in range(3):
                    dp[i+1][j][0] = max2(dp[i+1][j][0], dp[i][j][k])
            for j in range(2):
                dp[i+1][j+1][1] = max2(dp[i+1][j+1][1], dp[i][j][0] + A)
        else:
            for j in range(3):
                dp[i+1][j][1] = max2(dp[i+1][j][1], dp[i][j][0] + A)
            for k in range(2):
                for j in range(1, 3):
                    dp[i+1][j-1][0] = max2(dp[i+1][j-1][0], dp[i][j][k])

    if N&1:
        print(max(dp[-1][1]))
    else:
        print(max(dp[-1][2]))


solve()

Submission status: Accepted

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

v1 = 0
v2 = 0
v3 = 0
m = N // 2 *2 
if N % 2 == 0:
  for i in range(0, m, 2):
    v1 += A[i]
    v2 += A[i+1]
    v2 = max(v1,v2)
  print(v2)  
#
else:
  for i in range(0, m, 2):
    v1 += A[i]
    v2 += A[i+1]
    v3 += A[i+2]
    v2 = max(v1,v2)
    v3 = max(v2,v3)
  print(v3)
#

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

class Solver:

    def __init__(self, n, a_s):
        self.n = n
        self.a_s = a_s
        self.extra = 1 if self.n % 2 == 0 else 2
        self.dp = self.prepare_dp()

    def prepare_dp(self):
        dp = [None] * (self.n + 1)
        for i, _ in enumerate(dp):
            dp[i] = [-1 * math.inf] * (1 + self.extra)
        dp[0][0] = 0
        return dp

    def run(self):
        extra = 1 + self.n % 2
        for i, a in enumerate(self.a_s):
            for j in range(self.extra):
                self.dp[i + 1][j + 1] = self.dp[i][j]
            for j in range(self.extra + 1):
                v = self.dp[i][j]
                if (i + j) % 2 == 0:
                    v += a
                self.dp[i + 1][j] = max(self.dp[i + 1][j], v)
        #print('self.dp') # debug
        #print(self.dp) # debug
        return self.dp[n][extra]



if __name__ == '__main__':
    n = int(input())
    a_s = list(map(int, input().split()))
    ans = Solver(n, a_s).run()
    #print('ans') # debug
    print(ans)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
m0 = 0
m1 = 0
m2 = 0

if n%2 == 0:
    for i,ai in enumerate(a):
        if i%2 == 0:
            m0 += ai
        else:
            m1 = max(m0,m1+ai)
    print(max(m0,m1))
else:
    for i,ai in enumerate(a):
        if i%2 == 0:
            if i > 0:
                m2 = max(m2+ai,m1,m0)
            if i < n-1:
                m0 += ai
        else:
            m1 = max(m0,m1+ai)
    print(max(m0,m1,m2))

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
import numpy as np
dp=np.full((3,n+1),-pow(10,15))
dp[:,0]=0
dp[1,1]=a[0]
for i in range(2,n+1):
    #l,r=max(1,n//2-(n-i+1)//2),(i+1)//2+1
    l,r=max(1,i//2-1),(i+1)//2+1
    if i%3==2:
        now,pre,prepre=2,1,0
    elif i%3==0:
        now,pre,prepre=0,2,1
    elif i%3==1:
        now,pre,prepre=1,0,2
    dp[now,l:r]=np.maximum(dp[pre,l:r],dp[prepre,l-1:r-1]+a[i-1])
print(dp[now,n//2])

Submission status: Accepted

Solution code:
import collections, sys
sys.setrecursionlimit(100005)
N = int(input())
A = [int(_) for _ in input().split()]
INF = float('inf')
memo = collections.defaultdict(lambda: INF)


def c(start, res):
    if memo[start, res] != INF:
        return memo[start, res]
    elif 2 * res - 1 > N - start:
        memo[start, res] = -INF
    elif start >= N:
        memo[start, res] = -INF
    elif res > 1:
        memo[start, res] = max(A[start] + c(start + 2, res - 1),
                               c(start + 1, res), c(start + 2, res))
    else:
        memo[start, res] = max(A[start], c(start + 1, res))
    return memo[start, res]


print(c(0, N // 2))

Submission status: Accepted

Solution code:
#基本1つ飛ばしだが、パスも使える。
#奇数ならパス2回、偶数ならパス1回。
N = int(input())
A = [int(hoge) for hoge in input().split()]
DP = [[0]*3 for n in range(N)] #DP[n][y] = n桁目までみて、パスをy回使ったときの最大値

DP[0][0] = A[0]

for n in range(1,N):#n桁目までみる。
    #「選ぶ」か「パスを使う」かの2択。
    DP[n][0] = DP[n-2][0] + A[n]
    DP[n][1] = max((DP[n-2][1]+A[n],DP[n-1][0]))
    DP[n][2] = max((DP[n-2][2]+A[n],DP[n-1][1]))
if N%2:
    print(DP[n][2])
else:
    print(DP[n][1])

Submission status: Accepted

Solution code:
from collections import defaultdict
INF = 10 ** 15
N = int(input())
A = list(map(int,input().split()))
dp_take = defaultdict(lambda: -INF)
dp_not = defaultdict(lambda: -INF)
dp_take[(0,0)] = 0
dp_not[(0,0)] = 0

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

print(max(dp_take[(N, N//2)], dp_not[(N, N//2)]))

Submission status: Accepted

Solution code:
def find(A):
    N = len(A)
    ans = [0]*N
    odd_sum = [0]*N
    even_sum = [0]*N
    for i in range(N):
        if i%2 == 0:
            if i-2>=0:
                even_sum[i] = even_sum[i-2] + A[i]
            else:
                even_sum[i] = A[i]
        else:
            if i-2>=0:
                odd_sum[i] = odd_sum[i-2] + A[i]
            else:
                odd_sum[i] = A[i]

#     print(odd_sum)
#     print(even_sum)
    for i in range(1,N):
        length = i+1
        if length%2==0:
            ans[i] = max(A[i] + ans[i-2],odd_sum[i-1]+even_sum[i-1] )
        else:
            ans[i] = max(A[i] + ans[i-2],ans[i-1])
            
    return ans[-1]
    
input()   
print(find(list(map(int,input().strip().split()))))