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:
import numpy


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


memo = {}


def best_op(v_list, hand, k):
    # print('call ', v_list, hand, k)
    if (tuple(v_list.tolist()), tuple(hand.tolist()), k) in memo:
        # print('hit')
        return memo[(tuple(v_list.tolist()), tuple(hand.tolist()), 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)
            if not (tuple(v_list_a.tolist()), tuple(hand_a.tolist()), k - 1) in memo:
                memo[(tuple(v_list_a.tolist()), tuple(hand_a.tolist()), k - 1)] = sum_a
        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)
            if not (tuple(v_list_b.tolist()), tuple(hand_b.tolist()), k - 1) in memo:
                memo[(tuple(v_list_b.tolist()), tuple(hand_b.tolist()), k - 1)] = sum_b
        else:
            sum_b = -10 ** 7 * k

        # print('c')
        v_list_c, hand_c, succ = op_c(v_list, hand)
        if succ and hand[0] < 0:
            sum_c = best_op(v_list_c, hand_c, k - 1)
            if not (tuple(v_list_c.tolist()), tuple(hand_c.tolist()), k - 1) in memo:
                memo[(tuple(v_list_c.tolist()), tuple(hand_c.tolist()), k - 1)] = sum_c
        else:
            sum_c = -10 ** 7 * k

        # print('d')
        v_list_d, hand_d, succ = op_d(v_list, hand)
        if succ and hand[0] > 0:
            sum_d = best_op(v_list_d, hand_d, k - 1)
            if not (tuple(v_list_d.tolist()), tuple(hand_d.tolist()), k - 1) in memo:
                memo[(tuple(v_list_d.tolist()), tuple(hand_d.tolist()), k - 1)] = sum_d
        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)
    hand.sort()
    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)
    hand.sort()
    return v_list, hand, True


def op_c(v_list, hand):
    if len(hand) == 0:
        return v_list, hand, False
    min_val = hand[0]
    hand = numpy.delete(hand, 0)
    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_val = hand[0]
    hand = numpy.delete(hand, 0)
    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))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

# N = int(input())
N, K = map(int, input().split())
D = [int(x) for x in input().split()]
# S = input()

ans = 0
for l in range(N + 1):
    if l > K:
        break

    for r in range(N - l + 1):
        if l + r > K:
            break

        l_list = sorted(D[0 : l])
        r_list = sorted(D[N - r : N])

        for discard_l in range(K - (l + r) + 1):
            if l + r + discard_l > K:
                break
                
            for discard_r in range(K - (l + r + discard_l) + 1):
                if l + r + discard_l + discard_r > K:
                    break
                    
                value = sum(l_list[discard_l:])
                value += sum(r_list[discard_r:])

                ans = max(ans, value)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

# N = int(input())
N, K = map(int, input().split())
D = [int(x) for x in input().split()]
# S = input()

ans = 0
for l in range(N + 1):
    if l > K:
        break

    for r in range(N - l + 1):
        if l + r > K:
            break

        l_list = sorted(D[0 : l])
        r_list = sorted(D[N - r : N])

        for discard_l in range(K - (l + r) + 1):
            for discard_r in range(K - (l + r + discard_l) + 1):
                value = sum(l_list[discard_l:])
                value += sum(r_list[discard_r:])

                ans = max(ans, value)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

N,K = map(int,input().split())
vList = [int(x) for x in input().split()]

def dfs(vv, DD, k):
    v = copy.deepcopy(vv)
    D = copy.deepcopy(DD)
    value = sum(v)
    if k == 0:
        return value
    if len(D) > 0:
        v.extend([D[0]])
        a = dfs(v, D[1:], k-1)
        v = v[:-1]
        v.extend([D[-1]])
        b = dfs(v, D[:-1], k-1)
        v = v[:-1]
    else:
        a = 0
        b = 0
        
    if len(v) > 0:
        m = [min(v)]
        idx = v.index(m[0])
        del v[idx]
        D.extend(m)
        c = dfs(v, D, k-1)
        D = D[:-1]
        m.extend(D)
        d = dfs(v, m, k-1)
    else:
        c = 0
        d = 0
    return max(value, a,b,c,d)

result = dfs([], vList, K)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy


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


memo = {}


def best_op(v_list, hand, k):
    # print('call ', v_list, hand, k)
    if (tuple(v_list.tolist()), tuple(hand.tolist()), k) in memo:
        # print('hit')
        return memo[(tuple(v_list.tolist()), tuple(hand.tolist()), 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)
            if not (tuple(v_list_a.tolist()), tuple(hand_a.tolist()), k - 1) in memo:
                memo[(tuple(v_list_a.tolist()), tuple(hand_a.tolist()), k - 1)] = sum_a
        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)
            if not (tuple(v_list_b.tolist()), tuple(hand_b.tolist()), k - 1) in memo:
                memo[(tuple(v_list_b.tolist()), tuple(hand_b.tolist()), k - 1)] = sum_b
        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)
            if not (tuple(v_list_c.tolist()), tuple(hand_c.tolist()), k - 1) in memo:
                memo[(tuple(v_list_c.tolist()), tuple(hand_c.tolist()), k - 1)] = sum_c
        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)
            if not (tuple(v_list_d.tolist()), tuple(hand_d.tolist()), k - 1) in memo:
                memo[(tuple(v_list_d.tolist()), tuple(hand_d.tolist()), k - 1)] = sum_d
        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)
    hand.sort()
    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)
    hand.sort()
    return v_list, hand, True


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


def op_d(v_list, hand):
    if len(hand) == 0:
        return v_list, hand, False
    min_val = hand[0]
    hand = numpy.delete(hand, 0)
    v_list = numpy.append(v_list, min_val)
    hand.sort()
    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))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

# N = int(input())
N, K = map(int, input().split())
D = [int(x) for x in input().split()]
# S = input()

ans_list = set()
for l in range(N + 1):
    if l > K:
        break

    for r in range(N - l + 1):
        if l + r > K:
            break

        l_list = sorted(D[0 : l])
        r_list = sorted(D[N - r : N])

        for discard_l in range(K - (l + r) + 1):
            for discard_r in range(K - (l + r + discard_l) + 1):
                value = sum(l_list[discard_l:])
                value += sum(r_list[discard_r:])

                ans_list.add(value)
        
print(sorted(ans_list, reverse=True)[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop

def enR(have, V, mx, times):
    val = V.pop()
    heappush(have, val)
    #print('en', val, have, V)
    mx = check(have, V, mx, times-1)
    have.remove(val)
    V.append(val)
    return mx

def enL(have, V, mx, times):
    val = V.pop(0)
    heappush(have, val)
    #print('en', val, have, V)
    mx = check(have, V, mx, times-1)
    have.remove(val)
    V.insert(0, val)
    return mx

def deR(have, V, mx, times):
    val = heappop(have)
    V.append(val)
    #print('de', val, have, V)
    mx = check(have, V, mx, times-1)
    heappush(have, val)
    V.pop()
    return mx

def deL(have, V, mx, times):
    val = heappop(have)
    V.insert(0,val)
    #print('de', val, have, V)
    mx = check(have, V, mx, times-1)
    heappush(have, val)
    V = V.pop(0)
    return mx

def check(have, V, mx, times):
    if times > 0:
        if V != []:
            mx = enR(have, V, mx, times)
            mx = enL(have, V, mx, times)
        if have != []:
            #print(have, 'times', times)
            mx = deR(have, V, mx, times)
            mx = deL(have, V, mx, times)
    else:
        if mx < sum(have):
            mx = sum(have)
            #print(times, have, V, mx)

    return mx

sys.setrecursionlimit(10**7)
N,K = map(int,input().split())
V = list(map(int, input().split()))
mx = 0
have = []
print(check(have, V, mx, K))

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,k=map(int,input().split())
d=list(map(int,input().split()))
oll=list(itertools.product(['a','b','c','d'],repeat=k))
ans=0
for ol in oll:
    tv=0
    t=[]
    td=d[:]
    for o in ol:
        if o=='a':
            t+=[td.pop(0)]
            tv=sum(t)
            ans=max(ans,tv)
        elif o=='b':
            t+=[td.pop(-1)]
            tv=sum(t)
            ans=max(ans,tv)
        elif o=='c':
            if len(t)!=0:
                td.insert(0,min(t))
                t.remove(min(t))
                tv=sum(t)
                ans=max(ans,tv)
            else:
                break
        elif o=='d':
            if len(t)!=0:
                td.append(min(t))
                t.remove(min(t))
                tv=sum(t)
                ans=max(ans,tv)
            else:
                break
print(ans)

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]

    if queue not in memo:
        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())
queues = list(map(int, input().split()))

def A(queues):
    queues.reverse()
    a = queues. pop()
    queues.reverse()
    return a
    
def B(queues):
    return queues.pop()

def C(queues, val):
    queues.insert(0, val)

def D(queues, val):
    queues.append(val)

def exec(i, queues, ans, stones, method):
    ans[0] = max(ans[0], sum(stones))

    if i == 0:
        return

    if method == 1 and len(queues) > 0:
        stones.append(A(queues))
    elif method == 2 and len(queues) > 0:
        stones.append(B(queues))
    elif method == 3 and len(stones) > 0:
        stones.sort(reverse=True)
        val = stones.pop()
        C(queues, val)
    elif method == 4 and len(stones) > 0:
        stones.sort(reverse=True)
        val = stones.pop()
        D(queues, val)

    exec(i - 1, queues.copy(), ans, stones.copy(), 1)
    exec(i - 1, queues.copy(), ans, stones.copy(), 2)
    exec(i - 1, queues.copy(), ans, stones.copy(), 3)
    exec(i - 1, queues.copy(), ans, stones.copy(), 4)

ans = [0]
stones = []
exec(K + 1, queues, ans, stones, 0)
print(ans[0])

Submission status: Time Limit Exceeded

Solution code:
import copy

N, K = map(int, input().split())
V = list(map(int, input().split()))
total = -100000000
val = []

def depth(k, V, val):
    global total
    total2 = sum(val)
    if total < total2:
        total = total2
    if k == K: return

    
    if len(V) > 0:
        V2 = copy.copy(V)
        a = V2.pop(0)
        val2 = copy.copy(val)
        val2.append(a)
        depth(k + 1, V2, val2)

        val2 = copy.copy(val)
        val2.insert(0, a)
        depth(k + 1, V2, val2)

        if len(V) != 1:
            V2 = copy.copy(V)
            a = V2.pop()
            val2 = copy.copy(val)
            val2.append(a)
            depth(k + 1, V2, val2)

            val2 = copy.copy(val)
            val2.insert(0, a)
            depth(k + 1, V2, val2)
    
    if len(val) > 0:
        val2 = copy.copy(val)
        a = val2.pop(0)
        V2 = copy.copy(V)
        V2.append(a)
        depth(k + 1, V2, val2)

        V2 = copy.copy(V)
        V2.insert(0, a)
        depth(k + 1, V2, val2)
        if len(val) != 1:
            val2 = copy.copy(val)
            a = val2.pop()
            V2 = copy.copy(V)
            V2.append(a)
            depth(k + 1, V2, val2)

            V2 = copy.copy(V)
            V2.insert(0, a)
            depth(k + 1, V2, val2)

V2 = copy.copy(V)
a = V2.pop(0)
val2 = []
val2.append(a)
depth(1, V2, val2)

V2 = copy.copy(V)
a = V2.pop()
val2 = []
val2.append(a)
depth(1, V2, val2)

if total < 0: print(0)
else: print(total)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline

# N = int(input())
N, K = map(int, input().split())
D = [int(x) for x in input().split()]
# S = input()

ans_list = []
for l in range(N + 1):
    if l > K:
        break

    for r in range(N - l + 1):
        if l + r > K:
            break

        l_list = sorted(D[0 : l])
        r_list = sorted(D[N - r : N])

        for discard_l in range(K - (l + r) + 1):
            for discard_r in range(K - (l + r + discard_l) + 1):
                value = sum(l_list[discard_l:])
                value += sum(r_list[discard_r:])

                ans_list.append(value)
        
print(sorted(ans_list, reverse=True)[0])

Submission status: Time Limit Exceeded

Solution code:


def get_data(data_left, nokori):
    # print(data_left, nokori)
    while 1:
        if len(data_left) == 0:
            break
        if data_left[-1] <= 0:
            data_left.pop(-1)
            nokori += 1
        else:
            break

    # print(data_left, nokori)

    while nokori > 0:
        if len(data_left) == 0:
            break
        min_data = min(data_left)
        if min_data < 0:
            data_left.pop(data_left.index(min_data))
            nokori -= 1
        else:
            break
        # print('uuu', data_left)

    # print(data_left)

    while 1:
        if len(data_left) == 0:
            break
        saigo = data_left[-1]
        min_data = min(data_left)

        if saigo + min_data < 0:
            data_left.pop(-1)

            if len(data_left) == 0:
                nokori += 1
                break
            if min_data not in data_left:
                nokori += 1
            else:
                # print(data_left.index(min_data))
                data_left.pop(data_left.index(min_data))
        else:
            break

    return nokori, data_left

def main():

    num_houseki, num_sousa = map(int, input().split())
    data = list(map(int, input().split()))


    ans = 0


    # dp = defaultdict(int)

    for i in range(num_sousa + 1):

        nokori = 0
        left_ind = min(i, num_houseki)
        nokori += i - left_ind
        righ_ind = max(left_ind, num_houseki - num_sousa + i)
        nokori += num_sousa - i - num_houseki + righ_ind
        data_left = data[:left_ind]
        data_right = data[righ_ind:]

        # print('<><<><<><')
        # print(data_left)
        # print(data_right)

        pre_left = data_left
        pre_right = data_right
        while 1:
            nokori, data_left = get_data(data_left, nokori)
            nokori, data_right = get_data(data_right[::-1], nokori)
            data_right = data_right[::-1]

            if data_left == pre_left and pre_right == data_right:
                break
            else:
                pre_right = data_left
                pre_left = data_left

        # print('----')
        # print(data_left)
        # print(data_right)

        kari = sum(data_right) + sum(data_left)
        if kari > ans:
            ans = kari

    print(ans)







if __name__ == '__main__':
    main()

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]

    if queue not in memo:
        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:
from heapq import heappush, heappop
from collections import deque

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

ans = 0

for i in range(K+1):
    sup = min(i,K)
    for l in range(sup+1):
        for r in range(sup+1-l):
            j = min(i-r-l,r+l)
            hq = []
            dq = deque(V)
            for _ in range(l):
                if dq:
                    item = dq.popleft()
                    heappush(hq, item)
            for _ in range(r):
                if dq:
                    item = dq.pop()
                    heappush(hq, item)
            for _ in range(j):
                if hq:
                    heappop(hq)
            res = sum(hq)
            ans = max(ans,res)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def sousa(k,hand,v):
    if k==0:
        # print(k,sum(hand),hand,v)
        ans.append(sum(hand))
        return
    if len(v)>0:
        # 左から取る
        sousa(k-1,hand+[v[0]],v[1:])
        # 右から取る
        sousa(k-1,hand+[v[-1]],v[:-1])

    if len(hand)>0:
        # 右に入れる
        hand.sort()
        array=[hand[0]]
        sousa(k-1,hand[1:],v+array)
        # 左に入れる
        sousa(k-1,hand[1:],array+v)



n,k=map(int,input().split())
v=list(map(int,input().split()))
ans=[0]
sousa(k,[],v)
# print(ans)
print(max(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(4**K):
    act = i
    valList = []
    V = D.copy()

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

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

table = [[[0,0] for j in range(N+1)]for i in range(N+1)]

def create_table(i,j,k,t):
    if k>K: return
    table[i][j] = [t,k]
    if i+j==N: return
    #print(i,j,table)
    create_table(i+1,j,k+1,t+V[i])
    create_table(i,j+1,k+1,t+V[N-j-1])
    
create_table(0,0,0,0)


for i in range(N+1):
    for j in range(N+1):
        if table[i][j][1]==0: continue
        zank = K - table[i][j][1]
        if zank<1: continue #残数なければ次いく
        del_table = []
        if table[i][j][1] == N: #フルで取った
            del_table = sorted(list(filter(lambda x:x<0,V[:])))
        else:
            del_table = sorted(list(filter(lambda x:x<0,V[:i]+V[N-j:N])))
        table[i][j][0] -=sum(del_table[:zank])
        
ans = 0
for i in range(N+1):
    for j in range(N+1):
        if table[i][j][0] > ans:
            ans = table[i][j][0]
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def dfs(l, r, v, k, D):
#  print(l, r, v, k)
  if k == 0 or l > r:
    return v
  if k == 1:
    return max(v, v+D[l], v+D[r])
  else:
    return max(dfs(l+1, r, v+D[l], k-1, D), \
               dfs(l+1, r, v, k-2, D), \
               dfs(l, r-1, v+D[r], k-1, D), \
               dfs(l, r-1, v, k-2, D))
  
n, k = map(int, input().split())
D = list(map(int, input().split()))

print(dfs(0, n-1, 0, k, D))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
v = [int(x) for x in input().split()]

s = [(v, [])]
while k > 0:
    r = []
    for d, h in s:
        if len(d) > 0:
            a, *rem = d
            r.append((rem, h + [a]))
            *rem, b = d
            r.append((rem, h + [b]))
        if len(h) > 0:
            for j in range(len(h)):
                c = h[j]
                rem = h[:j] + h[j+1:]
                r.append(([c] + d, rem))
                r.append((d + [c], rem))
        r.append((d, h))
    k -= 1
    s = r
print(max(list(map(lambda x: sum(x[1]), s))))

Submission status: Time Limit Exceeded

Solution code:
import itertools


def A(v, m):
    if not v:
        return 0
    m.append(v.pop(0))


def B(v, m):
    if not v:
        return
    m.append(v.pop(-1))
    return


def C(v, m):
    if not m:
        return 0
    n = min(m)
    v.insert(0, n)
    m.remove(n)
    return


def D(v, m):
    if not m:
        return 0
    n = min(m)
    v.insert(-1, n)
    m.remove(n)
    return


N, K = list(map(int, input().split()))
V = list(map(int, input().split()))
fncs = ['a', 'b', 'c', 'd']
result = []
for i in itertools.product(fncs, repeat=K):
    v = V[:]
    mine = []
    for j in i:
        if j == 'a':
            A(v, mine)
        elif j == 'b':
            B(v, mine)
        elif j == 'c':
            C(v, mine)
        else:
            D(v, mine)
    result.append(sum(mine))

print(max(result))

Submission status: Time Limit Exceeded

Solution code:
import copy
import bisect
from collections import deque

def dfs(i, k, v, x):
    if i >= k:
        return sum(x)
    y = [0, 0, 0, 0]
    if len(v) > 0:
        p = v.popleft()
        xi = copy.copy(x)
        bisect.insort(xi, p)
        y[0] = dfs(i + 1, k, v, xi)
        v.appendleft(p)
    if len(v) > 1:
        p = v.pop()
        xi = copy.copy(x)
        bisect.insort(xi, p)
        y[1] = dfs(i + 1, k, v, xi)
        v.append(p)
    if len(x) > 0:
        p = x[0]
        xi = copy.copy(x)
        del xi[0]
        v.appendleft(p)
        y[2] = dfs(i + 1, k, v, xi)
        _ = v.popleft()
        v.append(p)
        y[3] = dfs(i + 1, k, v, xi)
        _ = v.pop()
    return max(y)

n, k = map(int, input().split())
v = deque(list(map(int, input().split())))
x = []
ans = dfs(0, k, v, [])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import deque

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

ans = 0

for i in range(K+1):
    for l in range(i+1):
        for r in range(i+1-l):
            j = min(i-r-l,r+l)
            hq = []
            dq = deque(V)
            for _ in range(l):
                if dq:
                    item = dq.popleft()
                    heappush(hq, item)
            for _ in range(r):
                if dq:
                    item = dq.pop()
                    heappush(hq, item)
            for _ in range(j):
                if hq:
                    heappop(hq)
            res = sum(hq)
            ans = max(ans,res)
        
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

def dp(n, D, v, op):
  if n == K:
    return sum(D)
  
  if op == 0:
    D, v, ret = opA(D, v)
  elif op == 1:
    D, v, ret = opB(D, v)
  elif op == 2:
    D, v, ret = opC(D, v)
  else:
    D, v, ret = opD(D, v)
  
  if ret == False:
    return sum(D)

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