Problem:


Score : 400 points

Problem Statement

Your friend gave you a dequeue D as a birthday present.

D is a horizontal cylinder that contains a row of N jewels.

The values of the jewels are V_1, V_2, ..., V_N from left to right. There may be jewels with negative values.

In the beginning, you have no jewel in your hands.

You can perform at most K operations on D, chosen from the following, at most K times (possibly zero):

Operation A: Take out the leftmost jewel contained in D and have it in your hand. You cannot do this operation when D is empty.

Operation B: Take out the rightmost jewel contained in D and have it in your hand. You cannot do this operation when D is empty.

Operation C: Choose a jewel in your hands and insert it to the left end of D. You cannot do this operation when you have no jewel in your hand.

Operation D: Choose a jewel in your hands and insert it to the right end of D. You cannot do this operation when you have no jewel in your hand.

Find the maximum possible sum of the values of jewels in your hands after the operations.

Constraints

All values in input are integers.

1 \leq N \leq 50

1 \leq K \leq 100

-10^7 \leq V_i \leq 10^7

Input

Input is given from Standard Input in the following format:

N K
V_1 V_2 ... V_N

Output

Print the maximum possible sum of the values of jewels in your hands after the operations.

Sample Input 1

6 4
-10 8 2 1 2 6

Sample Output 1

14

After the following sequence of operations, you have two jewels of values 8 and 6 in your hands for a total of 14, which is the maximum result.

Do operation A. You take out the jewel of value -10 from the left end of D.

Do operation B. You take out the jewel of value 6 from the right end of D.

Do operation A. You take out the jewel of value 8 from the left end of D.

Do operation D. You insert the jewel of value -10 to the right end of D.

Sample Input 2

6 4
-6 -100 50 -2 -5 -3

Sample Output 2

44

Sample Input 3

6 3
-6 -100 50 -2 -5 -3

Sample Output 3

0

It is optimal to do no operation.



Sample input:
6 4
-10 8 2 1 2 6


Sample output:
14

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for l in range(n):
	for r in range(l, n):
		o = v[:l] + v[r + 1:]
		if len(o) > k:
			continue
		o.sort()
		i = 0
		while i < len(o) and i < k - len(o) and o[i] < 0:
			i += 1
		ans = max(ans, sum(o[i:]))
		# print("%d %d: %s, %d, %d" % (l, r, str(o), i, ans))
print(ans)

Submission status: Wrong Answer

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

ans = 0

for i in range(0,min(n,k)+1): # 取り出す回数
    g = i - (k-i) #得る宝石数
    for j in range(i+1): #左から取り出す回数
        A = []
        r = i-j
        for L in range(j):
            A.append(V[L])
        for R in range(r):
            A.append(V[-(R+1)])
        A=sorted(A,reverse=1)
        pt = sum(A[:g])
        #print(A)
        #print(pt)
        ans = max(ans,pt)
print(ans)

Submission status: Wrong Answer

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

ans = 0
for L in range(min(N, K)):
    for R in range(min(N - L, K - L)):
        js = V[:L] + V[-R:] if R >= 1 else V[:L]
        t = K - L - R
        s = 0
        for j in sorted(js):
            if j < 0 and t > 0:
                s += -j
                t -= 1
        ans = max(ans, sum(js) + s)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k= list(map(int, input().split()))
v =  list(map(int, input().split()))

v = np.array(v)

cand = v[:k]

def calc(cand):
#     print(cand)
    if len(cand) <= 1:
        return np.sum(cand)
    cand = list(cand)
    for i in range(len(cand)):
        if np.min(cand) >= 0:
            break
        if np.argmin(cand) != len(cand):
            if -np.min(cand)  > cand[-1]:
                cand.pop(np.argmin(cand))
                cand = cand[:-1]
        if len(cand) == 0:
            break
            
    if len(cand) > 0:
        while True:
            
            if cand[-1] < 0:
                cand = cand[:-1]
            else:
                break
            if len(cand) ==0:
                break
    score = np.sum(cand)
#     print(cand)
    return int(score)

a = np.arange(k + 1)
max_score = 0
for aa in a:
    score = calc(v[:aa]) + calc(v[::-1][:k-aa])
#     print(score)
    if max_score < score:
        max_score = score
print(max_score)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
#input = sys.stdin.readline

n,k = map(int,input().split())
v = list(map(int,input().split()))
ans = 0
for i in range(k):
        for j in range(k-i):
                x = v[:i]
                if n< i+j:
                        continue
                if j > 0:
                        x = x + v[-j:]
                x.sort(key=lambda x : -x)
                kai = i+ j
                while kai < k and x and x[-1] < 0:
                        x.pop()
                        kai+=1
                ans = max(ans,sum(x))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import sys
from functools import lru_cache
input = lambda: sys.stdin.readline().strip()
n, k = [int(x) for x in input().split()]
v = [int(x) for x in input().split()]

@lru_cache
def opt(i, j, k):
    if i <= j:
        return max(
            v[i] + opt(i + 1, j, k - 1) if k >= 1 else 0,
            v[j] + opt(i, j - 1, k - 1) if k >= 1 else 0,
            opt(i + 1, j, k - 2) if k >= 2 else 0,
            opt(i, j - 1, k - 2) if k >= 2 else 0
        )
    else:
        return 0

print(max(opt(0, n - 1, kk) for kk in range(k + 1)))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,k = inpl()
a = inpl()
res = 0
for ope in range(k+1):
    for pick in range(ope+1):
        if pick > n: continue
        for back in range(ope - pick + 1):
            for lp in range(pick+1):
                rp = pick - lp
                # print(ope,back,lp,rp)
                q = []
                for i in range(lp):
                    q.append(a[i])
                for i in range(rp):
                    q.append(a[-i-1])
                q.sort()
                q = deque(q)
                for i in range(back):
                    if not q: break
                    q.popleft()
                res = max(res, sum(q))
print(res)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import deque
from functools import lru_cache

N,K = map(int,input().split())
lim = min(N,K)
V = list(map(int,input().split()))
D = V.copy()
have = []
heapq.heapify(have)

#@lru_cache(maxsize = None)
def recur(d,h,n):
  if n == lim:
    #print(h)
    return sum(h)
  else:
    a = d[0]
    b = d[-1]
    ha = h.copy()
    hb = h.copy()
    heapq.heappush(ha,a)
    heapq.heappush(hb,b)
    reta = recur(d[1:],ha,n + 1)
    retb = recur(d[:-1],hb,n + 1)
    if len(h) == 0:
      return max(reta,retb)
    else:
      heapq.heappop(h)
      retc = recur(d,h,n + 1)
      return max(reta,retb,retc)
    
print(max(recur(D,have,0),0))

Submission status: Time Limit Exceeded

Solution code:
import copy

N, K = map(int, input().split())
V = [int(i) for i in input().split()]

value = 0
# k+1個取って，ret-1個戻す
num = min(N*2,K)
for k in reversed(range(num)):
    for ret in range(num-k): #戻す個数はret個
        if (ret < k+1):
            #print('{}個取って{}戻す'.format(k+1,ret))
            for i in range(k+1+1): # 左右の分け方
                tmp = []
                V_tmp = copy.copy(V)
                #print('元々：',V_tmp)
                tmp.extend(V_tmp[:i]) # 左端
                #print('左端：',V_tmp[:i])
                V_tmp = V_tmp[i:]
                #print('左端取った：',V_tmp)
                if (k+1-i) > 0:
                    tmp.extend(V_tmp[-(k+1-i):]) #右端
                    #print('右端：',V_tmp[-(k+1-i):])
                # V_tmp = V_tmp[:-(k+1-i)]
                # print('右端取った：',V_tmp)
                if V_tmp == []:
                    break
                # ret個戻す
                tmp = list(filter(lambda x: x not in sorted(tmp)[:ret],tmp))
                #print('手元の宝石：',tmp)
                value = max(value,sum(tmp))
            #print()

print(value)

Submission status: Time Limit Exceeded

Solution code:
import copy

N, K = map(int, input().split())
V = [int(i) for i in input().split()]

value = 0
# k+1個取って，ret-1個戻す
for k in reversed(range(K)):
    for ret in range(K-k): #戻す個数はret個
        if (ret < k+1):
            #print('{}個取って{}戻す'.format(k+1,ret))
            for i in range(k+1+1): # 左右の分け方
                tmp = []
                V_tmp = copy.copy(V)
                #print('元々：',V_tmp)
                tmp.extend(V_tmp[:i]) # 左端
                #print('左端：',V_tmp[:i])
                V_tmp = V_tmp[i:]
                #print('左端取った：',V_tmp)
                if (k+1-i) > 0:
                    tmp.extend(V_tmp[-(k+1-i):]) #右端
                    #print('右端：',V_tmp[-(k+1-i):])
                # V_tmp = V_tmp[:-(k+1-i)]
                # print('右端取った：',V_tmp)
                if V_tmp == []:
                    break
                tmp = list(filter(lambda x: x not in sorted(tmp)[:ret],tmp))
                #print('手元の宝石：',tmp)
                value = max(value,sum(tmp))
            #print()

print(value)

Submission status: Time Limit Exceeded

Solution code:
import copy

N, K = map(int, input().split())
V = [int(i) for i in input().split()]

value = 0
# k+1個取って，ret-1個戻す
for k in reversed(range(K)):
    for ret in range(K-k): #戻す個数はret個
        if (ret < k+1) and ((k+1+ret)<=K):
            for i in range(k+1+1): # 左右の分け方
                tmp = []
                V_tmp = copy.copy(V)
                for sp in range(i): # 左端iつ取る
                    if V_tmp == []:
                        break
                    tmp.append(V_tmp.pop(0))
                for sp in range(k+1-i): # 右端k+1-iつ取る
                    if V_tmp == []:
                        break
                    tmp.append(V_tmp.pop(-1))
                tmp = list(filter(lambda x: x not in sorted(tmp)[:ret],tmp))
                value = max(value,sum(tmp))

print(value)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import heapq
    from copy import deepcopy
    from collections import deque
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    _N, K = [int(x) for x in input().strip().split()]
    V = deque([int(x) for x in input().strip().split()])
    max_ans = sum([v for v in V if v > 0])

    def dfs(ans, q, V, k):
        # print(k, q, V)
        ans = max(ans, sum(q))
        if ans == max_ans:
            print(ans)
            exit()
        if k == K:
            return ans
        if q:
            t = heapq.heappop(q)
            if t < 0:
                V.appendleft(t)
                ans = max(ans, dfs(ans, q[:], V, k+1))
                V.popleft()
                V.append(t)
                ans = max(ans, dfs(ans, q, V, k+1))
                V.pop()
            heapq.heappush(q, t)
        if V:
            q_l = q[:]
            q_r = q[:]
            t = V.popleft()
            heapq.heappush(q_l, t)
            ans = max(ans, dfs(ans, q_l[:], V, k+1))
            V.appendleft(t)
            t = V.pop()
            heapq.heappush(q_r, t)
            ans = max(ans, dfs(ans, q_r[:], V, k+1))
            V.append(t)
            
        return ans
    print(dfs(-float('inf'), [], V, 0))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import heapq
    from copy import deepcopy
    from collections import deque
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    _N, K = [int(x) for x in input().strip().split()]
    V = deque([int(x) for x in input().strip().split()])
    max_ans = sum([v for v in V if v > 0])

    def dfs(ans, q, V, k):
        # print(k, q, V)
        ans = max(ans, sum(q))
        if ans == max_ans:
            print(ans)
            exit()
        if k == K:
            return ans
        if q:
            t = heapq.heappop(q)
            V.appendleft(t)
            ans = max(ans, dfs(ans, q[:], V, k+1))
            V.popleft()
            V.append(t)
            ans = max(ans, dfs(ans, q, V, k+1))
            V.pop()
            heapq.heappush(q, t)
        if V:
            q_l = q[:]
            q_r = q[:]
            t = V.popleft()
            heapq.heappush(q_l, t)
            ans = max(ans, dfs(ans, q_l[:], V, k+1))
            V.appendleft(t)
            t = V.pop()
            heapq.heappush(q_r, t)
            ans = max(ans, dfs(ans, q_r[:], V, k+1))
            V.append(t)
            
        return ans
    print(dfs(-float('inf'), [], V, 0))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import heapq
    from copy import deepcopy
    from collections import deque
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    _N, K = [int(x) for x in input().strip().split()]
    V = deque([int(x) for x in input().strip().split()])

    def dfs(ans, q, V, k):
        # print(k, q, V)
        ans = max(ans, sum(q))
        if k == K:
            return ans
        if q:
            t = heapq.heappop(q)
            V.appendleft(t)
            ans = max(ans, dfs(ans, q[:], V, k+1))
            V.popleft()
            V.append(t)
            ans = max(ans, dfs(ans, q, V, k+1))
            V.pop()
            heapq.heappush(q, t)
        if V:
            q_l = q[:]
            q_r = q[:]
            t = V.popleft()
            heapq.heappush(q_l, t)
            ans = max(ans, dfs(ans, q_l[:], V, k+1))
            V.appendleft(t)
            t = V.pop()
            heapq.heappush(q_r, t)
            ans = max(ans, dfs(ans, q_r[:], V, k+1))
            V.append(t)
            
        return ans
    print(dfs(-float('inf'), [], V, 0))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import heapq
import copy
n, k = map(int, input().split())

v = deque(list(map(int, input().split())))
j = []
heapq.heapify(j)

def solve(hep, jue, c, end=k):
    if c==k:
        return sum(hep)
    result = [0]
    if len(jue)!=0:
        x, y = copy.deepcopy(hep), copy.deepcopy(jue)
        heapq.heappush(x, y.pop())
        result.append(solve(x, y, c+1))
        x, y = copy.deepcopy(hep), copy.deepcopy(jue)
        heapq.heappush(x, y.popleft())
        result.append(solve(x, y, c+1))

    if len(hep)!=0:
        x, y = copy.deepcopy(hep), copy.deepcopy(jue)
        y.append(heapq.heappop(x))
        result.append(solve(x, y, c+1))
        x, y = copy.deepcopy(hep), copy.deepcopy(jue)
        y.appendleft(heapq.heappop(x))
        result.append(solve(x, y, c+1))

    return max(result)


print(solve(j, v, 0))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
from collections import deque
from functools import partial, lru_cache
from heapq import heappush, heappop

inputs = open(0).readlines()
n, k = map(int, inputs[0].split())
V = deque(map(int, inputs[1].split()))
W = []

def dfs(root, option, function):
    stack =[root]
    ans = 0
    while stack:
        current_node = stack.pop()
        ans = function(current_node, ans)
        for n in option(current_node):
            stack.append(n)
    return ans

def option(node, limit):
    i, j = node
    if i+j < limit:
        return ((i+1, j), (i, j+1))
    return tuple()

def function(node, ans, W, V, limit, memo):
    if node in memo:
        return max(ans, memo[node])
    i, j = node
    W_, V_ = map(deepcopy, (W, V))
    for _ in range(i):
        if V_:
            heappush(W_, V_.pop())
    for _ in range(j):
        if V_:
            heappush(W_, V_.popleft())
    score = sum(W_)
    for _ in range(min(limit-i-j, i+j)):
        if W_ and W_[0] < 0:
            score -= heappop(W_)
    memo[node] = score
    return max(ans, memo[node])

ans = dfs((0, 0), partial(option, limit=min(n, k)), partial(function, W=W, V=V, limit=k, memo={}))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
from collections import deque
from functools import partial, lru_cache
from heapq import heappush, heappop

inputs = open(0).readlines()
n, k = map(int, inputs[0].split())
V = deque(map(int, inputs[1].split()))
W = []

def dfs(root, option, function):
    nodes, stack = [], [root]
    ans = 0
    while stack:
        current_node = stack.pop()
        if current_node in nodes:
            continue
        ans = function(current_node, ans)
        for n in option(current_node):
            if n not in nodes:
                stack.append(n)
    return ans

def option(node, limit):
    i, j = node
    if i+j < limit:
        return ((i+1, j), (i, j+1))
    return tuple()

def function(node, ans, W, V, limit, memo):
    if node in memo:
        return max(ans, memo[node])
    i, j = node
    W_, V_ = map(deepcopy, (W, V))
    for _ in range(i):
        if V_:
            heappush(W_, V_.pop())
    for _ in range(j):
        if V_:
            heappush(W_, V_.popleft())
    score = sum(W_)
    for _ in range(min(limit-i-j, i+j)):
        if W_ and W_[0] < 0:
            score -= heappop(W_)
    memo[node] = score
    return max(ans, memo[node])

ans = dfs((0, 0), partial(option, limit=min(n, k)), partial(function, W=W, V=V, limit=k, memo={}))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
from collections import deque
from functools import partial, lru_cache
from heapq import heappush, heappop

inputs = open(0).readlines()
n, k = map(int, inputs[0].split())
V = deque(map(int, inputs[1].split()))
W = []

def dfs(root, option, function):
    nodes, stack = [], [root]
    ans = 0
    while stack:
        current_node = stack.pop()
        if current_node in nodes:
            continue
        ans = function(current_node, ans)
        for n in option(current_node):
            if n not in nodes:
                stack.append(n)
    return ans

def option(node, k):
    i, j = node
    if i+j < k:
        return ((i+1, j), (i, j+1))
    return tuple()

def function(node, ans, W, V, k, memo):
    if node in memo:
        return max(ans, memo[node])
    i, j = node
    W_, V_ = map(deepcopy, (W, V))
    for _ in range(i):
        if V_:
            heappush(W_, V_.pop())
    for _ in range(j):
        if V_:
            heappush(W_, V_.popleft())
    score = sum(W_)
    for _ in range(min(k-i-j, i+j)):
        if W_ and W_[0] < 0:
            score -= heappop(W_)
    memo[node] = score
    return max(ans, memo[node])

ans = dfs((0, 0), partial(option, k=k), partial(function, W=W, V=V, k=k, memo={}))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
from collections import deque
from functools import partial
from heapq import heappush, heappop

inputs = open(0).readlines()
n, k = map(int, inputs[0].split())
V = deque(map(int, inputs[1].split()))
W = []

def dfs(root, option, function):
    nodes, stack = [], [root]
    ans = 0
    while stack:
        current_node = stack.pop()
        if current_node in nodes:
            continue
        ans = function(current_node, ans)
        for n in option(current_node):
            if n not in nodes:
                stack.append(n)
    return ans

def option(node, k):
    i, j, k_ = node
    if i+j+k_ < k:
        return [(i+1, j, k_), (i, j+1, k_), (i, j, k_+1)]
    return []

def function(node, ans, W, V):
    i, j, k = node
    W_, V_ = map(deepcopy, (W, V))
    for _ in range(i):
        if V_:
            heappush(W_, V_.pop())
    for _ in range(j):
        if V_:
            heappush(W_, V_.popleft())
    for _ in range(k):
        if W_:
            _ = heappop(W_)
    return max(ans, sum(W_))

ans = dfs((0, 0, 0), partial(option, k=k), partial(function, W=W, V=V))
print(ans)

Submission status: Time Limit Exceeded

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


N, K = map(int, input().split())
V = deque(list(map(int, input().split())))


def solve(v, k):
  if len(v) == 0 or k <= 0:
    return v, 0
  else:
    v0 = v.popleft()
    v, _a1 = solve(v, k-1)
    _a1 += v0
    v, _a2 = solve(v, k-2)
    v.appendleft(v0)
    v1 = v.pop()
    v, _a3 = solve(v, k-1)
    _a3 += v1
    v, _a4 = solve(v, k-2)
    v.append(v1)
    return v, max(_a1, _a2, _a3, _a4)

print(solve(V, K)[1])

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split(' ')))
vvv = list(map(int, input().split(' ')))
# 4^100 = 1.6e60 TLE

def f(current, d, l):
    if current == k:
        return sum(l)
    ans = -1e9-1
    if d:
        ans = max(ans, f(current + 1, d[1:], l + [d[0]]))
        ans = max(ans, f(current + 1, d[:-1], l + [d[-1]]))
        # 即捨てる
        if d[0] < 0 and current + 2 <= k:
            ans = max(ans, f(current + 2, d[1:], l))
        if d[-1] < 0 and current + 2 <= k:
            ans = max(ans, f(current + 2, d[:-1], l))
    else:
        return sum(l)
    ans = max(ans, f(current + 1, d, l))

    return ans
print(f(0, vvv, []))

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split(' ')))
vvv = list(map(int, input().split(' ')))
# 4^100 = 1.6e60 TLE

memo = {}  # 意味ないかも
def f(current, d, l):
    key = (current, str(d), sum(l))
    if key not in memo:
        if current == k:
            return sum(l)
        if current > k:
            return -1e9-1
        ans = -1e9-1
        if d:
            ans = max(ans, f(current + 1, d[1:], l + [d[0]]))
            ans = max(ans, f(current + 1, d[:-1], l + [d[-1]]))
            # 即捨てる
            if d[0] < 0:
                ans = max(ans, f(current + 2, d[1:], l))
            if d[-1] < 0:
                ans = max(ans, f(current + 2, d[:-1], l))
        ans = max(ans, f(current + 1, d, l))

        memo[key] = ans
    return memo[key]
print(f(0, vvv, []))

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split(' ')))
vvv = list(map(int, input().split(' ')))
# 4^100 = 1.6e60 TLE

memo = {}  # 意味ないかも
def f(current, d, l):
    key = (current, str(d), str(l))
    if key not in memo:
        if current == k:
            return sum(l)
        if current > k:
            return -1e9-1
        ans = -1e9-1
        if d:
            ans = max(ans, f(current + 1, d[1:], l + [d[0]]))
            ans = max(ans, f(current + 1, d[:-1], l + [d[-1]]))
            # 即捨てる
            if d[0] < 0:
                ans = max(ans, f(current + 2, d[1:], l))
            if d[-1] < 0:
                ans = max(ans, f(current + 2, d[:-1], l))
        ans = max(ans, f(current + 1, d, l))

        memo[key] = ans
    return memo[key]
print(f(0, vvv, []))

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split(' ')))
vvv = list(map(int, input().split(' ')))
# 4^100 = 1.6e60 TLE

memo = {}  # 意味ないかも
def f(current, d, l):
    key = (current, str(d), str(l))
    if key not in memo:
        if current == k:
            return sum(l)
        if current > k:
            return -1e9-1
        ans = -1e9-1
        if d:
            ans = max(ans, f(current + 1, d[1:], l + [d[0]]))
            ans = max(ans, f(current + 1, d[:-1], l + [d[-1]]))
            # 即捨てる
            ans = max(ans, f(current + 2, d[1:], l))
            ans = max(ans, f(current + 2, d[:-1], l))
        ans = max(ans, f(current + 1, d, l))

        memo[key] = ans
    return memo[key]
print(f(0, vvv, []))

Submission status: Time Limit Exceeded

Solution code:
n, k = list(map(int, input().split(' ')))
vvv = list(map(int, input().split(' ')))
# TLE !!!

def f(current, d, l):
    if current == k:
        return sum(l)
    if current > k:
        return -1e9-1
    ans = -1e9-1
    if d:
        ans = max(ans, f(current + 1, d[1:], l + [d[0]]))
        ans = max(ans, f(current + 1, d[:-1], l + [d[-1]]))
        # 即捨てる
        ans = max(ans, f(current + 2, d[1:], l))
        ans = max(ans, f(current + 2, d[:-1], l))
    ans = max(ans, f(current + 1, d, l))
    return ans

print(f(0, vvv, []))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = []
for i in range(1,K+1):
    for j in range(2**i):
        gem = 0
        minus = []
        flag = True
        A = 0
        B = -1
        for k in range(i):
            if (j >> k) & 1 == 1:
                if A <= N-1:
                    if V[A] >= 0:
                        gem += V[A]
                    else:
                        minus.append(V[A])
                    A += 1
                else:
                    flag = False
                    break
            else:
                if B >= -N:
                    if V[B] >= 0:
                        gem += V[B]
                    else:
                        minus.append(V[B])
                    B -= 1
                else:
                    flag = False
                    break
        if flag:
            minus.sort(reverse = True)
            for l in range(K-i):
                if minus:
                    minus.pop()
            ans.append(gem + sum(minus))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = []
for i in range(1,K+1):
    for j in range(2**i):
        gem = []
        flag = True
        A = 0
        B = -1
        for k in range(i):
            if (j >> k) & 1 == 1:
                if A <= N-1:
                    gem.append(V[A])
                    A += 1
                else:
                    flag = False
                    break
            else:
                if B >= -N:
                    gem.append(V[B])
                    B -= 1
                else:
                    flag = False
                    break
        if flag:
            gem.sort(reverse = True)
            for l in range(K-i):
                if gem and gem[-1] < 0:
                    gem.pop()
            ans.append(sum(gem))
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import itertools
N,K = map(int,input().split())
V=[int(x) for x in input().split()]
max_value=0

for action in itertools.product(['a','b','c','d'],repeat=K):
  #print(action)
  V_a=V.copy()
  value=[]
  for i in range(K):
    if action[i]=='a':
      if V_a==[]:
        break
      else:
        value +=[V_a[0]]
        V_a.pop(0)
      #print(V_a,value)
    elif action[i]=='b':
      if V_a==[]:
        break
      else:
        value +=[V_a[-1]]
        V_a.pop(-1)
      #print(V_a,value)
    elif action[i]=='c':
      if value==[]:
        break
      else:
        value.sort()
        V_a +=[value[0]]
        value.pop(0)
      #print(V_a,value)
    elif action[i]=='c':
      if value==[]:
        break
      else:
        value.sort()
        V_a =[value[0]]+V_a
        value.pop(0)
      #print(V_a,value)
  max_value=max(max_value,sum(value))
  #print(value)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
V = list(map(int, input().split()))
from collections import deque
d=deque(V)
my_gem = []
max_value=-1000000000
def nxt(num,cur_v):
        global max_value
        global my_gem
        if num == K :
                return

        if len(d) > 0:

                # sousa A
                gem_v = d.popleft()
                cur_v+=gem_v
                if max_value < cur_v:
                        max_value = cur_v

                my_gem.append(gem_v)
                nxt(num+1,cur_v)

                my_gem.remove(gem_v)
                cur_v -= gem_v
                d.appendleft(gem_v)

                # sousa B
                gem_v = d.pop()
                cur_v+=gem_v
                if max_value < cur_v:
                        max_value = cur_v

                my_gem.append(gem_v)
                nxt(num+1,cur_v)
                my_gem.remove(gem_v)

                cur_v -= gem_v
                d.append(gem_v)

        # sousa C
        itr = 0
        for pushgem in my_gem:
                itr+=1
                my_gem.remove(pushgem)
                cur_v -= pushgem

                if max_value < cur_v:
                        max_value = cur_v

                d.appendleft(pushgem)
                nxt(num+1,cur_v)
                d.popleft()

                cur_v += pushgem
                my_gem.append(pushgem)
                if itr == len(my_gem):
                        break

        # sousa D
        itr = 0
        for pushgem in my_gem:
                my_gem.remove(pushgem)
                cur_v -= pushgem

                if max_value < cur_v:
                        max_value = cur_v

                d.append(pushgem)
                nxt(num+1,cur_v)
                d.pop()

                cur_v += pushgem
                my_gem.append(pushgem)
                if itr == len(my_gem):
                        break

nxt(0,0)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
V = [int(v) for v in input().split()]


def f(L, i, n):
    if i == 0 or len(L) == 0:
        return 0
    if L[n] >= 0:
        t = L[n]
        if n >= 0:
            n += 1
        else:
            n -= 1
        return t+f(L,i-1,n)
    else:
        t = L[n]
        if n >= 0:
            n += 1
        else:
            n -= 1
        if i >= 2:
            return max(f(L, i-2, n), t+f(L, i-1, n))
        else:
            return t+f(L, i-1, n)
    

t = min(K+1, N)
L1 = [0]*(t)
L2 = [0]*(t)
cnt1 = 0
cnt2 = 0
for j in range(t):
    if V[j] <= 0:
        cnt1 += 1
    if cnt1 <= j:
        L1[j] = f(V, j, 0)
    if V[t-j-1] <= 0:
        cnt2 += 1
    if cnt2 <= j:
        L2[t-j-1] = f(V, t-j-1, -1)
    
V_sort = sorted(V)
s = sum(V)
ans = 0
for i in range(1, K+1):
    if i >= N:
        c = s
        j = 0
        while j < N:
            if V_sort[j] < 0:
                c -= V_sort[j]
            else:
                j = N
            j += 1
        ans = max(ans, c)
    else:
        c = 0
        for j in range(i+1):
            c = max(c, L1[j]+L2[i-j])
        ans = max(ans, c)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int, input().split())
V = [int(v) for v in input().split()]


def f(L, i, n):
    if i == 0 or len(L) == 0:
        return 0
    if L[n] >= 0:
        t = L[n]
        if n >= 0:
            n += 1
        else:
            n -= 1
        return t+f(L,i-1,n)
    else:
        t = L[n]
        if n >= 0:
            n += 1
        else:
            n -= 1
        if i >= 2:
            return max(f(L, i-2, n), t+f(L, i-1, n))
        else:
            return t+f(L, i-1, n)
    

t = min(K+1, N)
L1 = [0]*(t)
L2 = [0]*(t)
for j in range(t):
    L1[j] = f(V, j, 0)
    L2[t-j-1] = f(V, t-j-1, -1)
    
V_sort = sorted(V)
s = sum(V)
ans = 0
for i in range(1, K+1):
    if i >= N:
        c = s
        j = 0
        while j < N:
            if V_sort[j] < 0:
                c -= V_sort[j]
            else:
                j = N
            j += 1
        ans = max(ans, c)
    else:
        c = 0
        for j in range(i+1):
            c = max(c, L1[j]+L2[i-j])
        ans = max(ans, c)
        
print(ans)