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:
#coding:utf-8
def dbg(*something):
    if DEBUG:
        print(*something)






#正の宝石を戻すことはない
#負の宝石を戻すのは後半

from math import ceil,floor
DEBUG = False
N,K = list(map(int,input().split()))
V = list(map(int,input().split()))


#残りk回のとき深さk以下の場所に正の宝石がない→終了
#i回の操作で取れる石>それまでにとるi-1個の石の和
#深さiにある石vの価値：v - (それまでにとるi-1個の石の和　except (k-i)個の負の石)
'''
'''




def tansaku(left,right,rK,N,score):
    dbg(V[left:right+1],rK,N,score)


    max_v = score + sum(sorted(N)[rK:])


    # n = []
    for i in range(left,min(rK+left, ceil((right - left +1)/2)+left)):
        
        if V[i] <= 0:
            #n.append(V[i])
            continue

        #next_V = V[i+1:left+lenV]
        next_rK = rK - 1 - (i - left)
        next_tmp_v = tansaku(i+1,right,  next_rK, N+V[left:i], score+V[i])
        max_v = max(next_tmp_v , max_v)


        break

    # n = []
    for i in range(right ,max(right - ceil((right-left+1)/2)  ,right-rK)  ,-1 ):
        
        if V[i] <= 0:
            #n.append(V[i])
            continue

        #next_V = V[:i]
        next_rK = rK - 1 - (right - i)
        #next_tmp_v = tansaku(   left,   i- left -1  ,next_rK,N+n,score+V[i])
        next_tmp_v = tansaku(   left,   i-1  ,next_rK,N+V[i+1:right+1],score+V[i])
        max_v = max(next_tmp_v , max_v)
        break


    return max_v

print(tansaku(0,len(V)-1,K,[],0))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
def dbg(*something):
    if DEBUG:
        print(*something)






#正の宝石を戻すことはない
#負の宝石を戻すのは後半

from math import ceil,floor
DEBUG = False
N,K = list(map(int,input().split()))
V = list(map(int,input().split()))


#残りk回のとき深さk以下の場所に正の宝石がない→終了
#i回の操作で取れる石>それまでにとるi-1個の石の和
#深さiにある石vの価値：v - (それまでにとるi-1個の石の和　except (k-i)個の負の石)
'''
'''




def tansaku(left,right,rK,N,score):
    dbg(V[left:right+1],rK,N,score)


    max_v = score + sum(sorted(N)[rK:])


    n = []
    for i in range(left,min(rK+left, ceil((right - left +1)/2)+left)):
        
        if V[i] <= 0:
            n.append(V[i])
            continue

        #next_V = V[i+1:left+lenV]
        next_rK = rK - 1 - (i - left)
        next_tmp_v = tansaku(i+1,right,  next_rK, N+n, score+V[i])
        max_v = max(next_tmp_v , max_v)


        break

    n = []
    for i in range(right ,max(right - ceil((right-left+1)/2)  ,right-rK)  ,-1 ):
        
        if V[i] <= 0:
            n.append(V[i])
            continue

        #next_V = V[:i]
        next_rK = rK - 1 - (right - i)
        #next_tmp_v = tansaku(   left,   i- left -1  ,next_rK,N+n,score+V[i])
        next_tmp_v = tansaku(   left,   i-1  ,next_rK,N+n,score+V[i])
        max_v = max(next_tmp_v , max_v)
        break


    return max_v

print(tansaku(0,len(V)-1,K,[],0))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
def dbg(*something):
    if DEBUG:
        print(*something)






#正の宝石を戻すことはない
#負の宝石を戻すのは後半

from math import ceil,floor
DEBUG = False
N,K = list(map(int,input().split()))
V = list(map(int,input().split()))


#残りk回のとき深さk以下の場所に正の宝石がない→終了
#i回の操作で取れる石>それまでにとるi-1個の石の和
#深さiにある石vの価値：v - (それまでにとるi-1個の石の和　except (k-i)個の負の石)
'''
'''




def tansaku(V,rK,N,score):
    dbg(V,rK,N,score)
    # if rK == 0:
    #     db[]
    #     return score + sum(N)


    max_v = score + sum(sorted(N)[rK:])
    #LV = V[:ceil(len(V)/2)]
    #RV = V[floor(len(V)/2):][::-1]



    n = []
    for i in range(min(rK,ceil(len(V)/2))):
        
        if V[i] <= 0:
            n.append(V[i])
            continue

        next_V = V[i+1:]
        next_rK = rK - 1 - i
        next_tmp_v = tansaku(next_V, next_rK, N+n, score+V[i])
        max_v = max(next_tmp_v , max_v)


        break

    n = []
    for i in range(    len(V)-1    ,   max(floor(len(V)/2),len(V)-1-rK),-1 ):
        
        if V[i] <= 0:
            n.append(V[i])
            continue

        next_V = V[:i]
        next_rK = rK - 1 - (len(V)-1-i)
        next_tmp_v = tansaku(next_V,next_rK,N+n,score+V[i])
        max_v = max(next_tmp_v , max_v)
        break


    return max_v

print(tansaku(V,K,[],0))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
def dbg(*something):
    if DEBUG:
        print(*something)






#正の宝石を戻すことはない
#負の宝石を戻すのは後半

from math import ceil,floor
DEBUG = False
N,K = list(map(int,input().split()))
V = list(map(int,input().split()))


#残りk回のとき深さk以下の場所に正の宝石がない→終了
#i回の操作で取れる石>それまでにとるi-1個の石の和
#深さiにある石vの価値：v - (それまでにとるi-1個の石の和　except (k-i)個の負の石)
'''
'''




def tansaku(V,rK,N,score):
    dbg(V,rK,N,score)
    # if rK == 0:
    #     db[]
    #     return score + sum(N)


    max_v = score + sum(sorted(N)[rK:])
    #LV = V[:ceil(len(V)/2)]
    RV = V[floor(len(V)/2):][::-1]



    n = []
    for i in range(min(rK,ceil(len(V)/2))):
        
        if V[i] <= 0:
            n.append(V[i])
            continue

        next_V = V[i+1:]
        next_rK = rK - 1 - i
        next_tmp_v = tansaku(next_V, next_rK, N+n, score+V[i])
        max_v = max(next_tmp_v , max_v)


        break

    n = []
    for i in range(    len(V)-1    ,   max(floor(len(V)/2),len(V)-1-rK),-1 ):
        
        if V[i] <= 0:
            n.append(V[i])
            continue

        next_V = V[:i]
        next_rK = rK - 1 - (len(V)-1-i)
        next_tmp_v = tansaku(next_V,next_rK,N+n,score+V[i])
        max_v = max(next_tmp_v , max_v)
        break


    return max_v

print(tansaku(V,K,[],0))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
def dbg(*something):
    if DEBUG:
        print(*something)






#正の宝石を戻すことはない
#負の宝石を戻すのは後半

from math import ceil,floor
DEBUG = False
N,K = list(map(int,input().split()))
V = list(map(int,input().split()))


#残りk回のとき深さk以下の場所に正の宝石がない→終了
#i回の操作で取れる石>それまでにとるi-1個の石の和
#深さiにある石vの価値：v - (それまでにとるi-1個の石の和　except (k-i)個の負の石)
'''
'''




def tansaku(V,rK,N,score):
    dbg(V,rK,N,score)
    # if rK == 0:
    #     db[]
    #     return score + sum(N)


    max_v = score + sum(sorted(N)[rK:])
    LV = V[:ceil(len(V)/2)]
    RV = V[floor(len(V)/2):][::-1]



    n = []
    for i in range(min(rK,len(LV))):
        
        if LV[i] <= 0:
            n.append(LV[i])
            continue
        # tmpL = LV[:i]
        # tmpL.sort()
        # j = 0 #捨てる石の数
        # for _ in range(min(rK - 1 - i,len(tmpL)) ):
        #     if tmpL[j] >= 0:
        #         break
        #     j += 1
        # dbg("dbg= ",tmpL)
        # v_tmp = sum(tmpL[j:]) + LV[i]

        # if v_tmp > 0:
        #     next_V = V[i+1:]
        #     next_rK = rK - 1 - i - j
        #     max_v = max(tansaku(next_V,next_rK) + v_tmp, max_v)
        next_V = V[i+1:]
        next_rK = rK - 1 - i
        next_tmp_v = tansaku(next_V, next_rK, N+n, score+LV[i])
        max_v = max(next_tmp_v , max_v)


        break

    n = []
    for i in range(min(rK,len(RV))):
        
        if RV[i] <= 0:
            n.append(RV[i])
            continue
        # tmpL = RV[:i]
        # tmpL.sort()
        # j = 0 #捨てる石の数
        # for _ in range(min(rK - 1 - i,len(tmpL)) ):
        #     if tmpL[j] >= 0:
        #         break
        #     j += 1
        # dbg("dbg= ",tmpL)
        # v_tmp = sum(tmpL[j:]) + RV[i]

        # if v_tmp > 0:
        #     next_V = V[::-1][i+1:]
        #     next_rK = rK - 1 - i - j
        #     max_v = max(tansaku(next_V,next_rK) + v_tmp,max_v)
            # break
        next_V = V[::-1][i+1:][::-1]
        next_rK = rK - 1 - i
        next_tmp_v = tansaku(next_V,next_rK,N+n,score+RV[i])
        max_v = max(next_tmp_v , max_v)
        break


    return max_v

print(tansaku(V,K,[],0))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
def dbg(*something):
    if DEBUG:
        print(*something)






#正の宝石を戻すことはない
#負の宝石を戻すのは後半

from math import ceil,floor
DEBUG = False
N,K = list(map(int,input().split()))
V = list(map(int,input().split()))


#残りk回のとき深さk以下の場所に正の宝石がない→終了
#i回の操作で取れる石>それまでにとるi-1個の石の和
#深さiにある石vの価値：v - (それまでにとるi-1個の石の和　except (k-i)個の負の石)
'''
'''




def tansaku(V,rK):
    if rK == 0:
        return 0


    max_v = 0
    LV = V[:ceil(len(V)/2)]
    RV = V[ceil(len(V)/2):][::-1]


    for i in range(min(rK,len(LV))):
        if LV[i] <= 0:
            continue
        tmpL = LV[:i]
        tmpL.sort()
        j = 0 #捨てる石の数
        for _ in range(min(rK - 1 - i,len(tmpL)) ):
            if tmpL[j] >= 0:
                break
            j += 1
        dbg("dbg= ",tmpL)
        v_tmp = sum(tmpL[j:]) + LV[i]

        if v_tmp > 0:
            next_V = V[i+1:]
            next_rK = rK - 1 - i - j
            max_v = max(tansaku(next_V,next_rK) + v_tmp, max_v)
            # break


    for i in range(min(rK,len(RV))):
        if RV[i] <= 0:
            continue
        tmpL = RV[:i]
        tmpL.sort()
        j = 0 #捨てる石の数
        for _ in range(min(rK - 1 - i,len(tmpL)) ):
            if tmpL[j] >= 0:
                break
            j += 1
        dbg("dbg= ",tmpL)
        v_tmp = sum(tmpL[j:]) + RV[i]

        if v_tmp > 0:
            next_V = V[::-1][i+1:]
            next_rK = rK - 1 - i - j
            max_v = max(tansaku(next_V,next_rK) + v_tmp,max_v)
            # break

    return max_v


print(tansaku(V,K))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
def dbg(*something):
    if DEBUG:
        print(*something)






#正の宝石を戻すことはない
#負の宝石を戻すのは後半

from math import ceil,floor
DEBUG = False
N,K = list(map(int,input().split()))
V = list(map(int,input().split()))


#残りk回のとき深さk以下の場所に正の宝石がない→終了
#i回の操作で取れる石>それまでにとるi-1個の石の和
#深さiにある石vの価値：v - (それまでにとるi-1個の石の和　except (k-i)個の負の石)
'''
'''




def tansaku(V,rK):
    if rK == 0:
        return 0


    max_v = 0
    LV = V[:ceil(len(V)/2)]
    RV = V[floor(len(V)/2):][::-1]


    for i in range(min(rK,len(LV))):
        if LV[i] <= 0:
            continue
        tmpL = LV[:i]
        tmpL.sort()
        j = 0 #捨てる石の数
        for _ in range(min(rK - 1 - i,len(tmpL)) ):
            if tmpL[j] >= 0:
                break
            j += 1
        dbg("dbg= ",tmpL)
        v_tmp = sum(tmpL[j:]) + LV[i]

        if v_tmp > 0:
            next_V = V[i+1:]
            next_rK = rK - 1 - i - j
            next_v_tmp = tansaku(next_V,next_rK)
            if next_v_tmp + v_tmp >= max_v:
                max_v = next_v_tmp + v_tmp

    for i in range(min(rK,len(RV))):
        if RV[i] <= 0:
            continue
        tmpL = RV[:i]
        tmpL.sort()
        j = 0 #捨てる石の数
        for _ in range(min(rK - 1 - i,len(tmpL)) ):
            if tmpL[j] >= 0:
                break
            j += 1
        dbg("dbg= ",tmpL)
        v_tmp = sum(tmpL[j:]) + RV[i]

        if v_tmp > 0:
            next_V = V[::-1][i+1:][::-1]
            next_rK = rK - 1 - i - j
            next_v_tmp = tansaku(next_V,next_rK)
            if next_v_tmp + v_tmp >= max_v:
                max_v = next_v_tmp + v_tmp

    return max_v


print(tansaku(V,K))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

que = deque([(0, [], V, 0, True, True)])  # total, negative items, deque, count, left_flag, right_flag
best = 0
while que:
    t, s, v, n, lf, rf = que.pop()
    if n >= K:
        best = max([best, t + sum(s)])
        continue
    if v:
        if lf:
            if v[0] >= 0:
                best = max([best, t + v[0] + sum(s)])
                que.append((t + v[0], s, v[1:], n + 1, lf, rf))
            else:
                que.append((t, s + [v[0]], v[1:], n + 1, lf, rf))
        if rf and len(v) > 1:
            if v[-1] >= 0:
                best = max([best, t + v[-1] + sum(s)])
                que.append((t + v[-1], s, v[:-1], n + 1, lf, rf))
            else:
                que.append((t, s + [v[-1]], v[:-1], n + 1, lf, rf))
    if s:
        s.sort()
        que.append((t, s[1:], [s[0]] + v, n + 1, False, rf))
        que.append((t, s[1:], v + [s[0]], n + 1, lf, False))
        best = max([best, t + sum(s[1:])])

print(best)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

que = deque([(set(), V, 0)])
best = 0
while que:
    s, v, n = que.pop()
    if n >= K:
        best = max([best, sum(s)])
        continue
    if v:
        que.append((s | set([v[0]]), v[1:], n + 1))
        if len(v) > 1:
            que.append((s | set([v[-1]]), v[:-1], n + 1))
    if s:
        for i in s:
            que.append((s - set([i]), [i] + v, n + 1))
            que.append((s - set([i]), v + [i], n + 1))

print(best)

Submission status: Time Limit Exceeded

Solution code:
import math, itertools, copy
 
# 入力受け取り
N, K = list(map(int, input().split()))
V = list(map(int, input().split()))

# N, K = 6, 4
# V = [-10, 8, 2, 1, 2, 6]
# N, K = 6, 3
# V = [-6, -100, 50, -2, -5, -3]
max = 0


# 操作上限をKとし、実際に操作する回数をk回とする
# k回の操作のうち、l回は取り出す操作、m回は詰める操作とする
# 詰める宝石がなくなってはいけないので、l >= m が成り立つ

for k in range(K + 1): # 操作する回数をkで表す
	for l in range((k + 1) // 2, min(k + 1, N + 1)): # k = l + m かつ　l >= m から、l >= k / 2　が言える
		for left in range(l + 1):
			# 初期化処理
			trg_V = copy.deepcopy(V)
			hand = []
			for i in range(left): # 左からleft回popする
				hand.append(trg_V.pop(0))
			for i in range(l - left): # 右からl - left回popする
				hand.append(trg_V.pop(-1))
			total = sum(sorted(hand, reverse = True)[0 : len(hand) - (k - l)])
			# 最大値更新
			if max < total:
				max = total
				
print(max)

Submission status: Time Limit Exceeded

Solution code:
import math, itertools, copy
 
# 入力受け取り
N, K = list(map(int, input().split()))
V = list(map(int, input().split()))

# N, K = 6, 4
# V = [-10, 8, 2, 1, 2, 6]
# N, K = 6, 3
# V = [-6, -100, 50, -2, -5, -3]
max = 0


# 操作上限をKとし、実際に操作する回数をk回とする
# k回の操作のうち、l回は取り出す操作、m回は詰める操作とする
# 詰める宝石がなくなってはいけないので、l >= m が成り立つ

for k in range(K + 1): # 操作する回数をkで表す
	for l in range((k + 1) // 2, min(k + 1, N + 1)): # k = l + m かつ　l >= m から、l >= k / 2　が言える
		for left in range(l + 1):
			# 初期化処理
			trg_V = copy.deepcopy(V)
			hand = []
			for i in range(left): # 左からleft回popする
				hand.append(trg_V.pop(0))
			for i in range(l - left): # 右からl - left回popする
				hand.append(trg_V.pop(-1))
			for i in range(k - l): # 手札を捨てる操作をm = k - l 回行う
				hand.pop(hand.index(min(hand)))
			total = sum(hand)
			# 最大値更新
			if max < total:
				max = total
				
print(max)

Submission status: Time Limit Exceeded

Solution code:

import copy

class MyClass():

    maxSum = 0

    def do(self, baseList, _temochi, leftIndex, rightIndex, nokoriSousaCount):
        if nokoriSousaCount < 0:
            return

        sum = 0
        minNum = 0

        for each in _temochi:
            sum += each
            if each < 0 and each < minNum:
                minNum = each

        if self.maxSum < sum:
            self.maxSum = sum

        if leftIndex <= rightIndex:
            temochi = copy.copy(_temochi)
            temochi.append(baseList[leftIndex])
            self.do(baseList, temochi, leftIndex + 1, rightIndex, nokoriSousaCount - 1)

            temochi = copy.copy(_temochi)
            temochi.append(baseList[rightIndex])
            self.do(baseList, temochi, leftIndex, rightIndex - 1, nokoriSousaCount - 1)
            
        self.removeMin(_temochi, minNum, leftIndex, rightIndex, nokoriSousaCount - 1)

    def removeMin(self, _temochi, minNum, leftIndex, rightIndex, nokoriSousaCount):
        if minNum < 0 and len(_temochi) > 0 and nokoriSousaCount > 0:
            #minNum = min(_temochi)
            #if minNum < 0:
                #temochi = copy.copy(_temochi)
            _temochi.remove(minNum)
            self.do(baseList, _temochi, leftIndex, rightIndex, nokoriSousaCount)


count, opeCount = map(int, input().split())
baseList = list(map(int, input().split()))

doClass = MyClass()
doClass.do(baseList, [], 0, count - 1, opeCount)

print(doClass.maxSum)

Submission status: Time Limit Exceeded

Solution code:

import copy

class MyClass():

    maxSum = 0

    def do(self, baseList, _temochi, leftIndex, rightIndex, nokoriSousaCount):
        if nokoriSousaCount < 0:
            return

        sum = 0
        for each in _temochi:
            sum += each

        if self.maxSum < sum:
            self.maxSum = sum

        if leftIndex <= rightIndex:
            temochi = copy.copy(_temochi)
            temochi.append(baseList[leftIndex])
            self.do(baseList, temochi, leftIndex + 1, rightIndex, nokoriSousaCount - 1)

            temochi = copy.copy(_temochi)
            temochi.append(baseList[rightIndex])
            self.do(baseList, temochi, leftIndex, rightIndex - 1, nokoriSousaCount - 1)
            
        self.removeMin(_temochi, leftIndex, rightIndex, nokoriSousaCount - 1)

    def removeMin(self, _temochi, leftIndex, rightIndex, nokoriSousaCount):
        if len(_temochi) > 0 and nokoriSousaCount > 0:
            minNum = min(_temochi)
            if minNum < 0:
                #temochi = copy.copy(_temochi)
                _temochi.remove(minNum)
                self.do(baseList, _temochi, leftIndex, rightIndex, nokoriSousaCount)


count, opeCount = map(int, input().split())
baseList = list(map(int, input().split()))

doClass = MyClass()
doClass.do(baseList, [], 0, count - 1, opeCount)

print(doClass.maxSum)

Submission status: Time Limit Exceeded

Solution code:

import copy


class MyClass():

    maxSum = 0

    def do(self, baseList, _temochi, leftIndex, rightIndex, nokoriSousaCount):
        if nokoriSousaCount < 0:
            return

        sum = 0
        for each in _temochi:
            sum += each

        if self.maxSum < sum:
            self.maxSum = sum

        if leftIndex <= rightIndex:
            temochi = copy.copy(_temochi)
            temochi.append(baseList[leftIndex])
            self.do(baseList, temochi, leftIndex + 1, rightIndex, nokoriSousaCount - 1)

            temochi = copy.copy(_temochi)
            temochi.append(baseList[rightIndex])
            self.do(baseList, temochi, leftIndex, rightIndex - 1, nokoriSousaCount - 1)
            
        self.removeMin(_temochi, leftIndex, rightIndex, nokoriSousaCount - 1)

    def removeMin(self, _temochi, leftIndex, rightIndex, nokoriSousaCount):
        if len(_temochi) > 0 and nokoriSousaCount > 0:
            minNum = min(_temochi)
            if minNum < 0:
                temochi = copy.copy(_temochi)
                temochi.remove(minNum)
                self.do(baseList, temochi, leftIndex, rightIndex, nokoriSousaCount)


count, opeCount = map(int, input().split())
baseList = list(map(int, input().split()))

doClass = MyClass()
doClass.do(baseList, [], 0, count - 1, opeCount)

print(doClass.maxSum)

Submission status: Time Limit Exceeded

Solution code:
import copy

class MyClass():

    maxSum = 0

    def do(self, baseList, _temochi, leftIndex, rightIndex, nokoriSousaCount):
        if nokoriSousaCount < 0:
            return

        sum = 0
        for each in _temochi:
            sum += each

        if self.maxSum < sum:
            self.maxSum = sum

        if leftIndex <= rightIndex:
            temochi = copy.copy(_temochi)
            temochi.append(baseList[leftIndex])
            self.do(baseList, temochi, leftIndex + 1, rightIndex, nokoriSousaCount - 1)

            temochi = copy.copy(_temochi)
            temochi.append(baseList[rightIndex])
            self.do(baseList, temochi, leftIndex, rightIndex - 1, nokoriSousaCount - 1)
            
        self.removeMin(_temochi, leftIndex, rightIndex, nokoriSousaCount - 1)

    def removeMin(self, _temochi, leftIndex, rightIndex, nokoriSousaCount):
        temochi = copy.copy(_temochi)
        if len(temochi) > 0 and nokoriSousaCount > 0:
            minNum = min(temochi)
            if minNum < 0:
                temochi.remove(minNum)
                self.do(baseList, temochi, leftIndex, rightIndex, nokoriSousaCount)


count, opeCount = map(int, input().split())
baseList = list(map(int, input().split()))

doClass = MyClass()
doClass.do(baseList, [], 0, count - 1, opeCount)

print(doClass.maxSum)

Submission status: Time Limit Exceeded

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

score = {}

def Compute(n, D, S):
    D2 = tuple(D)
    S2 = tuple(S)
    if (n, D2, S2) in score:
        return score[(n, D2, S2)]
    if n == 0:
        return sum(S)

    candidate = [Compute(n - 1, D, S)]
    if len(D) > 0:
        candidate.append(Compute(n - 1, D[1:], sorted(S + [D[0]])))
        candidate.append(Compute(n - 1, D[:-1], sorted(S + [D[-1]])))
    for i in range(len(S)):
        candidate.append(Compute(n - 1, D + [S[i]], S[:i] + S[i+1:]))
        candidate.append(Compute(n - 1, [S[i]] + D, S[:i] + S[i+1:]))
    return max(candidate)

print Compute(K, V, [])

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy

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


def dfs(q, have, count, operate):
    if operate == 0:
        heapq.heappush(have, q[0])
        q = q[1:]
    elif operate == 1:
        heapq.heappush(have, q[-1])
        q = q[:-1]
    elif operate == 2:
        sub = heapq.heappop(have)
        q.insert(0, sub)
    elif operate == 3:
        sub = heapq.heappop(have)
        q.append(sub)

    count += 1
    if count >= k:
        return sum(have)

    a = -float('inf')
    b = -float('inf')
    c = -float('inf')
    d = -float('inf')
    e = dfs(q, have, count, -1)  # 何もしない

    if len(q) > 0:
        a = dfs(copy.deepcopy(q), copy.deepcopy(have), count, 0)
        b = dfs(copy.deepcopy(q), copy.deepcopy(have), count, 1)
    if len(have) > 0:
        c = dfs(copy.deepcopy(q), copy.deepcopy(have), count, 2)
        d = dfs(copy.deepcopy(q), copy.deepcopy(have), count, 3)

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


print(dfs(v, [], -1, -1))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun  2 14:23:16 2019

@author: hisaki
"""
#宝石問題を得くプログラム

decision = []

def func(recursive_num, myList, ValueList):
    global Sum
    global K
    #得点計算
    temp = sum(myList)
    if temp > Sum:
        Sum = temp

    if recursive_num == K:
        return




    if ValueList:
        save_myList = myList[:]
        save_ValueList = ValueList[:]
        
       # myList.append(ValueList.pop(0))
        save_myList.append(save_ValueList.pop(0))
        func(recursive_num+1,save_myList,save_ValueList)
    #    ValueList.insert(0,myList.pop(-1))#もとに戻す
    if ValueList:
#        myList.append(ValueList.pop(-1))
        save_myList = myList[:]
        save_ValueList = ValueList[:]
        save_myList.append(save_ValueList.pop(-1))
        func(recursive_num+1, save_myList, save_ValueList)
#        ValueList.insert(-1,myList.pop(-1))#もとに戻す

    if myList:
        temp_index = myList.index(min(myList))
 #       ValueList.insert(0,myList.pop(temp_index))
        
        save_myList = myList[:]
        save_ValueList = ValueList[:]
        save_ValueList.insert(0,save_myList.pop(temp_index))
        func(recursive_num+1, save_myList, save_ValueList)

#        myList.append(ValueList.pop(0))
    if myList:
        temp_index = myList.index(min(myList))
 #       ValueList.insert(-1,myList.pop(temp_index))
        save_myList = myList[:]
        save_ValueList = ValueList[:]
        save_ValueList.insert(-1,save_myList.pop(temp_index))
        func(recursive_num+1, save_myList, save_ValueList)
   #     myList.append(ValueList.pop(-1))

    return

N, K = map(int, input().split())
ValueList = list(map(int, input().split()))
recursive_num = 0
myList=[]
Sum=0
func(recursive_num, myList, ValueList)
print (Sum)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

max_value = 0

def operate(hnd, d, hnd_len, d_len, k, value, returned):
    global max_value

    if k > 0:
        if not returned and d_len > 0:
            max_value = max(max_value, value + d[0])
            max_value = max(max_value, value + d[-1])

            h = hnd[:]
            bisect.insort_left(h, d[0])
            operate(h, d[1:], hnd_len+1, d_len-1, k-1, value + d[0], False)

            h = hnd[:]
            bisect.insort_left(h, d[-1])
            operate(h, d[:-1], hnd_len+1, d_len-1, k-1, value + d[-1], False)

        if hnd_len > 0:
            max_value = max(max_value, value - hnd[0])
            operate(hnd[1:], [hnd[0]] + d, hnd_len-1, d_len+1, k-1, value - hnd[0], True)

operate([], V, 0, len(V), K, 0, False)

print(max_value)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product

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

max_v = -float("inf")
for actions in product(*([range(4)] * K)):
  d = deque(V)
  hand = []
  for action in actions:
    if action == 0:
      if len(d) != 0:
        hand.append(d.popleft())
        
    elif action == 1:
      if len(d) != 0:
        hand.append(d.pop())
        
    elif action == 2:
      if len(hand) > 0:
        min_hand = min(hand)
        if min_hand < 0:
          d.appendleft(min_hand)
          hand.remove(min_hand)
        
    elif action == 3:
      if len(hand) > 0:
        min_hand = min(hand)
        if min_hand < 0:
          d.append(min_hand)
          hand.remove(min_hand)

  sum_v = sum(hand)
  if max_v < sum_v:
    max_v = sum_v
print(max_v)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import product

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

max_v = -float("inf")
for actions in product(*([range(4)] * K)):
  d = deque(V)
  hand = []
  for action in actions:
    if action == 0:
      try:
        hand.append(d.popleft())
      except IndexError:
        break
        
    elif action == 1:
      try:
        hand.append(d.pop())
      except IndexError:
        break
        
    elif action == 2:
      if len(hand) > 0:
        min_hand = min(hand)
        if min_hand < 0:
          d.appendleft(min_hand)
          hand.remove(min_hand)
        
    elif action == 3:
      if len(hand) > 0:
        min_hand = min(hand)
        if min_hand < 0:
          d.append(min_hand)
          hand.remove(min_hand)

  sum_v = sum(hand)
  if max_v < sum_v:
    max_v = sum_v
print(max_v)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import copy


class Deque:
    def __init__(self, default_deque: list, max_count: int):
        self.in_hand = []
        self.deque = default_deque
        self.operation_count = 0
        self.max_count = max_count

    def operation(self, operation_type: str):
        if operation_type == "A":
            self.in_hand.append(self.deque[0])
            del self.deque[0]
            self.operation_count += 1
        elif operation_type == "B":
            self.in_hand.append(self.deque[-1])
            del self.deque[-1]
            self.operation_count += 1
        elif operation_type == "C":
            self.in_hand.sort()
            for i in range(self.max_count - self.operation_count):
                if self.in_hand[0] < 0:
                    del self.in_hand[0]
                else:
                    return


if __name__ == '__main__':
    max_repeat_count = int(input().split()[1])
    value_list = list(map(int, input().split()))
    point_list = []
    for repeat_count in range(max_repeat_count+1):
        operation_pattern_iter = itertools.product(["A", "B"], repeat=repeat_count)
        for operation_pattern in operation_pattern_iter:
            deque = Deque(copy.copy(value_list), max_repeat_count)
            for operation in operation_pattern:
                try:
                    deque.operation(operation)
                except:
                    break
            else:
                try:
                    deque.operation("C")
                    point_list.append(sum(deque.in_hand))
                except Exception as e:
                    point_list.append(sum(deque.in_hand))
                    break
    print(max(point_list))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import copy


class Deque:
    def __init__(self, default_deque: list):
        self.in_hand = []
        self.deque = default_deque

    def operation(self, operation_type: str):
        if operation_type == "A":
            self.in_hand.append(self.deque[0])
            del self.deque[0]
        elif operation_type == "B":
            self.in_hand.append(self.deque[-1])
            del self.deque[-1]
        elif operation_type == "C":
            if min(self.in_hand) < 0:
                _index = self.in_hand.index(min(self.in_hand))
                del self.in_hand[_index]
            else:
                return True


if __name__ == '__main__':
    max_repeat_count = int(input().split()[1])
    value_list = list(map(int, input().split()))
    point_list = []
    for repeat_count in range(max_repeat_count+1):
        operation_pattern_iter = itertools.product(["A", "B"], repeat=repeat_count)
        for operation_pattern in operation_pattern_iter:
            deque = Deque(copy.copy(value_list))
            for operation in operation_pattern:
                try:
                    deque.operation(operation)
                except:
                    break
            else:
                for remove in range(max_repeat_count - repeat_count):
                    try:
                        if deque.operation("C"):
                            point_list.append(sum(deque.in_hand))
                            break
                    except:
                        point_list.append(sum(deque.in_hand))
                        break
                else:
                    point_list.append(sum(deque.in_hand))
    print(max(point_list))