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

Solution code:
from copy import deepcopy

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

all_score = sum(V)
memo = {}

def dfs(queue, hand, depth):
    # print(queue, hand, depth)
    if depth == K:
        score = all_score - sum(queue)
        memo[queue] = score
        # print('return', queue, score)
        return score
    if queue in memo and memo[queue] is not None:
        # print('memo')
        return memo[queue]

    memo[queue] = None

    max_score = all_score - sum(queue)
    if len(queue) > 0:
        # A
        A_queue = queue[1:]
        if A_queue not in memo:
            A_hand = deepcopy(hand)
            A_hand.append(queue[0])
            score = dfs(A_queue, A_hand, depth + 1)
            if score > max_score:
                max_score = score
        # B
        B_queue = queue[:-1]
        if B_queue not in memo:
            B_hand = deepcopy(hand)
            B_hand.append(queue[-1])
            score = dfs(B_queue, B_hand, depth + 1)
            if score > max_score:
                max_score = score

    for i in range(len(hand)):
        # C
        C_queue = (hand[i],) + queue
        if C_queue not in memo:
            C_hand = deepcopy(hand)
            C_hand = C_hand[:i] + C_hand[i+1:]
            score = dfs(C_queue, C_hand, depth + 1)
            if score > max_score:
                max_score = score

        # D
        D_queue = queue + (hand[i],)
        if D_queue not in memo:
            D_hand = deepcopy(hand)
            D_hand = D_hand[:i] + D_hand[i + 1:]
            score = dfs(D_queue, D_hand, depth + 1)
            if score > max_score:
                max_score = score

    memo[queue] = max_score
    # print(queue, max_score)
    return max_score

ans = dfs(V, [], 0)
print('0' if ans < 0 else ans)

Submission status: Time Limit Exceeded

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

ans = 0
s = [(K, V[:], [], False)]
while s:
    cnt, v, bag, flag = s.pop()
    ans = max(ans, sum(bag))
    if cnt > 0 and v and not flag:
        s.append((cnt-1, v[1:], bag + [v[0]], False))
        s.append((cnt-1, v[:-1], bag + [v[-1]], False))
    if cnt > 0 and bag:
        min_bag = min(bag)
        if min_bag < 0:
            bag.remove(min_bag)
            s.append((cnt-1, [], bag, True))


print(ans)

Submission status: Time Limit Exceeded

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

maxValue = 0
actList = [0]*K

for i in range(5**K):
    act = i
    valList = []
    V = D.copy()

    for j in range(K):
        actList[j] = (act % 5)
        act = int(act / 5)

    for j in actList:
        if(j == 0): # 操作 A
            if(len(V) == 0):
                continue
            valList.append(V.pop(0))
        elif(j == 1): # B
            if(len(V) == 0):
                continue
            valList.append(V.pop())
        elif(j == 2): # C
            if(len(valList) == 0):
                continue
            V.insert(0,valList.pop(0))
        elif(j == 3): # D
            if(len(valList) == 0):
                continue
            V.append(valList.pop(0))
        valList.sort()

    val = sum(valList)
    if maxValue < val:
        maxValue = val

print(maxValue)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
import copy
# N,K = map(int,input().split())
# V = list(map(int,input().split()))
N = 17
K = 100
V = [i for i in range(N)]

V = [0 for i in range(N)] + V + [0 for i in range(N)] 

dp = {}

# discardフラグを立てて，一度捨てると取れないように．
def search(start, end, k, own, discard=False):
    if k==K:
        return sum(own)
    key = tuple(own)
    if key in dp:
        return dp[key]
    val_Default = sum(own)
    val_A,val_B = 0,0
    if end-start >= 0 and not discard:
        val_A = search(start+1, end, k+1, own + [V[start]])
        val_B = search(start, end-1, k+1, own + [V[end]])
    if len(own) == 0 and discard:
        return val_Default
    val_Cs = []
    val_Ds = []
    for i,o in enumerate(own):
        own_new = copy.copy(own)
        own_new.pop(i)
        val_Cs.append(search(-1, -1, k+1, own_new, discard=True) )
        # val_Cs.append(search(start-1, end, k+1, own_new, discard=True) )
        # val_Ds.append(search(start, end+1, k+1, own_new, discard=True) )
    # print([val_Default, val_A, val_B], val_Cs , val_Ds)
    # dp[key] = max([val_Default, val_A, val_B] + val_Cs + val_Ds)
    dp[key] = max([val_Default, val_A, val_B] + val_Cs)
    # print(own, [val_Default, val_A, val_B], val_Cs, val_Ds)
    return dp[key]

r = search(N, 2*N-1, 0, [])
print(r)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
v = list(map(int, input().split()))
# 再帰関数でいけそうだぞい
def dfs(que, cost, value):
    if cost <= 0:
        return value
    elif len(que) > 1:
        if que[0] < 0:
            tmp1 = max(dfs(que[1:], cost-1, value+que[0]), dfs(que[1:], cost-2, value))
        else:
            tmp1 = dfs(que[1:], cost-1, value+que[0])
        if que[-1] < 0:
            tmp2 = max(dfs(que[:-1], cost-1, value+que[-1]), dfs(que[:-1], cost-2, value))
        else:
            tmp2 = dfs(que[:-1], cost-1, value+que[-1])
    else:
        tmp1 = value + que[0]
        tmp2 = value + que[-1]
    return max(tmp1, tmp2)

ans = dfs(v, k, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy


def li():
    return list(map(int, input().split()))


def best_op(v_list, hand, k):
    # print('call ', v_list, hand, k)
    if k == 0:
        # print('return')
        return sum(hand)
    if k > 0:
        # print('a')
        # print(v_list, hand)
        v_list_a, hand_a, succ = op_a(v_list, hand)
        if succ:
            sum_a = best_op(v_list_a, hand_a, k - 1)
        else:
            sum_a = -10 ** 7 * k

        # print('b')
        # print(v_list, hand)
        v_list_b, hand_b, succ = op_b(v_list, hand)
        if succ:
            sum_b = best_op(v_list_b, hand_b, k - 1)
        else:
            sum_b = -10 ** 7 * k

        # print('c')
        v_list_c, hand_c, succ = op_c(v_list, hand)
        if succ:
            sum_c = best_op(v_list_c, hand_c, k - 1)
        else:
            sum_c = -10 ** 7 * k

        # print('d')
        v_list_d, hand_d, succ = op_d(v_list, hand)
        if succ:
            sum_d = best_op(v_list_d, hand_d, k - 1)
        else:
            sum_d = -10 ** 7 * k

        v_list_e, hand_e, succ = v_list, hand, True
        sum_e = best_op(v_list_e, hand_e, k - 1)

        # print(sum_a, sum_b, sum_c, sum_d)
        return max(sum_a, sum_b, sum_c, sum_d, sum_e)


def op_a(v_list, hand):
    if len(v_list) == 0:
        return v_list, hand, False
    value = v_list[0]
    v_list = numpy.delete(v_list, 0)
    hand = numpy.append(hand, value)
    return v_list, hand, True


def op_b(v_list, hand):
    if len(v_list) == 0:
        return v_list, hand, False
    value = v_list[len(v_list) - 1]
    v_list = numpy.delete(v_list, len(v_list) - 1)
    hand = numpy.append(hand, value)
    return v_list, hand, True


def op_c(v_list, hand):
    if len(hand) == 0:
        return v_list, hand, False
    min_idx = numpy.argmin(hand)
    min_val = hand[min_idx]
    hand = numpy.delete(hand, min_idx)
    v_list = numpy.insert(v_list, 0, min_val)
    return v_list, hand, True


def op_d(v_list, hand):
    if len(hand) == 0:
        return v_list, hand, False
    min_idx = numpy.argmin(hand)
    min_val = hand[min_idx]
    hand = numpy.delete(hand, min_idx)
    v_list = numpy.append(v_list, min_val)
    return v_list, hand, True


if __name__ == '__main__':
    [n, k] = li()
    v_list = li()
    v_list = numpy.array(v_list, dtype=numpy.int64)
    hand = numpy.array([], dtype=numpy.int64)

    # print(n, k)
    # print(v_list)
    print(max(best_op(v_list, hand, k), 0))

    # 1回だけできるとしたら
    # 左の価値　右の価値　handで一番低い価値*-1　で一番大きいものを選ぶ
    # 左か右なら取り出し　handなら詰める

Submission status: Time Limit Exceeded

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

ans = 0
s = [(K, V[:], [], False)]
while s:
    cnt, v, bag, flag = s.pop()
    ans = max(ans, sum(bag))
    if cnt > 0 and v and not flag:
        s.append((cnt-1, v[1:], bag + [v[0]], False))
        s.append((cnt-1, v[:-1], bag + [v[-1]], False))
    if cnt > 0 and bag:
        bag.sort()
        s.append((cnt-1, [bag[0]] + v, bag[1:], True))
        s.append((cnt-1, v + [bag[0]], bag[1:], True))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
n, k = map(int, input().split())
s_list = list(map(int, input().split()))
h_list = []
res_list = [0]

def rec_ope(s_list, h_list, k, minus_len):
  if k == 0:
    res_list.append(sum(h_list))
    return 0
  if len(h_list) > 0:
    if minus_len <= k:
      tmp_h = h_list.copy()
      min_h = min(h_list)
      tmp_h.remove(min_h)
      tmp_s = s_list.copy()
      tmp_s.insert(0, min_h)
      rec_ope(tmp_s, tmp_h, k-1, minus_len-1)
      tmp_s = s_list.copy()
      tmp_s.append(min_h)
      rec_ope(tmp_s, tmp_h, k-1, minus_len-1)
  if len(s_list) > 0:
    tmp_h = h_list.copy()
    tmp_s = s_list.copy()
    add_s = tmp_s.pop(0)
    tmp_h.append(add_s)
    if add_s < 0:
      minus_len += 1
    rec_ope(tmp_s, tmp_h, k-1, minus_len)
    tmp_h = h_list.copy()
    tmp_s = s_list.copy()
    add_s = tmp_s.pop(-1)
    tmp_h.append(add_s)
    if add_s < 0:
      minus_len += 1
    rec_ope(tmp_s, tmp_h, k-1, minus_len)

rec_ope(s_list, h_list, k, 0)
print(max(res_list))

Submission status: Time Limit Exceeded

Solution code:
N, K = list(map(int, input().split()))
V = list(map(int, input().split()))
opt = ['pol', 'por', 'pul', 'pur']
res = []
def helper(res, Q, M, K):
  if K==0:
    res.append(sum(M))
  else:
    if len(Q) > 0:
      # pol
      helper(res, Q[1:], M+[Q[0]], K-1)
      # por
      helper(res, Q[:-1], M+[Q[-1]], K-1)
      if len(M)>0:
        if min(M) < 0:
          # pul
          helper(res, [min(M)]+Q, [i for i in M if i != min(M)], K-1)
          # por
          helper(res, Q+[min(M)], [i for i in M if i != min(M)], K-1)
    helper(res, Q, M, K-1)
helper(res, V, [], K)
print (max(res))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

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

all_score = sum(V)
memo = {}

def dfs(queue, hand, depth):
    # print(queue, hand, depth)
    if depth == K:
        score = all_score - sum(queue)
        memo[queue] = score
        # print('return', queue, score)
        return score
    if queue in memo:
        # print('memo')
        return memo[queue]

    max_score = all_score - sum(queue)
    if len(queue) > 0:
        # A
        A_queue = queue[1:]
        A_hand = deepcopy(hand)
        A_hand.append(queue[0])
        score = dfs(A_queue, A_hand, depth + 1)
        if score > max_score:
            max_score = score
        # B
        B_queue = queue[:-1]
        B_hand = deepcopy(hand)
        B_hand.append(queue[-1])
        score = dfs(B_queue, B_hand, depth + 1)
        if score > max_score:
            max_score = score

    for i in range(len(hand)):
        # C
        C_queue = (hand[i],) + queue
        C_hand = deepcopy(hand)
        C_hand = C_hand[:i] + C_hand[i+1:]
        score = dfs(C_queue, C_hand, depth + 1)
        if score > max_score:
            max_score = score

        # D
        D_queue = queue + (hand[i],)
        D_hand = deepcopy(hand)
        D_hand = D_hand[:i] + D_hand[i + 1:]
        score = dfs(D_queue, D_hand, depth + 1)
        if score > max_score:
            max_score = score

    memo[queue] = max_score
    # print(queue, max_score)
    return max_score

ans = dfs(V, [], 0)
print('0' if ans < 0 else ans)

Submission status: Time Limit Exceeded

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

def opA(D, v):
  if len(v) != 0:
    D.append(v.pop(0))
  return D, v

def opB(D, v):
  if len(v) != 0:
    D.append(v.pop(-1))
  return D, v

def opC(D, v):
  if len(D) != 0:
    v.insert(0, min(D))
    D.remove(min(D))
  return D, v

def opD(D, v):
  if len(D) != 0:
    v.append(min(D))
    D.remove(min(D))
  return D, v

def dp(n, D, v, op):
  if n == K:
    return sum(D)
  
  if op == 0:
    D, v = opA(D, v)
  elif op == 1:
    D, v = opB(D, v)
  elif op == 2:
    D, v = opC(D, v)
  else:
    D, v = opD(D, v)
  return max(dp(n + 1, D.copy(), v.copy(), 0), dp(n + 1, D.copy(), v.copy(), 1), dp(n + 1, D.copy(), v.copy(), 2), dp(n + 1, D.copy(), v.copy(), 3))

print(max(dp(0, [], V.copy(), 0), dp(0, [], V.copy(), 1), dp(0, [], V.copy(), 2), dp(0, [], V.copy(), 3)))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
v = list(map(int, input().split()))
# 再帰関数でいけそうだぞい
def dfs(que, cost, value):
    if cost <= 0:
        return value
    elif len(que) > 1:
        tmp1 = max(dfs(que[1:], cost-1, value+que[0]), dfs(que[1:], cost-2, value))
        tmp2 = max(dfs(que[:-1], cost-1, value+que[-1]), dfs(que[:-1], cost-2, value))
    else:
        tmp1 = value + que[0]
        tmp2 = value + que[-1]
    return max(tmp1, tmp2)

ans = dfs(v, k, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappush, heappop
n, k = map(int, input().split())
ans = 0
def f(cnt, D, H, sum_H):
    if cnt == k:
        global ans
        if ans < sum_H:
            ans = sum_H
            li = H
        return
    cnt += 1
    if D:
        CH = H[:]
        heappush(CH, D[0])
        f(cnt, D[1:], CH, sum_H + D[0])
        CH = H[:]
        heappush(CH, D[-1])
        f(cnt, D[:-1], CH, sum_H + D[-1])
        if H:
            min_H = heappop(H)
            f(cnt, [min_H] + D, H, sum_H - min_H)
            f(cnt, D + [min_H], H, sum_H - min_H)
    else:
        min_H = heappop(H)
        f(cnt, [min_H] + D, H, sum_H - min_H)
        f(cnt, D + [min_H], H, sum_H - min_H)
def solve():
    D = list(map(int, input().split()))
    f(0, D[:], [], 0)
solve()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

INF = 10 ** 8


def rec(rest_ope, now_d, now_hand):

    if rest_ope == 0:
        return sum(now_hand)

    max_price = -INF

    if len(now_d) > 0:
        left_d = copy.copy(now_d)
        left_hand = copy.copy(now_hand)
        left_hand.append(left_d.pop(0))

        max_price = max(max_price, rec(rest_ope - 1, left_d, left_hand))

        right_d = copy.copy(now_d)
        right_hand = copy.copy(now_hand)
        right_hand.append(right_d.pop(-1))

        max_price = max(max_price, rec(rest_ope - 1, right_d, right_hand))

    if len(now_hand) > 0:
        drop_hand = copy.copy(now_hand)
        drop_hand.pop(drop_hand.index(min(drop_hand)))  # 最小値を削除

        max_price = max(max_price, rec(rest_ope - 1, now_d, drop_hand))

    # do nothing
    max_price = max(max_price, rec(rest_ope - 1, now_d, now_hand))

    return max_price


print(rec(K, V, []))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import itertools
from collections import deque
import heapq

have_v = []

N,K = map(int,input().split())
V = list(map(int,input().split()))
M = 0
for l in list(itertools.product(range(1,5),repeat = K)):
  flag = 1
  have_v = []
  rest_v = deque(V)
  for j in range(len(l)):
    if l[j] == 1:
      if not rest_v:
        flag = 0
        break
      else:
        heapq.heappush(have_v,rest_v.popleft())
    elif l[j] == 2:
      if not rest_v:
        flag = 0
        break
      else:
        heapq.heappush(have_v,rest_v.pop())
    elif l[j] == 3:
      if not have_v:
        flag = 0
        break
      else:
        rest_v.appendleft(heapq.heappop(have_v))
    else:
      if not have_v:
        flag = 0
        break
      else:
        rest_v.append(heapq.heappop(have_v))
  if flag:
    M = max(sum(have_v),M)
print(M)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
dp = {}

def dfs(N, K, k, have, q):
  if k == K:
    return sum(have)
  else:
    if not ((k, tuple(q)) in dp):
      a = [sum(have)]
      if len(q) > 0:
        tmp_q = copy.copy(q)
        tmp_have = copy.copy(have)
        v = tmp_q.popleft()
        tmp_have.append(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
        tmp_q = copy.copy(q)
        tmp_have = copy.copy(have)
        v = tmp_q.pop()
        tmp_have.append(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
      if len(have) > 0:
        tmp_q = copy.copy(q)
        tmp_have = sorted(copy.copy(have))
        v = tmp_have.pop(0)
        tmp_q.appendleft(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
        tmp_q = copy.copy(q)
        tmp_have = sorted(copy.copy(have))
        v = tmp_have.pop(0)
        tmp_q.append(v)
        a.append(dfs(N, K, k+1, tmp_have, tmp_q))
      dp[(k, tuple(q))] = max(a)
    return dp[(k, tuple(q))]


N, K = map(int, input().split())
V = deque(list(map(int, input().split())))
print(dfs(N, K, 0, [], V))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
listV = list(map(int, input().split()))
haveL=[]
memo={}
def maxTaker(haveL, listV, k):
    strH = "".join(list(map(str, haveL)))
    strV = "".join(list(map(str, haveL)))
    key = strH+strV+str(k)
    if key in memo:
        return memo[key]
    else:
        if k == 1:
            if haveL != [] and listV != []:
                minHave = min(haveL)
                memo[key] = max(0, -1*minHave, listV[0], listV[-1])
                return max(0, -1*minHave, listV[0], listV[-1])
            elif haveL == []:
                memo[key] = max(0, listV[0], listV[-1])
                return max(0, listV[0], listV[-1])
            else:
                minHave = min(haveL)
                memo[key] = max(0, -1*minHave)
                return max(0, -1*minHave)

        else:
            if haveL!=[] and listV!=[]:
                haveL.sort()
                minHave = haveL[0]
                listV1 = []
                listV1.extend(listV)
                listV2 = [minHave]
                listV1.extend([minHave])
                listV2.extend(listV)
                haveL1 = [listV[0]]
                haveL2 = [listV[-1]]
                haveL1.extend(haveL)
                haveL2.extend(haveL)
                memo[key] = max(0, maxTaker(haveL[1:], listV1, k-1)-minHave, maxTaker(haveL[1:], listV2, k-1)-minHave,
                                maxTaker(haveL1, listV[1:], k-1)+listV[0], maxTaker(haveL2, listV[:len(listV)-1], k-1)+listV[-1])
                return max(0, maxTaker(haveL[1:], listV1, k-1)-minHave, maxTaker(haveL[1:], listV2, k-1)-minHave, maxTaker(haveL1, listV[1:], k-1)+listV[0], maxTaker(haveL2, listV[:len(listV)-1], k-1)+listV[-1])
            elif haveL == []:
                haveL1 = [listV[0]]
                haveL2 = [listV[-1]]
                haveL1.extend(haveL)
                haveL2.extend(haveL)
                memo[key] = max(0, maxTaker(haveL1, listV[1:], k-1)+listV[0],
                                maxTaker(haveL2, listV[:len(listV)-1], k-1)+listV[-1])
                return max(0,maxTaker(haveL1, listV[1:], k-1)+listV[0], maxTaker(haveL2, listV[:len(listV)-1], k-1)+listV[-1])
            else:
                haveL.sort()
                minHave = haveL[0]
                listV1 = []
                listV1.extend(listV)
                listV2 = [minHave]
                listV1.extend([minHave])
                listV2.extend(listV)
                memo[key] = max(0, maxTaker(haveL[1:], listV1, k-1)-minHave, maxTaker(haveL[1:], listV2, k-1)-minHave)
                return max(0, maxTaker(haveL[1:], listV1, k-1)-minHave, maxTaker(haveL[1:], listV2, k-1)-minHave)

print(maxTaker(haveL, listV, k))

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
v=list(map(int,input().split()))
q=[[0,0,n-1,[]]]
qq=[]
ans=0
while len(q)>0:
  #print(q)
  qi=q.pop()
  #print(qi)
  
  if qi[0]==k or qi[1]==qi[2]+1:
    continue
  q+=[[qi[0]+1,qi[1]+1,qi[2],qi[3]+[v[qi[1]]]]]
  q+=[[qi[0]+1,qi[1],qi[2]-1,qi[3]+[v[qi[2]]]]]
  qq+=[[qi[0]+1,qi[1]+1,qi[2],qi[3]+[v[qi[1]]]]]
  qq+=[[qi[0]+1,qi[1],qi[2]-1,qi[3]+[v[qi[2]]]]]
  
  
while len(qq)>0:
  qi=qq.pop()
  ans=max(ans,sum(qi[3]))
  if qi[0]==k:
    continue
  if len(qi[3])==0:
    continue
  if len(qi[3])==1:
    qq+=[[qi[0]+1,qi[1],qi[2],[]]]
    continue
  #print(qi)
  qi[3].remove(min(qi[3]))
  qq+=[[qi[0]+1,qi[1],qi[2],qi[3]]]
  #print(qi)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

def cnt(arr, k, ans):
    if len(arr) == 0 or k == 0:
        return ans
    
    if len(arr) == 1:
        return ans + (arr[0] if arr[0] > 0 else 0)
    
    ans1 = cnt(arr[1:], k-(1 if arr[0] > -1 or k == 1 else 2), ans + (arr[0] if arr[0] > -1 else 0))
    ans2 = cnt(arr[1:], k-1, ans + arr[0])
    ans3 = cnt(arr[:-1], k-(1 if arr[-1] > -1 or k == 1 else 2), ans + (arr[-1] if arr[-1] > -1 else 0))
    ans4 = cnt(arr[:-1], k-1, ans + arr[-1])

    return max(ans1, ans2, ans3, ans4)
    
def solve():
    N, K = map(int, input().split())
    V = [int(k) for k in input().split()]

    print (cnt(V, K, 0))
    
if __name__ == "__main__":  
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

N, K  = map(int, input().split())
L = deque([int(v) for v in input().split()])
ans = 0

def bfs(count, point):
    global ans
    ans = max(ans, point)
    
    if len(L) == 0:
        return
    
    if count - 1 >= 0:
        left = L.popleft()
        bfs(count - 1, point + left)
        L.appendleft(left)
        
    if count - 1 >= 0:
        right = L.pop()
        bfs(count - 1, point + right)
        L.append(right)
        
    if count - 2 >= 0:
        left = L.popleft()
        if left < 0:
            bfs(count - 2, point)
        L.appendleft(left)
        
    if count - 2 >= 0:
        right = L.pop()
        if right < 0:
            bfs(count - 2, point)
        L.append(right)


bfs(K, 0)
print(ans)

Submission status: Time Limit Exceeded

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

rs = []
def check(k, v, current):
	global rs
	rs += [sum(current)]
	if 0 == k:
		return
	else:
		if current:
			mc = min(current)
			if mc < 0:
				i = current.index(mc)
				check(k - 1, v + [mc], current[:i] + current[i + 1:])
				check(k - 1, [mc] + v, current[:i] + current[i + 1:])
		if v:
			check(k - 1, v[1:], current + [v[0]])
			check(k - 1, v[:-1], current + [v[-1]])
		return

check(K, V, [])

print(max(rs))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

N, K  = map(int, input().split())
L = deque([int(v) for v in input().split()])
ans = 0

def bfs(count, point):
    global ans
    ans = max(ans, point)
    
    if len(L) == 0:
        return
    
    if count - 1 >= 0:
        left = L.popleft()
        bfs(count - 1, point + left)
        L.appendleft(left)
        
    if count - 1 >= 0:
        right = L.pop()
        bfs(count - 1, point + right)
        L.append(right)
        
    if count - 2 >= 0:
        left = L.popleft()
        bfs(count - 2, point)
        L.appendleft(left)
        
    if count - 2 >= 0:
        right = L.pop()
        bfs(count - 2, point)
        L.append(right)


bfs(K, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def do_action(q, temoto, value, k_remain):
    if k_remain == 0:
        return value
    a = b = c = d = e = -100000000
    # a
    if len(q) != 0:
        val = q[0]
        a = do_action(q[1:], temoto + [val], value + val, k_remain - 1)
    # b
    if len(q) != 0:
        val = q[-1]
        b = do_action(q[:-1], temoto + [val], value + val, k_remain - 1)
    temoto.sort()
    # 戻す可能性があるのは負のがあるときのみ
    if len(temoto) > 0 and temoto[0] < 0:
        # c
        if len(temoto) != 0:
            temoto.sort()
            val = temoto[0]
            c = do_action([val] + q , temoto[1:], value - val, k_remain - 1)
        # d
        if len(temoto) != 0:
            temoto.sort()
            val = temoto[0]
            d = do_action(q + [val], temoto[1:], value - val, k_remain - 1)
    # e
    e = do_action(q , temoto, value, k_remain - 1)

    return max(a,b,c,d,e)

n, k = map(int, input().split())
dat_v = map(int, input().split())
dat_v = list(dat_v)
val = do_action(dat_v, [], 0, k)
print(val)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, K: int, V: "List[int]"):

    mani = []
    for ac in range(K+1):
        for bc in range(K+1):
            for cc in range(K+1):
                for dc in range(K+1):
                    if (ac+bc+cc+dc) == K:
                        mani.append([ac,bc,cc,dc])

    max_v = 0
    for m in mani:
        VV = deque(V)
        MV = []
        lenVV = len(VV)
        for i in range(min(m[0],lenVV)):
            MV.append(VV.popleft())

        lenVV = len(VV)
        for i in range(min(m[1],lenVV)):
            MV.append(VV.pop())

        MV.sort()
        MV = deque(MV)
        for i in range(m[2]+m[3]):
            if len(MV) > 0 and MV[0] < 0:
                MV.popleft()

        max_v = max(max_v,sum(MV))

    print(max_v)



            



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    V = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, V)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

ans = 0
s = [(K, V[:], [])]
while s:
    cnt, v, bag = s.pop()
    ans = max(ans, sum(bag))
    if cnt > 0 and v:
        s.append((cnt-1, v[1:], bag + [v[0]]))
        s.append((cnt-1, v[:-1], bag + [v[-1]]))
    if cnt > 0 and bag:
        bag.sort()
        s.append((cnt-1, [bag[0]] + v, bag[1:]))
        s.append((cnt-1, v + [bag[0]], bag[1:]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, K: int, V: "List[int]"):

    mani = []
    for ac in range(K+1):
        for bc in range(K+1):
            for cc in range(K+1):
                for dc in range(K+1):
                    if (ac+bc+cc+dc) <= K:
                        mani.append([ac,bc,cc,dc])

    max_v = 0
    for m in mani:
        VV = deque(V)
        MV = []
        lenVV = len(VV)
        for i in range(min(m[0],lenVV)):
            MV.append(VV.popleft())

        lenVV = len(VV)
        for i in range(min(m[1],lenVV)):
            MV.append(VV.pop())

        MV.sort()
        MV = deque(MV)
        for i in range(m[2]+m[3]):
            if len(MV) > 0 and MV[0] < 0:
                MV.popleft()

        max_v = max(max_v,sum(MV))

    print(max_v)



            



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    V = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, K, V)

if __name__ == '__main__':
    main()