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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)
INF = -10000000001

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

a = int(n/2)

dpa = [[INF for j in range(a+1)] for i in range(n+1)]

def dp(x,y):
	ret = 0
	if 2*y-1 > x:
		ret = INF
	elif y == 0:
		ret = 0
	else:
		if dpa[x][y] != INF:
			ret = dpa[x][y]
		else:
			ret = max(dp(x-2,y-1)+l[x-1],dp(x-1,y))
#	print(x,y,ret)
	return ret

print(dp(n,a))

Submission status: Time Limit Exceeded

Solution code:
import sys
#import copy
#import numpy as np
#import itertools
#import collections
#from collections import deque
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

inf = float('inf')

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

    K = N//2
    DP = [[-inf] * (K)  for _ in range(N)]

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

    ans = DP[N-1][K-1]
    #print(DP)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#import copy
#import numpy as np
#import itertools
#import collections
#from collections import deque
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

inf = float('inf')

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

    K = N//2
    DP = [[-inf] * (K)  for _ in range(N)]

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

    ans = DP[N-1][K-1]
    #print(DP)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

import numpy as np 
import itertools

# Input Stdin
## 2 <= N <= 2 * 10^5
## abs(A_N) <= 10^9

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

A_dummy = list(range(len(A)))
#print(A_dummy)
N2_ = int(N / 2)

max_sum = -10 ** 20

for v_dummy, v in zip(itertools.combinations(A_dummy, N2_), itertools.combinations(A, N2_)):
    flag = True
    vdm_pre = v_dummy[0]
    for vdm in v_dummy:
        if vdm - vdm_pre == 1:
            flag = False
            break
        vdm_pre = vdm
    if flag and np.sum(v) > max_sum:
        max_sum = np.sum(v)

print(max_sum)

Submission status: Time Limit Exceeded

Solution code:
inf = 10**16
N = int(input())
A = list(map(int, input().split()))
dp0=[[-inf]*(2+N//2) for _ in range(N+1)]
dp1=[[-inf]*(2+N//2) for _ in range(N+1)]
dp0[0][0] = 0

for i, x in enumerate(A):
    j = i//2
    for n in (j, j + 1):
        dp0[i+1][n] = max(dp0[i][n], dp1[i][n])
        dp1[i+1][n] = dp0[i][n - 1] + x
    #print(dp0)
    #print(dp1)

print(max(dp0[N][N//2], dp1[N][N//2]))

Submission status: Time Limit Exceeded

Solution code:
inf = float('inf')
N = int(input())
A = list(map(int, input().split()))
dp0=[[-inf]*(2+N//2) for _ in range(N+1)]
dp1=[[-inf]*(2+N//2) for _ in range(N+1)]
dp0[0][0] = 0

for i, x in enumerate(A):
    j = i//2
    for n in (j, j + 1):
        dp0[i+1][n] = max(dp0[i][n], dp1[i][n])
        dp1[i+1][n] = dp0[i][n - 1] + x
    #print(dp0)
    #print(dp1)

print(max(dp0[N][N//2], dp1[N][N//2]))

Submission status: Time Limit Exceeded

Solution code:
inf = float('inf')
N = int(input())
A = list(map(int, input().split()))
dp0=[[-inf]*(2+N//2) for _ in range(N+1)]
dp1=[[-inf]*(2+N//2) for _ in range(N+1)]
dp0[0][0] = 0

for i, x in enumerate(A):
    j = i // 2
    for n in (j, j + 1):
        dp0[i+1][n] = max(dp0[i][n], dp1[i][n])
        dp1[i+1][n] = dp0[i][n - 1] + x
    #print(dp0)
    #print(dp1)

print(max(dp0[N][N//2], dp1[N][N//2]))

Submission status: Time Limit Exceeded

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

dp = [[-float("inf")]*(N//2+1) for i in range(N+1)]
f  = [-float("inf")]*(N//2+1)

#dp
for i in range(1,N+1):
  for j in range(i//2-1,(i+1)//2+1):
    if j<=0 or j>=N//2+1:
      pass
    elif j==1:
      dp[i][1]=max(A[0:i])
    else:
      if i<2:
        dp[i][j]=f[j]
      else:
        dp[i][j]=max(dp[i-2][j-1]+A[i-1], f[j])
      f[j]=max(dp[i][j],f[j])
#print(dp)
#print(f)
print(dp[N][N//2])

Submission status: Time Limit Exceeded

Solution code:
# unfinished
INF = 1 << 64


def find_max(a):
    n = len(a)
    odd_a = [a[i] for i in range(n) if i % 2 == 0]
    even_a = [a[i] for i in range(n) if i % 2 == 1]

    cum_odd_a = [0]
    sum_odd_a = 0
    for odd_a_elem in odd_a:
        cum_odd_a.append(cum_odd_a[-1] + odd_a_elem)
        sum_odd_a += odd_a_elem

    cum_even_a = [0]
    sum_even_a = 0
    for even_a_elem in even_a:
        cum_even_a.append(cum_even_a[-1] + even_a_elem)
        sum_even_a += even_a_elem

    max_sum_half_a = -INF

    if n % 2 == 0:  # nが偶数である場合
        # 奇数と偶数の境目
        for i in range(n // 2 + 1):
            odd_part_sum = cum_odd_a[i]
            even_part_sum = sum_even_a - cum_even_a[i]
            sum_half_a = odd_part_sum + even_part_sum

            if sum_half_a > max_sum_half_a:
                max_sum_half_a = sum_half_a
    else:  # nが奇数である場合
        # 奇数と偶数の境目
        for i in range(n // 2 + 1):
            odd_part_sum_1 = cum_odd_a[i]

            # 偶数と奇数の境目
            for j in range(i, n // 2 + 1):
                even_part_sum = cum_even_a[j] - cum_even_a[i]
                odd_part_sum_2 = sum_odd_a - cum_odd_a[j + 1]

                sum_half_a = odd_part_sum_1 + even_part_sum + odd_part_sum_2

                if sum_half_a > max_sum_half_a:
                    max_sum_half_a = sum_half_a

    return max_sum_half_a


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

    print(find_max(a))


main()

Submission status: Time Limit Exceeded

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


def main():
    from collections import defaultdict
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    dp = defaultdict(lambda: C)
    for i in range(N+1):
        dp[(i, 0)] = 0
        if i != 0:
            dp[(i, 1)] = max(dp[(i-1, 1)], A[i-1])
    for i in range(2, N+1):
        for j in range((i+2)//2-1, (i+2)//2 + 1):
            if j < 0:
                continue
            cur = dp[(i, j)]
            for k in range(2, i+1-j):
                if 0 < i-k <= N:
                    cur = max(cur, dp[(i-k, j-1)] + A[i-1])
            dp[(i, j)] = cur
    print(dp[(N, K)])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

dp = [[-float("inf")]*N for i in range(N+1)]
f  = [-float("inf")]*N

#dp
for i in range(1,N+1):
  for j in range(i//2-1,(i+1)//2+1):
    if j<=0 or j>=N:
      pass
    elif j==1:
      dp[i][1]=max(A[0:i])
    else:
      if i<2:
        dp[i][j]=f[j]
      else:
        dp[i][j]=max(dp[i-2][j-1]+A[i-1], f[j])
    f[j]=max(dp[i][j],f[j])
#print(dp)
#print(f)
print(dp[N][N//2])

Submission status: Time Limit Exceeded

Solution code:
n,*a=map(int,open(0).read().split())
dp=[[0]+[-10**18]*n for _ in range(n+1)]
for i,a in enumerate(a):
    for j in range(n//2-(n-i)//2,i//2+2):
        dp[i+1][j]=max(dp[i-1][j],dp[i-1][j-1]+a,dp[i][j])
print(dp[n][n//2])

Submission status: Time Limit Exceeded

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

dp = [[-float("inf") for _ in range(N)] for i in range(N+1)]
f  = [-float("inf") for j in range(N)]

#dp
for i in range(1,N+1):
  for j in range(i//2-1,(i+1)//2+1):
    if j<=0 or j>=N:
      pass
    elif j==1:
      dp[i][1]=max(A[0:i])
    else:
      if i<2:
        dp[i][j]=f[j]
      else:
        dp[i][j]=max(dp[i-2][j-1]+A[i-1], f[j])
    f[j]=max(dp[i][j],f[j])
#print(dp)
#print(f)
print(dp[N][N//2])

Submission status: Time Limit Exceeded

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

dp = [[-float("inf") for _ in range(N)] for i in range(N+1)]
f  = [-float("inf") for j in range(N)]
for i in range(N):
  dp[i+1][1]=max(A[0:i+1])
  f[1]=max(f[1],dp[i+1][1])

#dp
for i in range(1,N+1):
  for j in range(i//2-1,(i+1)//2+1):
    if j<=1 or j>=N:
      pass
    else:
      if i<2:
        dp[i][j]=f[j]
      else:
        dp[i][j]=max(dp[i-2][j-1]+A[i-1], f[j])
      f[j]=max(dp[i][j],f[j])
#print(dp)
#print(f)
print(dp[N][N//2])

Submission status: Time Limit Exceeded

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


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

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

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

    dp = [[0] * (N // 2 + 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 == 0:
            dp[i][i // 2 - 1] = max(A[i] + dp[i - 2][i // 2 - 1], dp[i - 1][i // 2 - 1])
            dp[i][i // 2] = max(A[i] + dp[i - 2][i // 2 - 1], dp[i - 1][i // 2])
        elif i > 3:
            dp[i][(i - 3) // 2] = max(A[i] + dp[i - 2][(i - 5) // 2], dp[i - 1][(i - 3) // 2])
            dp[i][(i - 1) // 2] = max(A[i] + dp[i - 2][(i - 3) // 2], dp[i - 1][(i - 1) // 2])
            dp[i][(i + 1) // 2] = A[i] + dp[i - 2][(i - 1) // 2]
        else:
            dp[3][1] = max(A[1:4])
            dp[3][2] = A[1] + A[3]
    print(dp[N][N // 2])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

dp = [[-float("inf") for _ in range(N)] for i in range(N+1)]
f  = [[-float("inf")] for j in range(N)]
for i in range(N):
  dp[i+1][1]=max(A[0:i+1])
  f[1].append(dp[i+1][1])

#dp
for i in range(1,N+1):
  for j in range(i//2-1,(i+1)//2+1):
    if j<=1 or j>=N:
      pass
    else:
      if i<2:
        dp[i][j]=max(f[j])
      else:
        dp[i][j]=max(dp[i-2][j-1]+A[i-1], max(f[j]) )
      f[j].append(dp[i][j])
#print(dp)
#print(f)
print(dp[N][N//2])

Submission status: Time Limit Exceeded

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

def wa(posi):
    s = 0
    for x in posi:
        s += A[x-1]
    return s

def copy(left,right):
    left = []
    for p in right:
        left.append(p)

tmp = [[1],[2]]
pre1 = [[]]
pre2 = [[]]
pre3 = [[]]

for n in range(3,N+1):
    pre3 = pre2
    pre2 = pre1
    pre1 = tmp
    tmp = []
    for p in pre2:
        tmp.append(p+[n])
    if n%2==1:
        for p in pre3:
            tmp.append(p+[n-1])
    p3 =[]
    for i in range(n//2):
        p3.append(2*i+1)
    tmp.append(p3)

sums = []

for p in tmp:
    sums.append(wa(p))

print(max(sums))

Submission status: Time Limit Exceeded

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

def zenbu(m, B):
    dp = [-10**9]*m
    if dp[m-1] > -10**9:
        return dp[m-1]
    elif m == 1:
        dp[0] = B[0]
        return dp[0]
    elif m == 2:
        dp[1] = max(B[0],B[1])
        return dp[1]
    elif m == 3:
        dp[2] = max(B[0],B[1],B[2])
        return dp[2]
    elif m%2 == 0: #偶数の場合
        temp = 0
        for i in range(m//2-1):
            temp += B[i*2]
        dp[m-1] = max(temp+ max(B[m-2],B[m-1]), zenbu(m-2, B)+ B[m-1])
        return dp[m-1]
    else:#奇数の場合
        temp = 0
        for i in range((m-1)//2):
            temp += B[i*2]
        dp[m-1] = max(temp, zenbu(m-2,B)+ B[m-1], zenbu(m-3,B)+ max(B[m-2],B[m-1]))
        return dp[m-1]

ans = zenbu(n,A)

print(ans)

Submission status: Time Limit Exceeded

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


def main():
    from collections import defaultdict
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    dp = defaultdict(lambda: C)
    for i in range(N+1):
        dp[(i, 0)] = 0
        if i != 0:
            dp[(i, 1)] = max(dp[(i-1, 1)], A[i-1])
    for i in range(2, N+1):
        for j in range(max(i//2 - 1, 0), i+1//2 + 1):
            dp[(i, j)] = max(dp[(i, j)], dp[(i-1, j)],
                             dp[(i-2, j-1)] + A[i-1],
                             dp[(i-3, j-1)] + A[i-1])
    print(dp[(N, K)])
    # print(*dp, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def main():
    from collections import defaultdict
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    dp = defaultdict(lambda: C)
    for i in range(N+1):
        dp[(i, 0)] = 0
        if i != 0:
            dp[(i, 1)] = max(dp[(i-1, 1)], A[i-1])
    for i in range(2, N+1):
        for j in range(max(i//2 - 1, 0), i+1//2 + 1):
            if dp[(i-1, j)] == C and dp[(i-2, j-1)] == C \
                    and (i < 3 or dp[(i-3, j-1)] == C):
                continue
            else:
                dp[(i, j)] = max(dp[(i, j)], dp[(i-1, j)],
                                 dp[(i-2, j-1)] + A[i-1],
                                 dp[(i-3, j-1)] + A[i-1])
    print(dp[(N, K)])
    # print(*dp, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Spyder Editor

This is a temporary script file.
"""

#f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)

select_num = N//2

Dp_f = [[-9999]*(N+1) for _ in range(N+1)]
Dp_s = [[-9999]*(N+1) for _ in range(N+1)]

for i in range(1,N+1):
    Start = (i-1)//2
    End = (i+1)//2

    for j in range(Start,End+1):
        Dp_f[i][j] = max(Dp_s[i-1][j], Dp_f[i-1][j])   
        # [0] in 3rd dimension  not chosen at last num
        # must be transfered from [i-1]
    for j in range(Start,End+1):
        if Dp_f[i-1][j-1] == -9999 and j == 1:
            Dp_s[i][j] = 0 + A[i]
        else:
            Dp_s[i][j] = Dp_f[i-1][j-1]+A[i]

print(max(Dp_f[-1][select_num], Dp_s[-1][select_num]))

Submission status: Time Limit Exceeded

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


def main():
    N = int(input())
    K = N//2
    A = [int(i) for i in input().split()]
    dp = [[C]*(K+1) for _ in range(N+1)]
    for i in range(N+1):
        dp[i][0] = 0
        if i != 0:
            dp[i][1] = max(dp[i-1][1], A[i-1])
    for i in range(2, N+1):
        for j in range(2, K+1):
            if dp[i-1][j] == -1 and dp[i-2][j-1] == -1 \
                    and (i < 3 or dp[i-3][j-1] == -1):
                dp[i][j] = -1
            else:
                dp[i][j] = max(dp[i][j], dp[i-1][j],
                               dp[i-2][j-1] + A[i-1])
                if i > 2:
                    dp[i][j] = max(dp[i][j], dp[i-3][j-1] + A[i-1])
    print(dp[N][K])
    # print(*dp, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

INF = 110110110
_INFL = -INF * INF

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

memo = {}
def solve(now, num, sum):
    hash = (now * 1000000007 + num * 1000000009 + sum) % 998244353
    try:
        return memo[hash]
    except KeyError:
        if num == N__2:
            return sum
        need = N__2 - num
        can = (N - now + 1) // 2
        if can < need:
            return _INFL
        res = max(solve(now+1, num, sum), solve(now+2, num + 1, sum + A[now]))
        memo[hash] = res
        return res



print(solve(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)

INF = 110110110
_INFL = -INF * INF

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

def solve(now, num, sum):
    if num == N__2:
        return sum
    need = N__2 - num
    can = (N - now + 1) // 2
    if can < need:
        return _INFL

    return max(solve(now+1, num, sum), solve(now+2, num + 1, sum + A[now]))

print(solve(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

INF = 110110110

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


def solve(now, num, sum):
    if num == N // 2:
        return sum
    need = N // 2 - num
    can = (N - now + 1) // 2
    if can < need:
        return -INF * INF

    return max(solve(now+1, num, sum), solve(now+2, num + 1, sum + A[now]))

print(solve(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000010)

INF = 110110110

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


def solve(now, num, sum):
    if num == N // 2:
        return sum
    need = N // 2 - num
    can = (N - now + 1) // 2
    if can < need:
        return -INF * INF
    return max(solve(now+1, num, sum), solve(now+2, num + 1, sum + A[now]))

print(solve(0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int,input().split()))
    dp = [[-float("INF")]*(n//2+1) for i in range(n+1)]
    dp[0][0] = 0
    dp[1][0] = 0
    dp[1][1] = l[0]
    for i in range(1,n):
        for j in range(max(0,i//2-1),min(i//2+2,n//2+1)):
            dp[i+1][j] = max(dp[i][j],dp[i-1][j-1]+l[i])
    print(dp[-1][-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
dp = [[-float("INF")]*(n//2+1) for i in range(n+1)]
dp[0][0] = 0
dp[1][0] = 0
dp[1][1] = l[0]
for i in range(1,n):
    for j in range(max(0,i//2-2),min(i//2+2,n//2+1)):
        dp[i+1][j] = max(dp[i][j],dp[i-1][j-1]+l[i])
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:

import math

N = int(input())
num = math.floor(N/2)

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

# iまででj個を選び、状態がk（i番目を選んでいる（もしくはいない））の場合の最大値
# j : [(i-1)/2] -1, 0, 1

dp = [[[- float('inf')] * 2 for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(1, N+1):
    min_j = math.floor((i-1)/2) - 1
    # print(i, min_j)

    for j in range(3):
        # k = 1なら次は必ず選ばない（その場合jは変わらない）
        dp[i][min_j + j][0] = max(dp[i][min_j + j][0], dp[i-1][min_j + j][1])
        # k = 0なら選んでも選ばなくてもいい
        dp[i][min_j + j][0] = max(dp[i][min_j + j][0], dp[i-1][min_j + j][0])
        dp[i][min_j + j + 1][1] = max(dp[i][min_j + j + 1][1], dp[i-1][min_j + j][0] + A[i-1])


'''
# print(dp)
for i in range(1, N+1):
    min_j = math.floor((i-1)/2)
    print(i, min_j, dp[i][min_j-1:min_j + 2])
'''

print(max(dp[N][num][0], dp[N][num][1]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Spyder Editor

This is a temporary script file.
"""

#f = open("/Users/naoki/Documents/Atcoder/input.txt")
N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)

select_num = N//2


Dp = [[[-9999 for _ in range(2)] for _ in range(N+1)] for _ in range(N+1)]

for i in range(1,N+1):
    Start = (i-1)//2
    End = (i+1)//2
    
    for j in range(Start,End+1):
        Dp[i][j][0] = max(Dp[i-1][j][1], Dp[i-1][j][0])   
        # [0] in 3rd dimension  not chosen at last num
        # must be transfered from [i-1]
    for j in range(Start,End+1):
        if Dp[i-1][j-1][0] == -9999 and j == 1:
            Dp[i][j][1] = 0 + A[i]
        else:
            Dp[i][j][1] = Dp[i-1][j-1][0]+A[i]

print(max(Dp[-1][select_num][0], Dp[-1][select_num][1]))

Submission status: Time Limit Exceeded

Solution code:
n=input()
List=list(map(int,input().split()))
def find(List):
    if len(List)==1:
        return(int(List[0]))
    elif len(List)==2:
        if List[0] >= List[1]:
            return(int(List[0]))
        else:
            return(int(List[1]))
    elif len(List)==3:
        if (List[0]>=List[1] and List[0]>=List[2]):
            return(int(List[0]))
        elif(List[1]>=List[0] and List[1]>=List[2]):
            return(int(List[1]))
        else:
            return(int(List[2]))
    else:
        if len(List)%2==0:
            List2=[]
            for i in range(0,len(List)-2):
                List2.append(List[i])
            sub1=int(int(List[len(List)-1])+find(List2))
            sub2=0
            for i in range(0,len(List)//2):
                sub2+=List[2*i]
            if sub1 >= sub2:
                return(sub1)
            else:
                return(sub2)
        else:
            List2=[]
            List3=[]
            for i in range(0,len(List)-2):
                List2.append(List[i])
            for i in range(0,len(List)-3):
                List3.append(List[i])
            sub1=int(int(List[len(List)-1])+find(List2))
            sub2=int(int(List[len(List)-2])+find(List3))
            sub3=0
            for i in range(0,len(List)//2):
                sub3+=List[2*i]
            if (sub1>=sub2 and sub1>=sub3):
                return(sub1)
            elif(sub2>=sub1 and sub2>=sub3):
                return(sub2)
            else:
                return(sub3)
print(find(List))

Submission status: Time Limit Exceeded

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

def zenbu(m, B):
    if m == 1:
        return B[0]
    elif m == 2:
        return max(B[0],B[1])
    elif m == 3:
        return max(B[0],B[1],B[2])
    elif m%2 == 0: #偶数の場合
        temp = 0
        for i in range(m//2-1):
            temp += B[i*2]
        return max(temp+ max(B[m-2],B[m-1]), zenbu(m-2, B)+ B[m-1])
    else:#奇数の場合
        temp = 0
        for i in range((m-1)//2):
            temp += B[i*2]
        return max(temp, zenbu(m-2,B)+ B[m-1], zenbu(m-3,B)+ max(B[m-2],B[m-1]))

ans = zenbu(n,A)

print(ans)

Submission status: Time Limit Exceeded

Solution code:

import math

N = int(input())
num = math.floor(N/2)

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

# iまででj個を選び、状態がk（i番目を選んでいる（もしくはいない））の場合の最大値
# j : [(i-1)/2] -1, 0, 1

dp = [[[- float('inf')] * 2 for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(1, N+1):
    val = A[i-1]
    min_j = math.floor((i-1)/2) - 1

    for j in range(3):
        # k = 1なら次は必ず選ばない（その場合jは変わらない）
        dp[i][min_j + j][0] = max(dp[i][min_j + j][0], dp[i-1][min_j + j][1])
        # k = 0なら選んでも選ばなくてもいい
        dp[i][min_j + j][0] = max(dp[i][min_j + j][0], dp[i-1][min_j + j][0])
        dp[i][min_j + j + 1][1] = max(dp[i][min_j + j + 1][1], dp[i-1][min_j + j][0] + val)


'''
# print(dp)
for i in range(1, N+1):
    min_j = math.floor((i-1)/2)
    print(i, min_j, dp[i][min_j-1:min_j + 2])
'''

print(max(dp[N][num][0], dp[N][num][1]))

Submission status: Time Limit Exceeded

Solution code:

import math

N = int(input())
num = math.floor(N/2)

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

# iまででj個を選び、状態がk（i番目を選んでいる（もしくはいない））の場合の最大値
# j : [(i-1)/2] -1, 0, 1

dp = [[[- float('inf')] * 2 for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(1, N+1):
    val = A[i-1]
    min_j = math.floor((i-1)/2) - 1

    for j in range(3):
        # k = 1なら次は必ず選ばない（その場合jは変わらない）
        dp[i][min_j + j][0] = max(dp[i][min_j + j][0], dp[i-1][min_j + j][1])
        # k = 0なら選んでも選ばなくてもいい
        dp[i][min_j + j][0] = max(dp[i][min_j + j][0], dp[i-1][min_j + j][0])
        dp[i][min_j + j + 1][1] = max(dp[i][min_j + j + 1][1], dp[i-1][min_j + j][0] + val)

print(max(dp[N][num][0], dp[N][num][1]))

Submission status: Time Limit Exceeded

Solution code:

import math

N = int(input())
num = math.floor(N/2)

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

# iまででj個を選び、状態がk（i番目を選んでいる（もしくはいない））の場合の最大値
# j : [(i-1)/2] -1, 0, 1

dp = [[[- float('inf')] * 2 for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(1, N+1):
    val = A[i-1]
    min_j = math.floor((i-1)/2) - 1
    # print(i, min_j)

    for j in range(3):
        # k = 1なら次は必ず選ばない（その場合jは変わらない）
        dp[i][min_j + j][0] = max(dp[i][min_j + j][0], dp[i-1][min_j + j][1])
        # k = 0なら選んでも選ばなくてもいい
        dp[i][min_j + j][0] = max(dp[i][min_j + j][0], dp[i-1][min_j + j][0])
        dp[i][min_j + j + 1][1] = max(dp[i][min_j + j + 1][1], dp[i-1][min_j + j][0] + val)


# print(dp)

for i in range(1, N+1):
    min_j = math.floor((i-1)/2)
    # print(i, min_j, dp[i][min_j-1:min_j + 2])

print(max(dp[N][num][0], dp[N][num][1]))

Submission status: Time Limit Exceeded

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

    N2 = N // 2

    dp = [[None] * N for _ in range(N2 + 1)]
    dp[0] = [0] * N
    dp[1][N-1] = A[N-1]
    dp[1][N-2] = max(A[N-1], A[N-2])

    for j in range(1, N2 + 1):
        for i in range(N - max(3, 1 + 2 * (j - 1)), -1, -1):
            if dp[j - 1][i + 2] is None:
                dp[j][i] = dp[j][i + 1]
            elif dp[j][i + 1] is None:
                dp[j][i] = A[i] + dp[j - 1][i + 2]
            else:
                dp[j][i] = max(A[i] + dp[j - 1][i + 2], dp[j][i + 1])

    print(dp[N2][0])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

def zenbu(m, B):
    if m == 1:
        return B[0]
    elif m == 2:
        return max(B[0],B[1])
    elif m == 3:
        return max(B[0],B[1],B[2])
    elif m%2 == 0: #偶数の場合
        temp = 0
        for i in range(m//2-1):
            temp += B[i*2]
        return max(temp+ max(B[m-2],B[m-1]), zenbu(m-2, B[:-2])+ B[m-1])
    else:#奇数の場合
        temp = 0
        for i in range((m-1)//2):
            temp += B[i*2]
        return max(temp, zenbu(m-2,B[:-2])+ B[m-1], zenbu(m-3,B[:-3])+ max(B[m-2],B[m-1]))

ans = zenbu(n,A)

print(ans)

Submission status: Time Limit Exceeded

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

    N2 = N // 2

    dp = [[None] * N for _ in range(N2 + 1)]
    dp[0] = [0] * N
    dp[1][N-1] = A[N-1]
    dp[1][N-2] = max(A[N-1], A[N-2])

    for j in range(1, N2 + 1):
        for i in range(N - 3, -1, -1):
            if dp[j - 1][i + 2] is None:
                dp[j][i] = dp[j][i + 1]
            elif dp[j][i + 1] is None:
                dp[j][i] = A[i] + dp[j - 1][i + 2]
            else:
                dp[j][i] = max(A[i] + dp[j - 1][i + 2], dp[j][i + 1])

    print(dp[N2][0])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def dfs(n, L):
  if n % 2 == 0:
    S = sum(L[2*i] for i in range(n//2))
    M = S
    for i in range(n//2, 0, -1):
      S += L[2*i-1] - L[2*i-2]
      if M < S:
        M = S
    return M
  elif n == 3:
    return max(L[0], L[1], L[2])
  else:
    return max(L[-1] + dfs(n - 2, L[:-2]), dfs(n - 1, L[:-1]))
print(dfs(N, A))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

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

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

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


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

Submission status: Time Limit Exceeded

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

def zenbu(m, B):
    if m == 1:
        return B[0]
    elif m == 2:
        return max(B[0],B[1])
    elif m == 3:
        return max(B[0],B[1],B[2])
    elif m%2 == 0: #偶数の場合
        temp = 0
        for i in range(m//2-1):
            temp += B[i*2]
        return max(temp+ max(B[m-2],B[m-1]), zenbu(m-2, B[:-2])+ B[m-1])
    else:#奇数の場合
        temp = 0
        for i in range((m-1)//2):
            temp += B[i*2]
        return max(temp, zenbu(m-2,B[:-2])+ B[m-1], zenbu(m-3,B[:-3])+ max(B[m-2],B[m-1]))

ans = zenbu(n,A)

print(ans)