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(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	n = II()
	a = LI()
	a = [0]+a
	dp_t = [[-10**9-1 for _ in range(n//2+2)] for _ in range(n+1)]
	dp_f = [[-10**9-1 for _ in range(n//2+2)] for _ in range(n+1)]
	dp_f[0][0]=0
	for i in range(1,n+1):
		dp_f[i][(i-1)//2]=max(dp_f[i-1][(i-1)//2], dp_t[i-1][(i-1)//2])
		dp_t[i][(i-1)//2]=dp_f[i-1][(i-1)//2-1]+a[i]
		dp_f[i][(i-1)//2+1]=max(dp_f[i-1][(i-1)//2+1], dp_t[i-1][(i-1)//2+1])
		dp_t[i][(i-1)//2+1]=dp_f[i-1][(i-1)//2]+a[i]
	print(max(dp_t[n][n//2],dp_f[n][n//2]))
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	n = II()
	a = LI()
	a = [0]+a
	dp = [[[-10**9,-10**9] for _ in range(n//2+2)] for _ in range(n+1)]
	dp[1][1][1]=a[1]
	for i in range(0,2):
		dp[i][0]=[0,0]
	for i in range(1,n+1):
		dp[i][(i-1)//2][0]=max(dp[i-1][(i-1)//2][0], dp[i-1][(i-1)//2][1])
		dp[i][(i-1)//2][1]=max(dp[i-1][(i-1)//2-1][0]+a[i], dp[i-2][(i-1)//2-1][0]+a[i])
		dp[i][i//2][0]=max(dp[i-1][i//2][0], dp[i-1][i//2][1])
		dp[i][i//2][1]=max(dp[i-1][i//2-1][0]+a[i], dp[i-2][i//2-1][0]+a[i])
		dp[i][(i+1)//2][1]=max(dp[i-1][(i+1)//2-1][0]+a[i], dp[i-2][(i+1)//2-1][0]+a[i])
	print(max(dp[n][n//2]))
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	n = II()
	a = LI()
	a = [0]+a
	dp = [[[-10**9,-10**9] for _ in range(n//2+2)] for _ in range(n+1)]
	dp[1][1][1]=a[1]
	for i in range(0,2):
		dp[i][0]=[0,0]
	for i in range(1,n+1):
		if i-1 >= 3:
			dp[i][(i-1)//2][0]=max(dp[i-1][(i-1)//2][0], dp[i-1][(i-1)//2][1])
			dp[i][(i-1)//2][1]=max(dp[i-1][(i-1)//2-1][0]+a[i], dp[i-2][(i-1)//2-1][0]+a[i])
		if i >= 2:
			dp[i][i//2][0]=max(dp[i-1][i//2][0], dp[i-1][i//2][1])
			dp[i][i//2][1]=max(dp[i-1][i//2-1][0]+a[i], dp[i-2][i//2-1][0]+a[i])
		if i >= 2:
			dp[i][(i+1)//2][1]=max(dp[i-1][(i+1)//2-1][0]+a[i], dp[i-2][(i+1)//2-1][0]+a[i])
	print(max(dp[n][n//2]))
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	n = II()
	a = LI()
	a = [0]+a
	dp = [[[-10**9,-10**9] for _ in range(n//2+2)] for _ in range(n+1)]
	dp[1][1][1]=a[1]
	for i in range(0,n+1):
		dp[i][0]=[0,0]
	for i in range(1,n+1):
		if i-1 >= 3:
			dp[i][(i-1)//2][0]=max(dp[i-1][(i-1)//2][0], dp[i-1][(i-1)//2][1])
			dp[i][(i-1)//2][1]=max(dp[i-1][(i-1)//2-1][0]+a[i], dp[i-2][(i-1)//2-1][0]+a[i])
		if i >= 2:
			dp[i][i//2][0]=max(dp[i-1][i//2][0], dp[i-1][i//2][1])
			dp[i][i//2][1]=max(dp[i-1][i//2-1][0]+a[i], dp[i-2][i//2-1][0]+a[i])
		if i >= 2:
			dp[i][(i+1)//2][1]=max(dp[i-1][(i+1)//2-1][0]+a[i], dp[i-2][(i+1)//2-1][0]+a[i])
	print(max(dp[n][n//2]))
if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

import sys
from collections import defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

# dp0[i][j] := i個目の要素まで見て、選んだ要素-選ばなかった要素=jで、直前を使っていない時の最大値
dp0 = [defaultdict(lambda: -INF) for i in range(N+1)]
# dp1[i][j] := i個目の要素まで見て、選んだ要素-選ばなかった要素=jで、直前を使った時の最大値
dp1 = [defaultdict(lambda: -INF) for i in range(N+1)]
dp0[0][0] = 0
for i, a in enumerate(A):
    for j in range(-2, 2):
        if j != -2:
            # 今回のaを使わない
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp0[i][j])
            dp0[i+1][j-1] = max(dp0[i+1][j-1], dp1[i][j])
        # 今回のaを使う
        dp1[i+1][j+1] = max(dp1[i+1][j+1], dp0[i][j] + a)
# 最終的に欲しい位置は偶奇で場合分け
if N % 2 == 0:
    # 偶数の時は使った数と使わなかった数が同じ
    ans = max(dp0[N][0], dp1[N][0])
else:
    # 奇数の時は使わなかった数が1つ多い
    ans = max(dp0[N][-1], dp1[N][-1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,*l=map(int,open(0).read().split())
p=0,0
d=p
i=0
for l in l:d+=max(l+d[-2],[d,p][i&1][-1]),;p+=l+p[-2],;i+=1
print(d[-1])

Submission status: Time Limit Exceeded

Solution code:
n,*l=map(int,open(0).read().split())
p=0,0
d=p
for l in l:d+=max(l+d[-2],[d,p][len(d)&1][-1]),;p+=l+p[-2],
print(d[-1])

Submission status: Time Limit Exceeded

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

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

def f(i,j):
  a = 0
  if not 2*j-1 <= i <= 2*j+1+(N-2*int(N/2)):
    a = 0
  elif i == 1 and j == 0:
    a = 0
  elif i == 1 and j == 1:
    a = A[0]
  elif i == 2 and j == 1:
    a = max(A[0],A[1])
  elif i == 2 and j == 0:
    a = 0
  else:
    a = max(f(i-2,j-1)+A[i-1],f(i-1,j))
  return a

print(f(N,int(N/2)))

Submission status: Time Limit Exceeded

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

dp = [[0 for i in range(n // 2 + 1)] for j in range(n + 1)]

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(2*1000000)

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

dp_dict = {}

inf = -1*1000000000


def dp(i, j):
    if j == 1:
        return A[i]
    if i+2 >= N:
        return inf
    if N//2-j < i//2-1:
        return inf
    temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
    dp_dict[(i, j)] = temp
    return temp


select = N//2
if select == 1:
    print(max(A))
else:
    print(dp(0, select))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)

def solve(n,a):
    wa=0
    for i in range(n):
        if(i%2==0):
            wa+=a[i]
    kotae=wa
    for i in range(n//2):
        wa+=a[(n//2-i-1)*2+1]
        wa-=a[(n//2-i-1)*2]
        if(wa>kotae):
            kotae=wa
    return kotae

def dfs(n,a,k):
    if(k==1):
        return max(a)
    ari=a[n-1]+dfs(n-2,a[:n-2],k-1)
    if(n==k*2-1):
        return ari
    nasi=dfs(n-1,a[:n-1],k)
    return max(ari,nasi)

n=int(input())

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

if(n%2==0):
    print(solve(n,a))
else:
    print(dfs(n,a,n//2))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


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

    @lru_cache(None)
    def f(i, j):
        if i < 0 or j < 0:
            return -INF
        if i == 0:
            return -INF
        if j == 0:
            return 0
        if j == 1:
            return max(A[:i])
        return max(A[i - 1] + f(i - 2, j - 1), f(i - 1, j))

    print(f(N, math.floor(N / 2)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


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

    @lru_cache()
    def f(i, j):
        if i < 0 or j < 0:
            return -INF
        if i == 0:
            return -INF
        if j == 0:
            return 0
        if j == 1:
            return max(A[:i])
        return max(A[i - 1] + f(i - 2, j - 1), f(i - 1, j))

    print(f(N, math.floor(N / 2)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)

def solve(n,a):
    wa=0
    for i in range(n):
        if(i%2==0):
            wa+=a[i]
    kotae=wa
    for i in range(n//2):
        wa+=a[(n//2-i-1)*2+1]
        wa-=a[(n//2-i-1)*2]
        if(wa>kotae):
            kotae=wa
    return kotae

def dfs(n,a,k):
    if(k==1):
        return max(a)
    ari=a[n-1]+dfs(n-2,a[:n-2],k-1)
    if(n==k*2-1):
        return ari
    nasi=dfs(n-1,a[:n-1],k)
    return max(ari,nasi)

n=int(input())

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


print(dfs(n,a,n//2))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7


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

    DP = [[0] * (N + 1) for _ in range(N + 1)]
    DP[1][1] = A[0]

    for i in range(2, N + 1):
        a = math.floor((i - 1) / 2)
        b = math.floor((i + 1) / 2)
        for j in range(a, b + 1):
            DP[i][j] = max(DP[i - 1][j], DP[i - 2][j - 1] + A[i - 1])
    print(int(DP[N][math.floor(N / 2)]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(2*1000000)

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

#dp_dict = {}


def dp(i, j):
    #print(i, j)
    if i >= N:
        return (-1*1000000000)
    if (N//2)-j < (i-1)//2:
        return (-1*1000000000)
    if j == 1:
        return A[i]
    # if (i, j) in dp_dict:
        # return dp_dict[(i, j)]
    else:
        temp = max([dp(i+2, j-1)+A[i], dp(i+1, j)])
        #dp_dict[(i, j)] = temp
        return temp


select = N//2
if select == 1:
    print(max(A))
else:
    print(dp(0, select))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

import itertools
n=n0()
a=n1()
if n%2==0:
    ans=max(sum(a[::2]),sum(a[1::2]))
    if n>=6:
        l=[1]*(n//2-2)
        l.append(2)
        for x in itertools.permutations(l):
            s=a[0]
            i=0
            for y in list(x):
                i+=y+1
                s+=a[i]
            ans=max(ans,s)
else:
    ans=max(sum(a[::2]),sum(a[1::2]),sum(a[2::2]))
    if n>=5:
        l=[1]*(n//2-2)
        l.append(2)
        for x in itertools.permutations(l):
            s=a[0]
            i=0
            for y in list(x):
                i+=y+1
                s+=a[i]
            ans=max(ans,s)
        for x in itertools.permutations(l):
            s=a[1]
            i=0
            for y in list(x):
                i+=y+1
                s+=a[i]
            ans=max(ans,s)
        l=[1]*(n//2-2)
        l.append(3)
        for x in itertools.permutations(l):
            s=a[0]
            i=0
            for y in list(x):
                i+=y+1
                s+=a[i]
            ans=max(ans,s)
    if n>=7:
        l=[1]*(n//2-3)
        l.append(2)
        l.append(2)
        for x in itertools.permutations(l):
            s=a[0]
            i=0
            print(list(x))
            for y in list(x):
                i+=y+1
                s+=a[i]
            ans=max(ans,s)



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

    ninf = -10 ** 10

    memo = [[0] * (N2 + 2) for _ in range(N + 2)]

    def search(i, c, memo):
        if c >= N2:
            return 0
        if i >= N:
            return ninf
        if memo[i][c]:
            return memo[i][c]

        v1 = A[i] + search(i + 2, c + 1, memo)
        v2 = search(i + 1, c, memo)
        ret = max(v1, v2)

        memo[i][c] = ret
        return ret

    val = search(0, 0, memo)
    print(val)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def calc():
  n=int(input())
  arr=list(map(int,input().split()))
  acum1=[0]
  acum2=[0]
  for i in range(n):
    if i%2==0:
      acum1.append(acum1[-1]+arr[i])
      acum2.append(acum2[-1]+0)
    else:
      acum1.append(acum1[-1]+0)
      acum2.append(acum2[-1]+arr[i])
  if n%2==0:
    ans=max(acum1[n-1],acum2[n])
    for i in range(1,n+1,2):
      if i+3>n:
        continue
      tmp=(acum1[i]-acum1[0])+(acum2[n]-acum2[i+2])
      ans=max(ans,tmp)
  else:
    ans=max(acum1[n-2]-acum1[0],acum2[n-1]-acum2[1],acum1[n]-acum1[2])
    for i in range(1,n+1,2):
      if i+3>n-1:
        continue
      tmp=(acum1[i]-acum1[0])+(acum2[n-1]-acum2[i+2])
      ans=max(ans,tmp)
    for i in range(2,n+1,2):
      if i+3>n:
        continue
      tmp=(acum2[i]-acum2[1])+(acum1[n]-acum1[i+2])
      ans=max(ans,tmp)
    for i in range(1,n+1,2):
      if i+4>n:
        continue
      tmp=(acum1[i]-acum1[0])+(acum1[n]-acum1[i+3])
      ans=max(ans,tmp)
    for i in range(1,n+1,2):
      for j in range(i+3,n+1,2):
        if j+3>n:
          continue
        tmp=(acum1[i]-acum1[0]-acum2[i+2])+(acum2[j]+acum1[n]-acum1[j+2])
        ans=max(ans,tmp)
  print(ans)
calc()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)
def solve(pick, idx):

    if pick == 0: return 0
    if idx >= n: return -float('inf')
    if (pick, idx) in dp: return dp[pick, idx]
    # if n-idx+2 < pick*2: return -float('inf')
    total = max(A[idx] + solve(pick-1, idx+2), solve(pick, idx+1))

    dp[(pick, idx)] = total
    return total

n = int(input())
A = list(map(int, input().split()))
dp = {}
pick = n//2

print(solve(pick, 0))

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 sys
sys.setrecursionlimit(10**8)

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

a_cs = [0] * (n + 1)
a_cs[-2] = a[-1]
for i in reversed(range(n - 1)):
    a_cs[i] = a[i] + a_cs[i + 2]
# print(a_cs)


def func(i):
    if i == n:
        return 0
    if i == n - 1:
        return a[-1]

    m = n - i
    if m % 2 == 0:
        ans0 = a[i] + func(i + 2)
        ans1 = a_cs[i + 1]
        ans = max(ans0, ans1)
    else:
        ans0 = a[i + 0] + func(i + 2)
        ans1 = a[i + 1] + func(i + 3)
        ans2 = a_cs[i + 2]
        ans = max(ans0, ans1, ans2)

    return ans


ans = func(0)

print(ans)

Submission status: Time Limit Exceeded

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

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

d = {}


def func(b, m):
    if m == 0:
        return 0
    if m == 1:
        return b[0]
    if m == 2:
        return max(b[0], b[1])
    if m in d:
        return d[m]

    if m % 2 == 0:
        ans0 = b[0] + func(b[2:], m - 2)
        ans1 = sum(b[i] for i in range(1, m, 2))
        ans = max(ans0, ans1)
    else:
        ans0 = b[0] + func(b[2:], m - 2)
        ans1 = b[1] + func(b[3:], m - 3)
        ans2 = sum(b[i] for i in range(2, m, 2))
        ans = max(ans0, ans1, ans2)

    d[m] = ans
    return ans


ans = func(a, n)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 9)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
INF = 10 ** 17

def F(index, n):
    if index >= N:
        return -INF
    if N - index + 2 < 2 * n:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(A[index:])
    ret = max(A[index] + F(index+2, n-1), F(index+1, n))
    return ret

answer = F(0, N//2)
print(answer)

Submission status: Time Limit Exceeded

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

dp = [[float('-inf') for _ in range(n+1)] for _ in range(ha+1)]

s = 1
for i in range(1,ha+1):
    for j in range(s,n+1):
        if i == 1:
            dp[i][j] = max(dp[i][j-1],a[j-1])
        else:
            if (j-2 >= 0) & (j>i):
                dp[i][j] = max(dp[i][j-1], dp[i-1][j-2]+a[j-1])
    s += 2
print(dp[-1][-1])

Submission status: Time Limit Exceeded

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

if  N % 2 == 0:
    M =  N // 2
    even_A = [A[i* 2] for i in range(M)]
    odd_A = [A[i* 2 + 1] for i in range(M)]
    even_sum = []
    _sum = 0
    for a in even_A:
        _sum += a
        even_sum.append(_sum)
    odd_sum = []
    _sum = 0
    for a in odd_A:
        _sum += a
        odd_sum.append(_sum)
    ans = max(odd_sum[-1], even_sum[-1])
    for i in range(M):
            x = even_sum[i] + odd_sum[-1] - odd_sum[i]
            ans = max(ans, x)
    print(ans)
    exit()
M =  N // 2
# evenが元一つ多い
even_A = [A[i* 2] for i in range(M+1)]
odd_A = [A[i* 2 + 1] for i in range(M)]
even_sum = []
_sum = 0
for a in even_A:
    _sum += a
    even_sum.append(_sum)
odd_sum = []
_sum = 0
for a in odd_A:
    _sum += a
    odd_sum.append(_sum)
# 全て奇数
all_even = even_sum[-1] - min(even_A)

ans = all_even
for i in range(M):
        x = even_sum[i] + odd_sum[-1] - odd_sum[i]
        y = odd_sum[i] + even_sum[-1] - even_sum[i+1]
        ans = max(ans, x, y)
        for k in range(i+1, M):
           z = even_sum[i] + odd_sum[k] - odd_sum[i] + even_sum[-1] - even_sum[k+1]
           ans = max(ans, z)

print(ans)

Submission status: Time Limit Exceeded

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

t = n // 2
invalid = -10**15
dp = [[invalid] * (t+2) for _ in range(n+3)]

for i in range(n, 0, -1):
    m = (n-i) // 2
    for j in range(m, m+2):
        if j == 0:
            pass
        elif j == 1:
            dp[i][j] = a[i-1]
        else:
            dp[i][j] = max(dp[i+2][j-1], dp[i+3][j-1], dp[i+4][j-1]) + a[i-1]

print(max(dp[1][t], dp[2][t], dp[3][t]))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N = int(input())
a = list(map(int, input().split()))


def max_even(n, a): # aからn個選ぶ
    #print('eve', n, a)
    if len(a) <= 2:
        #print(max(a))
        return max(a)
    else:
        #print(max(a[0]+max_even(n-1, a[2:]), a[1]+max_odd(n-1, a[3:])))
        return max(a[0]+max_even(n-1, a[2:]), a[1]+max_odd(n-1, a[3:]))

def max_odd(n, a): # aからn個選ぶ
    #print('odd', n, a)
    if len(a) <= 3:
        if n == 1:
            #print(max(a))
            return max(a)
        elif len(a)==3 and n==2:
            #print(a[0]+a[2])
            return a[0]+a[2]
    elif len(a)//2+1 == n:
        return sum(a[::2])
    else:
        #print(max(a[0]+max_odd(n-1, a[2:]), a[1]+max_even(n-1, a[3:]), a[2]+max_odd(n-1, a[4:])))
        return max(a[0]+max_odd(n-1, a[2:]), a[1]+max_even(n-1, a[3:]), a[2]+max_odd(n-1, a[4:]))


if N%2==0:
    ans = max_even(N//2, a)
else:
    ans = max_odd(N//2, a)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:


n = 0
a = []

def format_input(filename = None):
	global n
	global a
	if filename == None:
		n = int(input())
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 2 * 10**5)
		a = [rng(-1 * 10**9, 10**9) for i in range(n)]
		print(n)
		print(' '.join(list(map(str, a))))

def get_answer():
	odd = [0]
	even = [0]
	for i in range(n // 2):
		odd.append(odd[-1] + a[2*i])
		even.append(even[-1] + a[2*i+1])
	if n % 2 == 1:
		odd.append(odd[-1] + a[-1])

	answer = -1 * 10**9 * n
	if n % 2 == 0:
		for i in range(n // 2 + 1):
			answer = max(answer, odd[i] - even[i] + even[-1])
	else:
		for i in range(n // 2 + 2):
			if i < n // 2 + 1:
				for j in range(i+1):
					answer = max(answer, odd[j] - even[j] + even[i] - odd[i+1] + odd[-1])
			else:
				for j in range(i):
					answer = max(answer, odd[j] - even[j] + even[-1])
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
L=list(map(int,input().split()))
D=[{}for i in range(N)]
D[0][(0,0)]=L[0]
D[0][(1,1)]=0

for i in range(1,N):
    for k,v in D[i-1].items():
        #print(k)
        if k[0]==0:
            if k[1]+1<=(N-N//2):
                if (1,k[1]+1) in D[i]:
                    D[i][(1,k[1]+1)]=max(D[i][(1,k[1]+1)],v)
                else:
                    D[i][(1,k[1]+1)]=v
        else:
            if (0,k[1]) in D[i]:
                D[i][(0,k[1])]=max(D[i][(0,k[1])],v+L[i])
            else:
                D[i][(0,k[1])]=v+L[i]
            if k[1]+1<=(N-N//2):
                if (1,k[1]+1) in D[i]:
                    D[i][(1,k[1]+1)]=max(D[i][(1,k[1]+1)],v)
                else:
                    D[i][(1,k[1]+1)]=v
ans=-(10**9+7)
for i in D[-1].values():
    if ans<i:
        ans=i
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

dp = [[minv]*(N//2+1) for _ in range(N+1)]
for i in range(1, N+1):
    dp[i][1] = max(A[:i])

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

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

Submission status: Time Limit Exceeded

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

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


def func(b, m):
    if m == 0:
        return 0
    if m == 1:
        return b[0]

    if m % 2 == 0:
        ans0 = b[0] + func(b[2:], m - 2)
        ans1 = sum(b[i] for i in range(1, m, 2))
        ans = max(ans0, ans1)
    else:
        ans0 = b[0] + func(b[2:], m - 2)
        ans1 = b[1] + func(b[3:], m - 3)
        ans2 = sum(b[i] for i in range(2, m, 2))
        ans = max(ans0, ans1, ans2)

    return ans


ans = func(a, n)

print(ans)

Submission status: Time Limit Exceeded

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

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

d = {}


def func(b, m):
    if m == 0:
        return 0
    if m == 1:
        return b[0]
    if m in d:
        return d[m]

    if m % 2 == 0:
        ans0 = b[0] + func(b[2:], m - 2)
        ans1 = sum(b[i] for i in range(1, m, 2))
        ans = max(ans0, ans1)
    else:
        ans0 = b[0] + func(b[2:], m - 2)
        ans1 = b[1] + func(b[3:], m - 3)
        ans2 = sum(b[i] for i in range(2, m, 2))
        ans = max(ans0, ans1, ans2)

    d[m] = ans
    return ans


ans = func(a, n)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
num = int(input())
arr = [int(i ) for i in input().split()]
ans = 0
counta = 0
half = num // 2
idx_arr = np.argsort(arr).tolist()
while(counta < half):
    idx = idx_arr.pop()
    ans += arr[idx]
    counta += 1
    try:
        idx_arr.remove(idx - 1)
    except:
        pass
    try:
        idx_arr.remove(idx + 1)
    except:
        pass
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(j) for j in input().split()]
import numpy as np
dp=np.array([[0]*n for i in range((n//2)+1)])

def f(l,m):
    if l==[]:
        return -10**100
    if m==1:
        return max(l)
    if -(-len(l)//2)<m:
        return -10**100
    return max(f(l[1:],m),l[0]+f(l[2:],m-1))

print(f(a,n//2))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

def calc(i,j):
    d = defaultdict(lambda:defaultdict(int))
    ret = -float('inf')
    if j==0:
        return 0
    if (N-i+1)//2 < j:
        return ret
    else:
        if i <= N-1:
            if d[i+2][j-1]:
                ret = max(ret,d[i+2][j-1])
            else:
                ret = max(ret,A[i]+calc(i+2,j-1))
        if i+1 <= N-1:
            if d[i+3][j-1]:
                ret = max(ret,d[i+3][j-1])
            else:
                ret = max(ret,A[i+1]+calc(i+3,j-1))
        d[i][j] = ret
        return ret


N = I()
A = LI()


if N%2 == 0:
    print(calc(0,N//2))
else:
    a1 = calc(0,N//2)
    n = 0
    for i in range(2,N,2):
        n += A[i]
    print(max(a1,n))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
n=int(input())
a=[int(i) for i in input().split()]

selectnum=n//2


def maximum(number):
    n=len(number)
    now=0
    for i in range(0,len(number)-1,2):
        now+=number[i]
    if n%2==0:
        if n==2:
            return max(number[0],number[1])
        return max(maximum(number[:-2])+number[-1],now)
    else:
        if n==3:
            return max(number[0],number[1],number[2])
        return max(now,maximum(number[:-3])+number[-2],maximum(number[:-2])+number[-1])
        
    
    
    
print(maximum(a))

Submission status: Time Limit Exceeded

Solution code:

N = int(input())


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


dp = [[-(2**63)] * (N + 2) for _ in range((N // 2) + 5)]
for i in range(N + 2):
    dp[0][i] = 0

for i, v in enumerate(A):
    for taken in range(1, len(dp)):
        dp[taken][i+2] = max(dp[taken][i+1], dp[taken-1][i] + v)
target = N // 2

# for d in dp:
#     print(d)

print(max(dp[target]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
num = int(input())
arr = np.array([int(i ) for i in input().split()], dtype='int64')
ans = 0
counta = 0
half = num // 2
selected = []
idx_arr = np.argsort(arr).tolist()
itrator = 0
while(counta < half):
    idx = idx_arr.pop()
    ans += arr[idx]
    counta += 1
    try:
        idx_arr.remove(idx - 1)
    except:
        pass
    try:
        idx_arr.remove(idx + 1)
    except:
        pass
    
    itrator += 1
print(ans)