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: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    n, k = map(int, input().split())

    v_s = list(map(int, input().split()))
    v_s_rev = list(reversed(v_s))

    ans = 0
    for i in range(min(n, k) + 1):
        left = i

        for j in range(min(n, k) + 1 - i):
            right = j
            remove = min(n, k) - i - j
            if k > n:
                remove += k - n

            val_list = v_s[0:left] + v_s_rev[0:right]
            val_list.sort()
            for loop_k in range(remove):
                if len(val_list) == 0:
                    break
                if len(val_list) < loop_k + 1:
                    break
                if val_list[loop_k] >= 0:
                    break
                val_list[loop_k] = 0

            ans = max(ans, sum(val_list))

    print(ans)


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """6 4
-10 8 2 1 2 6"""
        output = """14"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """6 4
-6 -100 50 -2 -5 -3"""
        output = """44"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """6 3
-6 -100 50 -2 -5 -3"""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """6 1
-100 14 1 1 -1 10"""
        output = """10"""
        self.assertIO(test_input, output)

    def test_input_5(self):
        test_input = """6 2
-100 14 1 1 -1 10"""
        output = """10"""
        self.assertIO(test_input, output)

    def test_input_6(self):
        test_input = """6 3
-100 14 1 1 -1 10"""
        output = """14"""
        self.assertIO(test_input, output)

    def test_input_7(self):
        test_input = """6 4
-100 14 1 1 -1 10"""
        output = """24"""
        self.assertIO(test_input, output)

    def test_input_8(self):
        test_input = """6 5
-100 14 1 1 -1 10"""
        output = """25"""
        self.assertIO(test_input, output)

    def test_input_9(self):
        test_input = """6 6
-100 14 1 1 -1 10"""
        output = """26"""
        self.assertIO(test_input, output)

    def test_input_10(self):
        test_input = """6 7
-100 14 1 1 -1 10"""
        output = """26"""
        self.assertIO(test_input, output)

    def test_input_11(self):
        test_input = """7 100
-100 14 -40 1 1 -30 10"""
        output = """26"""
        self.assertIO(test_input, output)

    def test_input_20(self):
        test_input = """50 100
-764207 3102944 -2816278 3249966 5606865 -5997439 4365454 1776907 -1954736 1584162 -437416 -964246 -1828950 -9965518 8636253 -6232397 3421258 -7526570 -7457280 7482600 -1554803 1252 6781335 -3233072 9958581 2263691 -3088247 -2356190 7836991 -1918599 -164787 -9946145 -4801498 3171733 4929342 -6133400 1034826 3746419 -8038615 -7593315 -6791676 5749280 -6696702 6056324 1545511 -2745311 7686370 9321150 -140154 1709122"""
        output = """111018336"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
v = list(map(int, input().split()))
reverse_v = v[::-1]
lst = [0] * (k + 1)
left = [[]]
right = [[]]
for i in range(1, n+1):
  left.append(v[:i])
  right.append(reverse_v[:i])

for cnt in range(1, k+1):
  rest = k - cnt
  total = 0
  if cnt <= n:
    for j in range(cnt+1):
      lst_j = left[j] + right[cnt-j]
      lst_j.sort()
      l = cnt
      for idx in range(cnt):
        if lst_j[idx] >= 0:
          l = idx
          break
      if l == cnt:
        value = 0
      else:
        flg = min(l, rest)
        value = sum(lst_j[flg:])
      if value > total:
        total = value
    lst[cnt] = total

ans = max(lst)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
V = list(map(int, input().split()))
ans = 0
for anum in range(min(N, K) + 1):
    owned = V[:anum]
    for bnum in range(min(N, K) - anum + 1):
        if bnum > 0:
            owned.append(V[-bnum])
        owned.sort()
        cdnum = K - (anum + bnum)
        total = 0
        for v in owned:
            if v < 0 and 0 < cdnum:
                cdnum -= 1
            else:
                total += v
        ans = max(ans, total)
print(ans)

Submission status: Accepted

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

ans = 0

for a in range(min(N,K)+1):
    for b in range(min(N,K)-a+1):
        cur = V[:a] + V[N-b:]
        cur.sort()

        idx = 0
        while idx < min(K-a-b, len(cur)):
            if cur[idx] > 0: break
            else: idx += 1
        
        ans = max(ans, sum(cur[idx:]))
    
print(ans)

Submission status: Accepted

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

max_val = 0
left_hq = list()
left_val = 0
for left in range(N+1):
    if left > 0:
        heapq.heappush(left_hq,V[left-1])
        left_val += V[left-1]
        all_hq = copy.deepcopy(left_hq)
        all_val = left_val
        for right in range(N+1):
            if right+left > K or right+left > N :
                continue
            if right > 0:
                heapq.heappush(all_hq,V[-right])
                all_val += V[-right]
            
            temp_hq = copy.deepcopy(all_hq)
            temp_val = all_val
            for i in range(K-left-right):
                if len(temp_hq) == 0:
                    break
                else:
                    minus = heapq.heappop(temp_hq)
                    if minus > 0:
                        break
                    temp_val -= minus
                    
            if temp_val > max_val:
                max_val = temp_val
print(max_val)

Submission status: Accepted

Solution code:

from collections import deque

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

ans = 0
for a in range(K + 1):
    for b in range(K + 1 - a):
        if a + b > N:
            continue

        q = deque(X)
        tmp = []
        for _ in range(a):
            tmp.append(q.popleft())

        for _ in range(b):
            tmp.append(q.pop())

        tmp.sort(reverse=True)
        cnt = 0
        for _ in range(K - a - b):
            if tmp and tmp[-1] < 0:
                tmp.pop()

        ans = max(ans, sum(tmp))

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N,K = (int(x) for x in input().rstrip('\n').split())
vs = [int(x) for x in input().rstrip('\n').split()]
g = [vs[0],vs[-1]]
rest = K
for k in [K-1,K]:
  for b in range(K//2):
    t = k-b
    if t>N:
      t=N
    for i in range(t+1):
      v = []
      if i <t:
        v.extend(vs[:i])
        v.extend(vs[-(t-i):])
        for _ in range(b):
          if min(v)<0:
            v.remove(min(v))
          else:
            break
      else:
        v.extend(vs[:t])
        for _ in range(b):
          if min(v)<0:
          	v.remove(min(v))
      g.append(sum(v))
if max(g)<0:
  print(0)
else:
  print(max(g))

Submission status: Accepted

Solution code:
n , k = map(int, input().split())
v = list(map(int,input().split()))
ma = float('INF')*(-1)
m = min(n,k)
for i in range(m+1):
    for j in range(m+1-i):
        vl=v[:i]
        vr=v[n-j:]
        ans = sum(vl)+sum(vr)
        vb=vl+vr
        vb.sort()
        m2 = min(k-i-j, len(vb))
        for l in range(m2):
            if vb[l]<0:
                ans-=vb[l]
            else:
                break
        ma = max(ans,ma)
if ma<0:
    ma = 0
print(ma)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    ans = -float("inf")
    for t in range(min(N, K) + 1):
        s = K - t
        for l in range(t + 1):
            r = t - l
            gem = V[:l]
            gem += V[-r:] if r != 0 else []
            gem.sort()
            value = sum(gem)
            for i in range(min(s, t)):
                if gem[i] < 0:
                    value -= gem[i]
                else:
                    break
            ans = max(ans, value)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import copy
    n,k = map(int,input().split())
    v = list(map(int,input().split()))
    ans = 0
    for i in range(min(n+1,k+1)):
        t = v[0:i]
        for j in range(min(n-i+1,k-i+1)):
            t_ = copy.deepcopy(t)
            t_ += v[n-j:n]
            
            r = k-i-j
            t_ = sorted(t_)
            cnt = 0
            for l in range(len(t_)):
                if t_[l]<0 and cnt<r:
                    t_[l] = 0
                    cnt += 1
                else:
                    break
            if ans<sum(t_):
                ans = sum(t_)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
v = list(map(int,input().split()))
ans = 0
for a in range(min(n,k)+1):
    for b in range(min(n,k)-a+1):
        c = v[:a] + v[n-b:]
        c = sorted(c)
        for i in range(k-a-b):
            if len(c) == 0:
                break
            if c[0] < 0:
                c = c[1:]
            else:
                break
        ans = max(ans,sum(c))
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
v = list(map(int, input().split()))
m = min(n, k)
max_score = 0
for i in range(m+1):
    for j in range(m+1-i):
        vals = v[:i] if j == 0 else v[:i] + v[-j:]
        minus = list(filter(lambda x : x < 0, vals))
        minus.sort()
        score = sum(vals) - sum(minus[:min(k - i - j, len(minus))])
        if max_score < score:
            max_score = score
print(max_score)

Submission status: Accepted

Solution code:
import copy

def insert_to_sorted_list(vals:list, new_val):
    l = 0
    r = len(vals)
    while l < r:
        m = (l + r) // 2
        if vals[m] == new_val:
            vals.insert(m, new_val)
            return
        elif vals[m] < new_val:
            l = m + 1
        else:
            r = m
    vals.insert(l, new_val)
    return

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

sum_l = [0] * (n + 1)
sum_r = [0] * (n + 1)
for i in range(1, n+1):
    sum_l[i] += sum_l[i - 1] + v[i - 1]
    sum_r[i] += sum_r[i - 1] + v[n - i]
max_score = -10000000
left_vals = []
left_minus_n = 0
for i in range(0, n + 1):
    if i > k:
        break
    if i > 0:
        if v[i-1] < 0:
           left_minus_n += 1
        insert_to_sorted_list(left_vals, v[i-1])
    vals = copy.copy(left_vals)
    minus_n = left_minus_n
    for j in range(0, n + 1 - i):
        if i + j > k:
            break
        if j > 0:
            if v[n-j] < 0:
                minus_n += 1
            insert_to_sorted_list(vals, v[n-j])
        score = sum_l[i] + sum_r[j]
        score -= sum(vals[0:min(k - i - j, minus_n)])
        if max_score < score:
            max_score = score
print(max_score)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
V = list(map(int,input().split()))
vmax = 0
for i in range(K+1):
    for j in range(K-i+1):
        cnt = sum(V[:j])
        A = V[:j]
        n = N-(K-i-j)
        if n>=j:
            cnt += sum(V[n:])
            A += V[n:]
        else:
            cnt += sum(V[j:])
            A += V[j:]
        A = sorted(A)
        B = []
        for k in range(i):
            if k<len(A) and A[k]<0:
                B.append(k)
        for k in B:
            cnt -= A[k]
        vmax = max(vmax,cnt)
print(vmax)

Submission status: Accepted

Solution code:
def solve():
  ans = 0
  N, K = map(int, input().split())
  V = list(map(int, input().split()))
  A = V[:]*2
  for k in range(K,-1,-1): #kは操作回数
    if k>=N:
      suteru = k-N
      a = V[:]
      a.sort()
      ans = max(ans,sum(a[suteru:]))
    else:
      for i in range(k//2+1,k+1): #iは取る回数
        suteru = k-i
        for j in range(i+1):
          a = A[N-j:N+i-j]
          a.sort()
          ans = max(ans,sum(a[suteru:]))
  return ans
print(solve())

Submission status: Accepted

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

from collections import deque
V = deque(V)

import copy

ans = -10**18
for i in range(k+1):
    for j in range(k+1):
        if i+j > k:
            continue
        if i+j > n:
            continue
        V_ = copy.copy(V)
        temp = []
        for p in range(i):
            temp.append(V_.popleft())
        for q in range(j):
            temp.append(V_.pop())
        temp.sort()
        s = sum(temp)
        l = k-i-j
        for r in range(min(l, len(temp))):
            if temp[r] < 0:
                s -= temp[r]
        ans = max(ans, s)
print(ans)

Submission status: Accepted

Solution code:
def solve():
  ans = 0
  N, K = map(int, input().split())
  V = list(map(int, input().split()))
  A = V[:]*2
  for k in range(K,-1,-1): #kは操作回数
    if k>=N:
      suteru = k-N
      a = V[:]
      a.sort()
      ans = max(ans,sum(a[suteru:]))
    else:
      for i in range(k//2+1,k+1): #iは取る回数
        suteru = k-i
        for j in range(i+1):
          a = A[N-j:N+i-j]
          a.sort()
          ans = max(ans,sum(a[suteru:]))
  return ans
print(solve())

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, K = rl()
V = rl()
dp = [[[-float('inf')]*(K+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
	for j in range(N):
		for k in range(K):
			dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k])
			# if i+j >= K or i+j >= N:
			# 	print('?', i,j,k,dp[i][j][k+1], dp[i][j][k])
			# 	dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k])
			# 	continue
			ni, nj, nk = i+1, j, k+1
			if ni+nj <= N:
				dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k]+V[i])
				if V[i] < 0 and nk+1 <= K:
					dp[ni][nj][nk+1] = max(dp[ni][nj][nk+1], dp[i][j][k])
			ni, nj, nk = i, j+1, k+1
			if ni+nj <= N:
				dp[ni][nj][nk] = max(dp[ni][nj][nk], dp[i][j][k]+V[N-j-1])
				if V[N-j-1] < 0 and nk+1 <= K:
					dp[ni][nj][nk+1] = max(dp[ni][nj][nk+1], dp[i][j][k])

ans = 0
for i in range(N+1):
	for j in range(N+1):
		ans = max(ans, dp[i][j][K])
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque


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


def main():
    N, K = map(int, input().split())
    V = list(map(int, input().split()))
    ans = 0

    for i in range(min(N + 1, K+1)):  # 左から i 個取る　　
        for j in range(min(N + 1 - i, K - i+1)):  # 右からi個取る 計算量10^3
            res = K - i - j  # 残り行動回数
            agg = V[:i] + V[N  - j:]
            agg.sort(reverse=True)
            while res > 0 and agg:
                if agg[-1] < 0:
                    agg.pop()
                    res -= 1
                else:
                    break
            ans = max(sum(agg), ans)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

res = 0
r = min(n, k)
for i in range(r+1):
    for j in range(r-i+1):
        in_hand = v[:i] + v[n-j:] if i + j < n else v[:]
        in_hand.sort(reverse=True)
        for _ in range(k-len(in_hand)):
            if not in_hand or in_hand[-1] >= 0:
                break
            in_hand.pop()
        res = max(res, sum(in_hand))
print(res)

Submission status: Accepted

Solution code:
from itertools import accumulate
n, k = map(int, input().split())
vs = list(map(int, input().split()))
res = 0
for i in range(min(n,k)+1):
    for j in range(min(n-i,k-i)+1):
        res_tmp = 0
        arr = []
        if i > 0:
            arr += vs[:i]
        if j > 0:
            arr += vs[(n-j):]
        if arr != []:
            arr.sort()
            n_len = len(arr)
            for m in range(min(k-i-j,n_len)):
                if arr[m] >= 0:
                    break
                res_tmp -= arr[m]
            res_tmp += sum(arr)
        res = max(res,res_tmp)
print(res)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for i in range(k+1):
  for j in range(k+1):
    if i+j > k or i+j > n:
      continue
    t = k-(i+j)
    s = v[:i] + v[(n-j):]
    s.sort()
    u = 0
    while u < t:
      u += 1
      if len(s) < 1:
        break
      if s[0] < 0:
        s.pop(0)
      else:
        break
    ans = max(ans, sum(s))
print (ans)

Submission status: Accepted

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

ans = 0
for i in range(min(n,k)+1):
    for j in range(min(n,k)-i+1):
        l = [0]
        r = [0]
        mm = [0]
        for p in range(i):
            if v[p] > 0:
                l.append(v[p])
            else:
                heapq.heappush(mm,v[p])
        for o in range(j):
            if v[-o-1] > 0:
                r.append(v[-o-1])
            else:
                heapq.heappush(mm,v[-o-1])
        for m in range(min(k-i-j,len(mm))):
            heapq.heappop(mm)
        ans = max(ans,sum(l)+sum(r)+sum(mm))
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(min(n,k)+1):
    for j in range(min(n,k)-i+1):
        l = [0]
        r = [0]
        mm = [0]
        for p in range(i):
            if v[p] > 0:
                l.append(v[p])
            else:
                heapq.heappush(mm,v[p])
        for o in range(j):
            if v[-o-1] > 0:
                r.append(v[-o-1])
            else:
                heapq.heappush(mm,v[-o-1])
        for m in range(min(k-i-j,len(mm))):
            heapq.heappop(mm)
        # print(i,j,ans,l,r)
        ans = max(ans,sum(l)+sum(r)+sum(mm))
print(ans)
# while k and v:
#     heapq.heappush(l,deque.popleft(v))
#     k-=1
# ans = sum(l)+sum(r)
# while l:
#     print(ans)
#     deque.appendleft(v,heapq.heappop(l))
#     ans = max(ans,sum(l)+sum(r))
#     heapq.heappush(r,deque.pop(v))
#     ans = max(ans,sum(l)+sum(r))
# print(ans)

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush

N, K = map(int, input().split())
V = list(map(int, input().split()))
INF = 10**9

def h(X, cnt):
  S = sum(X)
  heapify(X)
  limit = cnt
  while cnt < K and cnt < 2*limit:
    m = heappop(X)
    if m >= 0:
      break
    S -= m
    cnt += 1
  return S

ans = 0

for i in range(1, min(N, K)+1):
  if i != N:
    for j in range(i+1):
      X = V[:i-j] + V[N-j:]
      ans = max(ans, h(X, i))
  else:
    ans = max(ans, h(V, i))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

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

    # 方針: 操作Aの回数・操作Bの回数で全探索
    ans = 0
    R = min(N,K)

    for i in range(R+1):
        for j in range(R+1-i):
            tmp = 0
            q = []# 価値が負の宝石をいれる(C)
            
            for k in range(i):
                tmp += V[k]
                if V[k] < 0:
                    q.append(V[k])
            for k in range(j):
                tmp += V[N-1-k]
                if V[N-1-k] < 0:
                    q.append(V[N-1-k])

            q.sort()
            tmp -= sum(q[:min(len(q),K-i-j)])
            ans = max(ans,tmp)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import heapq
pop = heapq.heappop
push = heapq.heappush

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

ans = 0
for i in range(min(N + 1, K + 1)):
  for j in range(min(N + 1, K + 1) - i):
    q = []
    t = 0
    for k in range(i):
      tt = V[k]
      t += tt
      push(q, tt)
    for k in range(j):
      tt = V[N - 1 - k]
      t += tt
      push(q, tt)

    for k in range(K - i - j):
      if q == []:
        break
      tt = pop(q)
      if tt >= 0:
        break
      t -= tt

    ans = max(ans, t)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 12, 2020 17:27:07 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from sys import stdin
input = stdin.readline


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

  max_ = 0
  for i in range(N+1):
    for j in range(N+1):
      res = K-(i+j)
      if i+j == 0 or i+j > N or K-(i+j) < 0:
        continue
      temp = sorted(V[:i]+V[-j if j else len(V):])
      start = 0
      for k in range(min(res, len(temp))):
        if temp[k] < 0:
          start += 1
      max_ = max(max_, sum(temp[start:]))
      # print('--', i, j, res, start, '--')
      # print(temp)
      # print(max_)
      # print()

  print(max_)


if(__name__ == '__main__'):
  main()

Submission status: Accepted

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

ans = 0
for x in range(k+1):# LeftHand
  for y in range(k-x+1):# RightHand
    temp = v[:x]+v[len(v)-y:]
    if x+y >= n:
      temp = v
    temp1 = []
    temp2 = []
    for i in temp:
      if i >= 0:
        temp1.append(i)
      else:
        temp2.append(i)

    temp2.sort()
    ans = max(ans, sum(temp1) + sum(temp2[k-x-y:]))
print(ans)

Submission status: Accepted

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

ans = 0
for x in range(k+1):# LeftHand
  for y in range(k-x+1):# RightHand
    temp1 = []
    temp2 = []
    if x+y >= n:
      for i in v:
        if i >= 0:
          temp1.append(i)
        else:
          temp2.append(i)
    else:
      for i in v[:x]:
        if i >= 0:
          temp1.append(i)
        else:
          temp2.append(i)
      for i in v[len(v)-y:]:
        if i >= 0:
          temp1.append(i)
        else:
          temp2.append(i)
    temp2.sort()
    ans = max(ans, sum(temp1) + sum(temp2[k-x-y:]))
print(ans)

Submission status: Accepted

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

max_value = -10**9
for kL in range(0, K+1):
    for kR in range(0, K+1):
        if kL + kR > min(N, K):
            continue
        vL = V[:kL]
        vR = []
        if kR:
            vR = V[-kR:]
        hand = list(sorted(vL + vR, reverse=True))
        rest = K - (kL + kR)
        for kD in range(rest):
            if len(hand) == 0:
                break
            if hand[-1] < 0:
                hand.pop()
            else:
                break
        value = sum(hand[:K])
        if value > max_value:
            max_value = value
print(max_value)

Submission status: Accepted

Solution code:
def main():
    n, k = list(map(int, input().split()))
    V = list(map(int, input().split()))
    ans = -1
    for i in range(c := min(n, k) + 1):
        for j in range(c - i):
            A = V[:i] + V[-j:] if j != 0 else V[:i]
            A.sort(reverse = True)
            r = k - (i + j)
            for _ in range(r):
                if len(A) == 0:
                    break
                if (a := A.pop()) >= 0:
                    A.append(a)
                    break
            ans = max(ans, sum(A))
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def readinput():
    n,k=map(int,input().split())
    v=list(map(int,input().split()))
    return n,k,v

def main(n,k,v):
    ruisekiL=[0]*(n+1)
    ruisekiR=[0]*(n+1)
    for i in range(1,n+1):
        ruisekiL[i]=ruisekiL[i-1]+v[i-1]
        ruisekiR[i]=ruisekiR[i-1]+v[n-i]
    vv=[]
    for i in range(n):
        vv.append((i+1,v[i]))
    vv.sort(key=lambda x:x[1])
    #print(vv)

    maxown=-10**7
    for kk in range(k+1):
        if n<kk:
            own=ruisekiL[n]
            m=0
            while m<n and vv[m][1]<0: 
                own-=vv[i][1]
                m+=1
            #print(own)
            maxown=max(maxown,own)
        else:
            for l in range(kk//2+1):
                for i in range(kk-l+1):
                    j=kk-i-l
                    jj=n-j+1
                    own=ruisekiL[i]+ruisekiR[j]
                    #print(i,j,own)
                    m=0
                    mcnt=0
                    while(mcnt<l):
                        if i<vv[m][0] and vv[m][0]<jj:
                            m+=1
                            continue
                        #print(i,jj,vv[m])
                        own-=vv[m][1]
                        mcnt+=1
                        m+=1
                    #print(own)
                    maxown=max(own,maxown)
    return maxown

def main2(n,k,v):
    ruisekiL=[0]*(n+1)
    ruisekiR=[0]*(n+1)
    for i in range(1,n+1):
        ruisekiL[i]=ruisekiL[i-1]+v[i-1]
        ruisekiR[i]=ruisekiR[i-1]+v[n-i]
    vv=[]
    for i in range(n):
        vv.append((i+1,v[i]))
    vv.sort(key=lambda x:x[1])
    #print(vv)

    maxown=-10**7
    for i in range(n+1):
        for j in range(n+1):
            if i+j>k or i+j>n:
                break
            jj=n-j+1
            own=ruisekiL[i]+ruisekiR[j]
            #print(i,j,own)
            l=min(i+j,k-i-j)
            m=0
            mcnt=0
            while(mcnt<l):
                if i<vv[m][0] and vv[m][0]<jj:
                    m+=1
                    continue
                if vv[m][1]>=0:
                    break
                own-=vv[m][1]
                mcnt+=1
                m+=1
            #print(own)
            maxown=max(own,maxown)
    return maxown

if __name__=='__main__':
    n,k,v=readinput()
    ans=main2(n,k,v)
    print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
V = [0]*N
*V, = map(int, input().split())

ans = []
for i in range(N+1):
    for j in range(N+1):
        if i+j > min(N, K): continue
        out = V[:i] + V[N-j:]
        out.sort()
        r = 0
        while i+j+r < K and r < len(out):
            if out[r] < 0: r += 1
            else: break
        ans.append(sum(out[r:]))

print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
n, k = map(int, input().split())
v = list(map(int, input().split()))
ans = 0
for i in range(1, min(n, k+1)):
    vv = deque(v)
    q = deque(v[:i])
    for _ in range(i+1):
        tmp = list(q)
        tmp.sort()
        rem = k-i
        s = sum(tmp)
        for j in tmp:
            if rem==0 or j>=0:
                break
            s -= j
            rem -= 1
        ans = max(ans, s)
        q.pop()
        q.appendleft(vv.pop())
if k>=n:
    v.sort()
    rem = k-n
    s = sum(v)
    for j in v:
        if rem==0 or j>=0:
            break
        s -= j
        rem -= 1
    ans = max(ans, s)
print(ans)

Submission status: Accepted

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

for i in range(1, K + 1):#i個以下取り出し、K - i個以下戻す＃１００
  nownow = 0
  for p in range(i + 1):#[0:i] から [N - i:N]まで取り出さないところを選べる#100
    #[p:p + N - i]を取り出さない
    if i < N:
      now = sorted(V[:p] + V[p + N - i:])
    else:
      now = V
    #print(now, i, p)
    index = bisect.bisect_right(now, 0)
    #index個の負の数がある。
    if K - i >= index:
      nownow = sum(now[index:])
    else:
      nownow = sum(now[K - i:])
    ans = max(ans, nownow)
    #print(now, nownow, ans)

print(ans)

Submission status: Accepted

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

# 1<=N<=50
# 1<=K<=100
# 10**8になってしまうので、全探索は無理そう？？？？


# CDは最後に持ってくれば良い。途中でやる必要はない
# A,Bをそれぞれ何回やるか決めれば、価値はわかるのでは。ただし、A,Bの数を合わせてKにならない場合もあり、その場合はリリースしないといけない
ans = 0

for i in range(K + 1):
    for j in range(K - i + 1):
        # 抜き出す動作がNを超えてしまった時、入れて取り出すという作業によって暇つぶしをする必要がある。
        # print(i, j, release_count)
        # i + j + relase_count = K
        for k in range(K - i - j + 1):
            if i + j < N:
                left_nums = values[0:i].copy()
                right_nums = values[N - j:N].copy()
                nums = sorted(left_nums + right_nums)
                ans = max(ans, sum(nums[k:]))
            elif i + j == N:
                nums = sorted(values.copy())
                ans = max(ans, sum(nums[k:]))
            else:
                if k < N - (i + j):
                    continue
                nums = sorted(values.copy())
                ans = max(ans, sum(nums[k - (N - (i + j)):]))


print(ans)