Problem:


Score : 600 points

Problem Statement

Given is an integer sequence A_1, ..., A_N of length N.

We will choose exactly \left\lfloor \frac{N}{2} \right\rfloor elements from this sequence so that no two adjacent elements are chosen.

Find the maximum possible sum of the chosen elements.

Here \lfloor x \rfloor denotes the greatest integer not greater than x.

Constraints

2 \leq N \leq 2\times 10^5

|A_i|\leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the maximum possible sum of the chosen elements.

Sample Input 1

6
1 2 3 4 5 6

Sample Output 1

12

Choosing 2, 4, and 6 makes the sum 12, which is the maximum possible value.

Sample Input 2

5
-1000 -100 -10 0 10

Sample Output 2

0

Choosing -10 and 10 makes the sum 0, which is the maximum possible value.

Sample Input 3

10
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5000000000

Watch out for overflow.

Sample Input 4

27
18 -28 18 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49

Sample Output 4

295



Sample input:
6
1 2 3 4 5 6


Sample output:
12

Submission status: Wrong Answer

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

if n % 2 == 0:
  print(max(sum(a[::2]), sum(a[1::2])))

else:
    a_2 = a[:-2]
    a_3 = a[1:]
    print(max(sum(a_2[::2]), sum(a_2[1::2]), sum(a_3[1::2])))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if n % 2 == 0:
    x = a[::2]
    y = a[1::2]
    print(max(sum(x), sum(y)))
else:
    x = a[::2]
    y = a[1::2]
    print(x)
    print(y)
    z = sum(x)
    print(max(z-a[0], sum(y), z-a[-1]))

Submission status: Time Limit Exceeded

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

print(dp[n+1][m])

Submission status: Time Limit Exceeded

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


INF=10**20
def main():
    N=ii()
    A=list(mi())

    sel_count = N//2
    X = []
    for i,a in enumerate(A):
        X.append((a,i))

    i = 0
    loop_count = 0
    Y = []
    X.sort(reverse=True)
    while i != sel_count:
        i = 0
        ans = 0
        ng_index = set()
        xi = loop_count
        while xi < len(X) and i < sel_count:
            current_max, j = X[xi]

            xi += 1
            if j in ng_index: continue
            ans += current_max
            
            ng_index.add(j-1)
            ng_index.add(j)
            ng_index.add(j+1)

            i += 1
        
        loop_count += 1
        
    print(ans)

    



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


INF=10**20
def main():
    N=ii()
    A=list(mi())

    sel_count = N//2
    X = []
    for i,a in enumerate(A):
        X.append((-1*a,i))

    i = 0
    loop_count = 0
    Y = []
    while i != sel_count:
        X += Y
        heapq.heapify(X)
        for _ in range(loop_count):
            _,_ = heapq.heappop(X)
        
        Y = []
        i = 0
        ans = 0
        ng_index = set()
        while X and i < sel_count:
            current_max, j = heapq.heappop(X)
            current_max *= -1

            Y.append((-1*current_max, j))
            if j in ng_index: continue
            ans += current_max
            
            ng_index.add(j-1)
            ng_index.add(j)
            ng_index.add(j+1)

            i += 1
        
    print(ans)

    



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


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


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

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

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

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, floor

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


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

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


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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

# 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])
dp = [[0]*(n//2 + 1) for i in range(n+1)]

for i in range(1, n+1):
    dp[i][0] = 0

# for j in range(1, n//2 + 1):
#     dp[1][j] = nums[0]
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])
# print(dp)

Submission status: Time Limit Exceeded

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(N+1)]

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][j] = max(dp[i-1][j], dp[i-2][j-1] + A[i-1])

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

Submission status: Time Limit Exceeded

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

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 >= n):
        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))

Submission status: Time Limit Exceeded

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 >= n):
        memo[(n, m)] = -float('inf')
        return -float('inf')
    
    res = -float('inf')
    for i in range(math.ceil(n/2)):
        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))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
m_INF = -10 ** 19
dp = [[m_INF] * N for _ in range(N)]
# dp[i][j] := i番目までの数列のうちj個選んだ場合の最大値
for i in range(N):
    for j in range(i//2,i//2+2):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i])
        elif i//2+1 >= j:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + A[i])
        else:
            break

#print(dp)
print(dp[-1][math.floor(N/2)])

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
m_INF = -10 ** 19
dp = [[m_INF] * N for _ in range(N)]
# dp[i][j] := i番目までの数列のうちj個選んだ場合の最大値
for i in range(N):
    for j in range(i//2,N):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i])
        elif i//2+1 >= j:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + A[i])
        else:
            break

#print(dp)
print(dp[-1][math.floor(N/2)])

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = list(map(int, input().split()))
m_INF = -10 ** 19
dp = [[m_INF] * N for _ in range(N)]
# dp[i][j] := i番目までの数列のうちj個選んだ場合の最大値
for i in range(N):
    for j in range(1,N):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i])
        elif i//2+1 >= j:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1] + A[i])
        else:
            break

#print(dp)
print(dp[-1][math.floor(N/2)])

Submission status: Time Limit Exceeded

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

def evensum(k,bn):
    seven=0
    if k%2==0:
        for i in range(1,k,2):
            seven+=bn[i]
        tmp=seven
        ans=seven
        for i in range(1,k,2):
            tmp=tmp+bn[i-1]-bn[i]
            if tmp>ans:
                ans=tmp
    return ans

if n%2==0:
    ans=evensum(n,an)
else:
    sodd=0
    for j in range(0,n,2):
        sodd+=an[j]
    ans=sodd-an[0]
    tmp=sodd-an[0]
    ss=0
    for j in range(2,n,2):
        tmp=tmp-an[j]+evensum(j,an[:j])-ss
        if ans<tmp:
            ans=tmp
        ss=evensum(j,an[:j])
print(ans)

Submission status: Time Limit Exceeded

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

def evensum(k,bn):
    seven=0
    if k%2==0:
        for i in range(1,k,2):
            seven+=bn[i]
        tmp=seven
        ans=seven
        for i in range(1,k,2):
            tmp=tmp+bn[i-1]-bn[i]
            if tmp>ans:
                ans=tmp
    return ans

if n%2==0:
    ans=evensum(n,an)
else:
    sodd=0
    for j in range(0,n,2):
        sodd+=an[j]
    ans=sodd-an[0]
    tmp=sodd-an[0]
    
    for j in range(2,n,2):
        tmp=tmp-an[j]+evensum(j,an[:j])-evensum(j-2,an[:(j-2)])
        if ans<tmp:
            ans=tmp
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math
from sys import stdin
import sys
sys.setrecursionlimit(10**9) 

N = stdin.readline().rstrip()
N=int(N)
a=list(map(int, stdin.readline().rstrip().split()))
nan=np.nan
dp = [[nan for i in range(N+1)]for i in range(N+1)]
dp[1][1]=a[0]
dp[2][1]=max(a[0],a[1])
for i in range(N+1):
    dp[i][0]=0
    
if N>=3:
    for i in range(3, N+1):
        for j in range(max(1,math.ceil((i-3)/2)), int((i+1)/2)+1):
            dp[i][j]=np.nanmax([dp[i-2][j-1]+a[i-1], dp[i-1][j]])

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

if N==2:    
    print(int(dp[2][1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

from sys import stdin

N = stdin.readline().rstrip()
N=int(N)
a=list(map(int, stdin.readline().rstrip().split()))


nan=np.nan

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

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


if N>=3:
    dp[3][0]=0
    for i in range(3, N+1):
        for j in range(max(1,math.ceil((i-3)/2)), int((i+1)/2)+1):
            dp[i][j]=np.nanmax([dp[i-2][j-1]+a[i-1], dp[i-1][j]])

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

if N==2:
    print(int(dp[2][1]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

DP[0][0] = A[0]
#for i in range(1,N):
#    DP[i][0] = max(DP[i-1][0],A[i])

#for i in range(1,N//2-1):
#    DP[2*i][i] = DP[2*(i-1)][i-1] + A[2*i]

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

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

DP = [[-10**9 for i in range((N+1)//2)] for i in range(N)]

DP[0][0] = A[0]
for i in range(1,N):
    DP[i][0] = max(DP[i-1][0],A[i])

for i in range(1,N//2-1):
    DP[2*i][i] = DP[2*(i-1)][i-1] + A[2*i]

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

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

Submission status: Time Limit Exceeded

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

DP = [[-10**9 for i in range((N+1)//2)] for i in range(N)]

DP[0][0] = A[0]
for i in range(1,N):
    DP[i][0] = max(DP[i-1][0],A[i])

for i in range(1,N//2-1):
    DP[2*i][i] = DP[2*(i-1)][i-1] + A[2*i]

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

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

Submission status: Time Limit Exceeded

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

DP = [[-10**9 for i in range((N+1)//2)] for i in range(N)]

DP[0][0] = A[0]
for i in range(1,N):
    DP[i][0] = max(DP[i-1][0],A[i])

for i in range(1,N//2-1):
    DP[2*i][i] = DP[2*(i-1)][i-1] + A[2*i]

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

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

Submission status: Time Limit Exceeded

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

for i in range(N):
    A[i] = [A[i],i]
    #A[i][0]:number,A[i][1]:index

A.sort(reverse = True)

sum = A[0][0]
index = [A[0][1]]
cnt = 1

for i in range(1,N):
    if A[i][1]+1 not in index and A[i][1]-1 not in index:
        sum += A[i][0]
        index.append(A[i][1])
        cnt += 1
        if cnt == N//2:
            break

print(sum)

Submission status: Time Limit Exceeded

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

for i in range(N):
    A[i] = [A[i],i]
    #A[i][0]:number,A[i][1]:index

A.sort(reverse = True)

sum = A[0][0]
index = [A[0][1]]
cnt = 1

for i in range(1,N):
    if A[i][1]+1 not in index and A[i][1]-1 not in index:
        sum += A[i][0]
        index.append(A[i][1])
        if len(index) == N//2:
            break

print(sum)

Submission status: Time Limit Exceeded

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

f = [0,1] * (N // 2)
g = []
if N % 2 == 0:
  for i in range(1, N, 2):
    e = [1,0] * (N // 2 -1) + [1]
    e[i:i] = [0]
    for j in range(N):
      if e[j] == 1:
        e[j] = d[j]
      if f[j] == 1:
        f[j] = d[j]
    g.append(sum(e))
    g.append(sum(f))
    
elif N % 2 == 1:
  for i in range(1, N, 2):
    for j in range(1, i, 2):
      e = [1,0] * (N // 2 -1) + [1]
      e[i:i] = [0]
      e[j:j] = [0]
      for k in range(N):
        if e[k] == 1:
          e[k] = d[k]
      g.append(sum(e))

  for l in range(0, N, 2):
    f = [0,1] * (N // 2)
    f[l:l] = [0]
    for m in range(N):
      if f[m] == 1:
        f[m] = d[m]
    g.append(sum(f))

print(max(g))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

INF = 2 ** 60
dp = defaultdict(lambda: -INF)

n = int(input())
a = list(map(int, input().split())) + [0] * 10

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

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

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

Submission status: Time Limit Exceeded

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

m = n//2
INF = 10**18
dp = [[-INF]*(m+1) 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: Time Limit Exceeded

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

m = n//2
INF = 10**18
dp = [[-INF]*(m+1) 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: Time Limit Exceeded

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

m = n//2
INF = 10**18
dp = [[-INF]*(m+1) 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])
            continue
        if 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: Time Limit Exceeded

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

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

else:
  for i in range(1,w+1):
    for k in range(i):
      dp[(2*i)-1][i] += a[2*k]
    dp[2*i][i]  = max(dp[(2*i)-1][i], dp[(2*i)-2][i-1]+a[(2*i)-1])
    dp[2*i+1][i]= max(dp[2*i][i],     dp[(2*i)-1][i-1]+a[2*i])

print(dp[n][w])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

m = n//2
INF = 10**18
dp = [[-INF]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in reversed(range(1, m+1)):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i-1])
            continue
        if 0 <= i-2:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+A[i-1])
print(dp[-1][m])

Submission status: Time Limit Exceeded

Solution code:
INF = -1000000000000001

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

a = int(n/2)

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

dpa[0][0] = 0
dpa[1][0] = 0
dpa[1][1] = l[0]
j = 1
for i in range(2,n+1):
	if i == j*2:
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
	else:
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
		if (i != n):
			j += 1
#			print(i,j,dpa[i][j])
#			print("   ",i-2,j-1,dpa[i-2][j-1],"")
			dpa[i][j] = dpa[i-2][j-1]+l[i-1]

#print(dpa)
print(dpa[n][a])

Submission status: Time Limit Exceeded

Solution code:
INF = -1000000000000001

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

a = int(n/2)

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

dpa[0][0] = 0
dpa[1][0] = 0
dpa[1][1] = l[0]
for i in range(2,n+1):
	j = int(i / 2)
	
	if i == j*2:
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
	else:
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
		if (i != n):
			j += 1
#			print(i,j,dpa[i][j])
#			print("   ",i-2,j-1,dpa[i-2][j-1],"")
			dpa[i][j] = dpa[i-2][j-1]+l[i-1]

#print(dpa)
print(dpa[n][a])

Submission status: Time Limit Exceeded

Solution code:
INF = -1000000000000001

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

a = int(n/2)

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

dpa[0][0] = 0
dpa[1][0] = 0
dpa[1][1] = l[0]
for i in range(2,n+1):
	if i % 2 == 0:
		j = int(i / 2)
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
	else:
		j = int((i-1)/2)
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
		if (i != n):
			j += 1
#			print(i,j,dpa[i][j])
#			print("   ",i-2,j-1,dpa[i-2][j-1],"")
			dpa[i][j] = dpa[i-2][j-1]+l[i-1]

#print(dpa)
print(dpa[n][a])

Submission status: Time Limit Exceeded

Solution code:
INF = -1000000000000001

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

a = int(n/2)

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

dpa[0][0] = 0
for i in range(1,n+1):
	dpa[i][0] = 0
	if i % 2 == 0:
		j = int(i / 2)
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
	elif i == 1:
		dpa[1][1] = l[0]
	else:
		j = int((i-1)/2)
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
		if (i != n):
			j += 1
#			print(i,j,dpa[i][j])
#			print("   ",i-2,j-1,dpa[i-2][j-1],"")
			dpa[i][j] = dpa[i-2][j-1]+l[i-1]

#print(dpa)
print(dpa[n][a])

Submission status: Time Limit Exceeded

Solution code:
INF = -1000000000000001

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

dpa[0][0] = 0
for i in range(1,n+1):
	dpa[i][0] = 0
	if i % 2 == 0:
		j = int(i / 2)
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
	elif i == 1:
		dpa[1][1] = l[0]
	else:
		j = int((i-1)/2)
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
#		print(i,j,dpa[i][j])
		if (i != n):
			j += 1
#			print(i,j,dpa[i][j])
#			print("   ",i-2,j-1,dpa[i-2][j-1],"")
			dpa[i][j] = dpa[i-2][j-1]+l[i-1]

#print(dpa)
print(dpa[n][a])

Submission status: Time Limit Exceeded

Solution code:
import sys
#import resource
#import pprint
sys.setrecursionlimit(20000000)
#print(sys.getrecursionlimit())

n = int(input())
ls = input().split()
lst = [int(e) for e in ls]
m = n //2
d = n % 2

def sum_res(plst):
  no = len(plst)
  if no <= 3:
    return max(plst)
  ret = []
  if no % 2 == 0:
    ret.append(plst[0]+sum_res(plst[2:no]))
    ret.append(sum_res(plst[0:no-2])+plst[no-1])
  else:
    ret.append(sum_res(plst[1:no]))
    if no >= 5:
      ret.append(plst[0]+sum_res(plst[2:no]))
  return max(ret)
#print(lst[26])
mmm = sum_res(lst)
print(mmm)

Submission status: Time Limit Exceeded

Solution code:
import pprint
n = int(input())
ls = input().split()
lst = [int(e) for e in ls]
m = n //2
d = n % 2

def sum_res(plst):
  no = len(plst)
  ret = []
  if no % 2 == 0:
    m = no // 2
    for i in range(m+1):
      sum = 0
      for j in range(m):
        if j < i :
          sum += plst[j*2]
        else:
          sum += plst[j*2+1]
      ret.append(sum)
  else:
    if no == 1:
      return plst[0]
    if no == 3:
      return max(plst)

    ret.append(sum_res(plst[1:no]))

    if no >= 5:
      ret.append(plst[0]+sum_res(plst[2:no]))
  return max(ret)

mmm = sum_res(lst)
print(mmm)

Submission status: Time Limit Exceeded

Solution code:
import pprint
n = int(input())
ls = input().split()
lst = [int(e) for e in ls]
m = n //2
d = n % 2

def sum_res(plst):
  no = len(plst)
  ret = []
  if no % 2 == 0:
    m = no // 2
    for i in range(m+1):
      sum = 0
      for j in range(m):
        if j < i :
          sum += plst[j*2]
        else:
          sum += plst[j*2+1]
      ret.append(sum)
  else:
    if no == 1:
      return plst[0]
    if no == 3:
      return max(plst)

    ret.append(sum_res(plst[1:no]))

    if no >= 5:
      ret.append(plst[0]+sum_res(plst[2:no-1]))

    if no >= 5:
      ret.append(plst[0]+sum_res(plst[2:no-2])+plst[no-1])
  return max(ret)

mmm = sum_res(lst)
print(mmm)

Submission status: Time Limit Exceeded

Solution code:
import pprint
n = int(input())
ls = input().split()
lst = [int(e) for e in ls]
m = n //2
d = n % 2

def sum_lst(plst):
  no = len(plst)
  ret = []
  if no % 2 == 0:
    m = no // 2
    for i in range(m+1):
      sum = 0
      for j in range(m):
        if j < i :
          sum += plst[j*2]
        else:
          sum += plst[j*2+1]
      ret.append(sum)
  else:
    if no == 1:
      return [plst[0]]
    if no == 3:
      return [max(plst)]

    for elst in sum_lst(plst[1:no]):
      ret.append(elst)

    if no >= 5:
      for elst in sum_lst(plst[2:no-1]):
        ret.append(plst[0]+elst)

    if no >= 5:
      for elst in sum_lst(plst[2:no-2]):
        ret.append(plst[0]+elst+plst[no-1])
  return [max(ret)]    

mmm = sum_lst(lst)
print(mmm[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000000000)
N = int(input())
import math
l = [int(x) for x in input().split()]
tobi = [0]*(math.ceil(N/2))
tobi[0] = l[0]
for i in range(1,math.ceil(N/2)):
    tobi[i] = tobi[i-1] + l[i*2]
def motomeru(x,y):
    if y == 0 or x == 0 or x == 1:
        return 0
    elif x % 2 == 0:
        return max(motomeru(x-2,y-1)+l[x-1],tobi[math.floor((x-1)/2)])
    else:
        return max(motomeru(x-2,y-1)+l[x-1],motomeru(x-1,y))
print(motomeru(N,N//2))

Submission status: Time Limit Exceeded

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

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

def solve_even(a, n):
  s = sum(a[::2])
  ans = s
  i = n - 2
  while i >= 0:
    s += a[i+1] - a[i]
    ans = max(ans, s)
    i -= 2
  return ans

def solve_odd(a, n):
  if n == 1:
    return 0
  ans = solve_even(a[:-1], n-1)
  s = a.pop()
  a.pop()
  ans = max(ans, s + solve_odd(a, n-2))
  return ans
  

if N%2 == 0:
  print(solve_even(A, N))
else:
  print(solve_odd(A, N))

Submission status: Time Limit Exceeded

Solution code:
import pprint
n = int(input())
ls = input().split()
lst = [int(e) for e in ls]
#print(lst)
m = n //2
d = n % 2
#print(m,d)

def ns ( l1, l2 ):
  res = 0
  for i in range(len(l1)):
    res += l1[i]*l2[i]
  return res

def mklst(no):
  ret = []
  if no % 2 == 0:
    m = no // 2
    for i in range(m+1):
      wk = [0]*no
      for j in range(m):
        if j < i :
          wk[j*2] = 1
        else:
          wk[j*2+1] = 1
      ret.append(wk)
  else:
    #wk = [0]*no
    if no == 1:
      ret.append([0])
      return ret
    if no == 3:
      ret.append([1,0,0])
      ret.append([0,1,0])
      ret.append([0,0,1])
      return ret

    for elst in mklst(no-1):
      ret.append([0]+elst)

    if no >= 5:
      for elst in mklst(no-3):
        ret.append([1,0]+elst+[0])

    if no >= 5:
      for elst in mklst(no-4):
        ret.append([1,0]+elst+[0,1])
      
  return ret    

mmm = lst[0]
for el in mklst(n):
  ans = ns(lst,el)
  if mmm < ans :
    mmm = ans

print(mmm)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

INF = 2 ** 60
dp = defaultdict(lambda: -INF)

n = int(input())
a = list(map(int, input().split())) + [0] * 10

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

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

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

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

for i in range(0,n+1):
	dpa[i][0] = 0

for i in range(1,n+1):
	if i % 2 == 0:
		j = int(i / 2)
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
	else:
		j = int((i-1)/2)
		dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])
		if (i != n):
			j += 1
#			print(i,j,i-2,j-1,i-1,j)
			dpa[i][j] = max(dpa[i-2][j-1]+l[i-1],dpa[i-1][j])

#print(dpa)
print(dpa[n][a])

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 2*y-1 == x:
		for i in range(0,x,2):
			ret+= l[i]
	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,"->",x-2,y-1,x-1,y)
#	print(x,y,ret)
	dpa[x][y] = ret
	return ret

print(dp(n,a))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

def find(idx, c, arr, tb):

    if c == 0:
        return 0

    if idx <= 0:
        return -100000

    if (idx, c) in tb:
        return tb[(idx, c)]

    rs = find(idx - 2, c - 1, arr, tb) + arr[idx - 1]
    rs = max(rs, find(idx - 1, c, arr, tb))

    tb[(idx, c)] = rs
    return rs


def main():

    n = int(input())
    arr = [int(e) for e in input().split(' ')]
    print(find(n, n // 2, arr, {}))
    return 0


main()