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)

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):
    if(n==3):
        return max(a)
    #kotae=solve(n-1,a[1:])+a[0]
    #kotae=max(kotae,solve(n-1,a[:n-1])+a[n-1])
    #kotae=max(kotae,dfs(n-2,a[1:n-1]))
    #print(kotae)
    kotae=dfs(n-2,a[2:])+a[0]
    kotae=max(kotae,dfs(n-2,a[:n-2])+a[n-1])
    temp=0
    for i in range(n//2):
        temp+=a[i*2+1]
    kotae=max(temp,kotae)
    return kotae

n=int(input())

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


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

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):
    for j in range(N//2,0,-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 math import factorial
def f(nn):
  while True:
    for i in range(len(nn)):
      if nn[i] == 1:
        nn[i] = 0
      else:
        nn[i] += 1
        break
    br = True
    cnt = 0
    for i in range(len(nn)-1):
      if nn[i] == 1:
        cnt += 1
        if nn[i+1] == 1:
          br = False
    if nn[-1] == 1:
      cnt += 1
    if br and cnt == int(len(nn)/2):
      break
  return nn
n = int(input())
a = input()
a = a.split()
a = list(map(int, a))
nn = [0]*n
nn = f(nn)
ans = -100000000000
time = int(factorial(n) / factorial(int(n/2)) / factorial(n - int(n/2)))
for i in range(time):
  num = 0
  for j in range(len(nn)):
    if nn[j] == 1:
      num += a[j]
  ans = max(ans, num)
  nn = f(nn)
print(ans)

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)[::-1]

for idx in idx_arr:
    if idx + 1 in selected or idx - 1 in selected:
        continue
    ans += arr[idx]
    counta += 1
    selected.append(idx)
    if counta >= half:
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
k = int(2 * pow(10,5))
if 2 <= n <= k:
    A = list(map(int, input().split()))
    S = 0
    B = []
    c = 0
    for _ in range(n):
        a = max(A)
        if c != n//2:
            if A.index(a)+1 not in B and A.index(a)-1 not in B:
                S += a
                B.append(A.index(a))
                A[A.index(a)] = -1000000000
                c += 1
            else:
                A[A.index(a)] = -1000000000
        else:
            break
    print(S)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    A = read_list()
    dp = [[[-10 ** 20 for _ in range(2)] for _ in range(N // 2 + 5)] for _ in range(N + 1)]

    dp[1][0][0] = 0
    dp[1][1][1] = A[0]
    for i in range(1, N):
        for k in range(max(0, i // 2 - 2), i // 2 + 2):
            dp[i + 1][k][0] = max(dp[i][k][1], dp[i][k][0])
            dp[i + 1][k + 1][1] = dp[i][k][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 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

@lru_cache(None)
def F(index, n):
    if index >= 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:
import itertools

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

set_list = list(itertools.combinations(range(N), N // 2))
for num_set in set_list[:]:
    for i in range(len(num_set) - 1):
        if num_set[i] + 1 == num_set[i + 1]:
            set_list.remove(num_set)
            break
total_list=[]
for num_set in set_list:
    total = 0
    for i in num_set:
        total+=A[i]
    total_list.append(total)
print(max(total_list))

Submission status: Time Limit Exceeded

Solution code:
import itertools


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

    p = itertools.combinations(list(range(N)), 2)

    if N % 2 == 0:
        ans = 0
        for i in range(N):
            A_new = A[:i] + A[i+1:]
            if ans < sum(A_new[0::2]):
                ans = sum(A_new[0::2])
        print(ans)

    else:
        ans = 0
        for a in range(N):
            for b in range(a+1, N):
                A_new = A[:a] + A[a+1:b] + A[b+1:]
                if ans < sum(A_new[0::2]):
                    ans = sum(A_new[0::2])
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import itertools

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    #
    n=int(readline())
    aa=list(map(int, readline().rstrip().split()))
    #ss=readline().rstrip()
    #yn(1)
    c=n//2
    ans=0
    for cmb in itertools.combinations(list(range(n-c+1)),c):
        rui=0
        sm=0
        for i in range(len(cmb)):
            sm+=aa[cmb[i]+rui]
            rui+=1
        ans=max(ans,sm)
    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Time Limit Exceeded

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

answer = [max(A[0],A[1])]

for i in range(2,N):
  if i==2:
    answer.append(max(A[0],A[1],A[2]))
  elif i%2==0:
    answer.append(max(answer[-1], answer[-2]+A[i]))
  else:
    answer.append(max(answer[-2]+A[i], sum(A[:i-1:2])))

print(answer[-1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
k = int(2 * pow(10,5))
if 2 <= n <= k:
    A = list(map(int, input().split()))
    S = max(A)
    B = []
    B.append(A.index(S))
    A[A.index(S)] = -1000000000
    c = 1
    for _ in range(n):
        a = max(A)
        if c != n//2:
            if A.index(a)+1 not in B and A.index(a)-1 not in B:
                S += a
                B.append(A.index(a))
                A[A.index(a)] = -1000000000
                c += 1
            else:
                A[A.index(a)] = -1000000000
    print(S)

Submission status: Time Limit Exceeded

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

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

mx = 0
def dfs(i,c,s,p,q):
  global mx
  #print(i,c,s)
  if c == n//2:
    mx = max(s,mx)
    return
  if i > n-1:
    return
  dfs(i+2,c+1,s+a[i],p,q)
  if p < 2:
    dfs(i+3,c+1,s+a[i],p+1,q)
  if q < 1:
    dfs(i+4,c+1,s+a[i],p,q+1)
  
dfs(0,0,0,0,0)
dfs(1,0,0,1,1)
dfs(2,0,0,2,1)

print(mx)

Submission status: Time Limit Exceeded

Solution code:
import itertools


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


p = itertools.combinations(list(range(N)), 2)

if N % 2 == 0:
    ans = 0
    for i in range(N):
        A_new = A[:i] + A[i+1:]
        if ans < sum(A_new[0::2]):
            ans = sum(A_new[0::2])
    print(ans)

else:
    ans = 0
    for a in range(N):
        for b in range(a+1, N):
            A_new = A[:a] + A[a+1:b] + A[b+1:]
            if ans < sum(A_new[0::2]):
                ans = sum(A_new[0::2])
    print(ans)

Submission status: Time Limit Exceeded

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

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

mx = 0
def dfs(i,c,s,p,q):
  global mx
  #print(i,c,s)
  if c == n//2:
    mx = max(s,mx)
    return
  if i > n-1:
    return
  dfs(i+2,c+1,s+a[i],p,q)
  if p < 2:
    dfs(i+3,c+1,s+a[i],p+1,q)
  if q < 1:
    dfs(i+4,c+1,s+a[i],p,q+1)
  
dfs(0,0,0,0,0)
dfs(1,0,0,0,0)
dfs(2,0,0,0,0)

print(mx)

Submission status: Time Limit Exceeded

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import itertools

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    #n,m,k=map(int, readline().rstrip().split())
    #
    n=int(readline())
    aa=list(map(int, readline().rstrip().split()))
    #ss=readline().rstrip()
    #yn(1)
    c=n//2
    ans=0
    for cmb in itertools.combinations(list(range(n-c+1)),c):
        rui=0
        sm=0
        for i in range(len(cmb)):
            sm+=aa[cmb[i]+rui]
            rui+=1
        ans=max(ans,sm)
    print(ans)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Time Limit Exceeded

Solution code:
import itertools


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


p = itertools.combinations(list(range(N)), 2)

if N % 2 == 0:
    ans = 0
    for i in range(N):
        A_new = A[:i] + A[i+1:]
        if ans < sum(A_new[0::2]):
            ans = sum(A_new[0::2])
    print(ans)

else:
    ans = 0
    for v in p:
        a, b = min(v), max(v)
        A_new = A[:a] + A[a+1:b] + A[b+1:]
        if ans < sum(A_new[0::2]):
            ans = sum(A_new[0::2])
    print(ans)

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:
N= int(input())
A = list(map(int, input().split()))

if N%2==0:
    S=0
    for i in range(0,N):
        T=0
        a = A.pop(i)
        for j in range(0,N//2):
                T=T+A[2*j]
        if S<T:
            S=T
        A.insert(i,a)
else:
    S=0
    for i in range(0,N):
        p=i
        for j in range(p+1,N):
            T=0
            aj=A.pop(j)
            ai=A.pop(i)
            for k in range(0,N//2):
                    T=T+A[2*k]
            if S<T:
                S=T
            A.insert(i,ai)
            A.insert(j,aj)

print(S)

Submission status: Time Limit Exceeded

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))

def main():
    n = II()
    aa = MII()
    index = [i for i in range(n)]
    aa = list(zip(index, aa))
    aa.sort(key=lambda x: x[1], reverse=True)
    # print(aa)
    sumv = 0
    cnt = 0
    neibs = [-100]
    u = n//2
    i = 0
    while cnt < u:
        idx = aa[i][0]
        # print(neibs)
        if idx+1 in neibs or idx-1 in neibs:
            # print('skip');
            i+=1; continue
        sumv += aa[i][1]
        neibs.append(idx)
        cnt += 1
        i += 1
        # print('SUMV:{}'.format(sumv))
    print(sumv)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from math import floor
N=int(input())
As = [int(x) for x in input().split()]
ch = floor(N/2)
Pat=[x for x in combinations(range(N),ch) if all(x[i+1]-x[i]!=1 for i in range(ch-1))]
Pat2=[sum(As[y] for y in x) for x in Pat]
print(max(Pat2))

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


def func(A, X):
    if len(A) < 2 * X - 1:
        return -1000000000000000000

    if X == 0:
        return 0
    if not A:
        return -1000000000000000000

    return max(A[0] + func(A[2:], X - 1), func(A[1:], X))


def main():
    N = int(input())
    A = list(map(int, input().split()))
    X = N // 2
    print(func(A, X))


if __name__ == "__main__":
    main()

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')
sortet_arr = np.sort(arr)[::-1]
idx_arr = np.argsort(arr)[::-1]
ans = 0
counta = 0
half = num // 2
selected = []
for item, idx in zip(sortet_arr, idx_arr):
    if idx + 1 in selected or idx - 1 in selected:
        continue
    ans += item
    tmp = idx
    counta += 1
    selected.append(idx)
    if counta >= half:
        break
print(ans)

Submission status: Time Limit Exceeded

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

if N%2==0:
    S=0
    for i in range(0,N):
        T=0
        a = A.pop(i)
        for j in range(0,N//2):
                T=T+A[2*j]
        if S<T:
            S=T
        A.insert(i,a)
else:
    S=0
    for i in range(0,N):
        p=i
        for j in range(p+1,N):
            T=0
            aj=A.pop(j)
            ai=A.pop(i)
            for k in range(0,N-2):
                if k%2==0:
                    T=T+A[k]
            if S<T:
                S=T
            A.insert(i,ai)
            A.insert(j,aj)

print(S)

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):
    ret = -float('inf')
    if j==0:
        return 0
    if (N-i+1)//2 < j:
        return ret
    else:
        if i <= N-1:
            ret = max(ret,A[i]+calc(i+2,j-1))
        if i+1 <= N-1:
            ret = max(ret,A[i+1]+calc(i+3,j-1))
        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 = list(map(int,input().split()))

mx = 0
def dfs(i,c,s):
  global mx
  #print(i,c,s)
  if c == n//2:
    mx = max(s,mx)
    return
  if i > n-1:
    return
  dfs(i+2,c+1,s+a[i])
  dfs(i+3,c+1,s+a[i])
  dfs(i+4,c+1,s+a[i])
  
dfs(0,0,0)
dfs(1,0,0)
dfs(2,0,0)

print(mx)

Submission status: Time Limit Exceeded

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

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

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


def solve(i, m):
    if m == 1 and i <= n:
        return a[i-1]

    if i + 2 * (m-1) > n:
        return invalid

    if dp[i][m] != invalid:
        return dp[i][m]

    v = max(solve(i+2, m-1), solve(i+3, m-1), solve(i+4, m-1)) + a[i-1]
    dp[i][m] = v

    return v


print(max(solve(1, t), solve(2, t), solve(3, t)))

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):
    ret = -float('inf')
    if j==0:
        return 0
    if (N-i+1)//2 < j:
        return ret
    else:
        if i <= N-1:
            ret = max(ret,A[i]+calc(i+2,j-1))
        if i+1 <= N-1:
            ret = max(ret,A[i+1]+calc(i+3,j-1))
        return max(ret,calc(i+2,j))


N = I()
A = LI()

s = sum(A)
cums = [A[0]]
for i in range(1,N):
    cums.append(cums[-1]+A[i])

if N%2 == 0:
    print(calc(0,N//2))
else:
    print(calc(0,N//2))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
from collections import deque
q=deque([(-1,0,-2,0)])
ans=-10**18
for i,a in enumerate(A):
    while q and q[0][0]<i:
        j,n,r,x=q.popleft()
        if r<-1:
            if n==N//2-1:
                ans=max(ans,x+a)
            else:
                q.append((i,n+1,-1,x+a))
        if (j+1)//2<=n:
            q.append((i,n,r-1,x))
print(ans)

Submission status: Time Limit Exceeded

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


M=N//2

if N%2==0:
    S=0
    for i in range(0,N):
        B = copy.deepcopy(A)
        T=0
        B.pop(i)
        for j in range(0,N-1):
            if j%2==0:
                T=T+B[j]
        if S<T:
            S=T
else:
    S=0
    for i in range(0,N):
        p=i
        for j in range(p+1,N):
            B = copy.deepcopy(A)
            T=0
            B.pop(j)
            B.pop(i)
            for k in range(0,N-2):
                if k%2==0:
                    T=T+B[k]
            if S<T:
                S=T

print(S)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
N = int(input())
A = list(map(int,input().split()))
s = [0]*N
for i in range(N):
    s[i] = s[i-2]+A[i]

def f(n):
    if n==0:
        return 0
    elif n ==1:
        return max(A[0],A[1])
    elif n==2:
        return max(A[0],A[1],A[2])
    elif n%2==1:
        return max(A[n]+f(n-2),s[n-1])
    else:
        return max(A[n]+f(n-2),A[n-1]+f(n-3),s[n-2])

ans = f(N-1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int, input().split()))
d=-100000000000000
if n%2==0:
    for i in range(n//2+1):
        e=0
        for k in range(0,i):
            e+=a[2*k]
        for l in range(i,n//2):
            e+=a[2*l+1]
        if e>d:
            d=e
if n%2==1:
    for i in range(n//2+1):
        e=0
        for k in range(0,i):
             e+=a[2*k]
        for j in range (i,n//2+1):
            f=0
            for l in range(i,j):
                f+=a[2*l+1]
            for m in range(j,n//2):
                f+=a[2*m+2]
            if e+f>d:
                d=e+f
print(d)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    indices=[*range(len(a))]
    sorted_indices=sorted(indices,key=lambda i: -a[i])
    sorted_num= [a[i] for i in sorted_indices]
    #print(sorted_indices)
    #print(sorted_num)
    residue=n//2
    dif=[]
    ans=0
    for i in range(n):
        if residue==0: break
        flg=False
        for j in range(len(dif)):
            if abs(sorted_indices[i]-dif[j])==1:
                flg=True
        if flg: continue
        
        dif.append(sorted_indices[i])
        ans+=sorted_num[i]
        residue-=1
    #print(dif)
    print(ans)
        
    
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]


def main():
	n=int(nextLine())
	aList=nextIntList()
	
	num=n//2
	score=[[None for _ in range(num)] for i in range(n)]
	
	for i in range(n):
		
		if i==0:
			score[i][0]=aList[i]
		else:
			score[i][0]=max(aList[i], score[i-1][0])
			
		for j in range(1, num):
			nextScore=[]
			if i>=1:
				s=score[i-1][j]
				if s is not None:
					nextScore.append(s)
			if i>=2:
				s=score[i-2][j-1]
				if s is not None:
					s+=aList[i]
					nextScore.append(s)
			if len(nextScore)>0:
				nextScore=max(nextScore)
				score[i][j]=nextScore
	
# 		print(i, *[str(s) for s in score[i]], sep="\t")
	
	print(score[-1][-1])
	
if __name__=="__main__":
	main()

Submission status: Memory Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

SUM=[0]*(N+1)
for i in range(N-1,-1,-1):
    SUM[i]=SUM[i+1]

    if (N-i)%2==1:
        SUM[i]+=A[i]

#print(SUM)
        
from functools import lru_cache
@lru_cache(maxsize=None)
def calc(i,select):
    rest=N-i

    if rest==0 or select==0:
        return 0

    if rest%2==1 and rest//2+1==select:
        return SUM[i]
    
    elif rest%2==0 and rest//2==select:
        return max(calc(i+1,select),A[i]+calc(i+2,select-1))

    elif rest%2==1 and rest//2==select:
        return max(calc(i+1,select),A[i]+calc(i+2,select-1))

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N = getN()
A = getList()

# N // 2個の整数をどの２箇所も連続しないように選ぶ
# 和の最大値を求めよ

# 通りの数は？　まあまあ多い
# 偶数の場合
# 始点がA[1]なら１通りに定まる
# 始点がA[0]なら?
# 次に3個先を取ると1通りに定まる
# 次に2個先を取り、その次に3個先を取ると1通りに定まる

# dp[i][j]: i回目までに3つ飛ばしをj回使った
# 長さが偶数なら1回まで使える
if N % 2 == 0:
    dp = [[-float('inf')] * 2 for i in range(N)]
    dp[0][0] = A[0]
    dp[1][0] = A[1]
    for i in range(2, N):
        for j in range(1, -1, -1):
            if j == 0:
                dp[i][j] = max(dp[i][j], dp[i - 2][j] + A[i])
            elif j == 1 and i - 3 >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 2][j] + A[i])
            if i - 3 >= 0 and j - 1 >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 3][j - 1] + A[i])
    # 0個飛ばしdp[-2]:奇数個目だけ 0個飛ばしdp[-1]:偶数個目だけ 1個飛ばしdp[-1]
    print(max(dp[-2][0], dp[-1][0], dp[-1][1]))
# 長さが奇数なら2回まで使える
else:
    dp = [[-float('inf')] * 3 for i in range(N)]
    dp[0][0] = A[0]
    dp[1][0] = A[1]
    for i in range(2, N):
        for j in range(2, -1, -1):
            if j == 0:
                dp[i][j] = max(dp[i][j], dp[i - 2][j] + A[i])
            elif j >= 1 and i - 3 >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 2][j] + A[i])
            if i - 3 >= 0 and j - 1 >= 0:
                dp[i][j] = max(dp[i][j], dp[i - 3][j - 1] + A[i])
    opt_1 = [A[i] for i in range(N) if i % 2 == 0]
    opt_2 = [A[i] for i in range(N) if i % 2 == 1]
    # 2個飛ばしならdp[-1]のが該当
    # 1個飛ばしならdp[-1], dp[-2]のが該当
    # 0個飛ばしは奇数個目だけ - その中の最小値、偶数個目だけ
    print(max(dp[-1][2], dp[-1][1], dp[-2][1], sum(opt_1) - min(opt_1), sum(opt_2)))

Submission status: Accepted

Solution code:
from itertools import accumulate
n = int(input())
A = list(map(int, input().split()))
L = [0]
R = []
min_L = float("inf")
for i, a in enumerate(A):
  b = A[-(i+1)]
  if i%2 == 0:
    L.append(a)
  else:
    R.append(a)
R.append(0)
L = list(accumulate(L))
R = list(accumulate(R[::-1]))[::-1]
ans = -float("inf")
if n%2:
  def f(A):
    temp = 0
    left = 0
    right = 0
    for i in range(2, n, 2):
      temp += A[i]
    res = max(ans, temp)
    for i in range(1, n//2):
      temp -= A[i*2]
      left, right = left+A[2*(i-1)], max(left, right)+A[2*(i-1)+1]
      res = max(res, temp+max(left, right))
    return res
  ans = max(f(A), f(A[::-1]))
  temp = 0
  for i in range(1, n, 2):
    temp += A[i]
  ans = max(ans, temp)
else:
  for l, r in zip(L, R):
    ans = max(ans, l+r)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split())) + [0]

dp0, dp1, dp2 = [0] * (N + 1), [0] * (N + 1), [0] * (N + 1)
dp0[0] = A[0]
dp1[1] = A[1]
dp2[2] = A[2]

for i in range(N - 3):
    dp0[i + 2] = 0 if i % 2 else dp0[i] + A[i + 2]
    dp1[i + 3] = max(dp0[i], dp1[i + 1]) + A[i + 3]
    dp2[i + 4] = max(dp0[i], dp1[i + 1], dp2[i + 2]) + A[i + 4]

if N % 2:
    print(max(dp0[N - 3], dp1[N - 2], dp2[N - 1]))
else:
    print(max(dp0[N - 2], dp1[N - 1]))

Submission status: Accepted

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

Submission status: Accepted

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(max(1, i//2-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: Accepted

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

inf = float('inf')

# 累積和
if n % 2 == 0:
    l_even = [0]
    l_odd = [0]
    for i in range(n):
        if i % 2 == 0:
            l_even.append(l_even[-1] + a[i])
        else:
            l_odd.append(l_odd[-1] + a[i])
    ans = -inf
    for i in range(n // 2 + 1):
        if ans < l_even[i] + l_odd[-1] - l_odd[i]:
            ans = l_even[i] + l_odd[-1] - l_odd[i]
    print(ans)
    exit()

# dp[i] = i回ずらしを使った時の最大値
# 1個ずつdpを更新
# i = 0, 1, 2
dp = [a[0], a[1], a[2]]
for i in range(2, n-2, 2):
    dp[2] = max([dp[2] + a[i+2], dp[1] + a[i+2]])
    dp[1] = max([dp[1] + a[i+1], dp[0] + a[i+1]])
    dp[0] += a[i]

print(max(dp))

Submission status: Accepted

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

# i個使う時の要素の和の最大値
dp = [0]*(n+1)
dp[1] = 0
dp[2] = max(a[0],a[1])

# 奇数の番号の累積和
b = [0]*(n+1)
b[1] = a[0]
for i in range(1,n-1,2):
    b[i+2] = b[i] + a[i+1]
# print(b)

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

# print(dp)
print(dp[n])

Submission status: Accepted

Solution code:
import sys
import numpy as np
def input(): return sys.stdin.readline().rstrip()

def odd(A):
    oddi=np.array(A[::2],dtype=np.int64)
    eveni=np.array(A[1::2],dtype=np.int64)
    left=np.cumsum(oddi[:-1]-eveni)
    left=np.insert(left,0,0)
    right=np.cumsum(oddi[:0:-1]-eveni[::-1])[::-1]
    right=np.append(right,0)
    tmp=np.max(np.maximum.accumulate(left)+right)
    return tmp+np.sum(eveni)

def even(A):
    left=np.array([0]+A[::2],dtype=np.int64)
    right=np.array(A[1::2]+[0],dtype=np.int64)[::-1]
    return np.max(left.cumsum()+right.cumsum()[::-1])

def main():
    n=int(input())
    A=list(map(int, input().split()))
    if n%2==1:
        print(odd(A))
    else:
        print(even(A))


if __name__ == '__main__':
    main()