金苹果岛 - 代码能力最大化问题

金苹果岛 - 代码能力最大化问题

题目描述

代码勇者来到了金苹果岛上，金苹果岛上有两种苹果：随处可见的红苹果与稀有美味的金苹果。

勇者的'初始代码能力为 1'，他每吃下一个红苹果，代码能力就会得到一定程度的提升（每个红苹果带来的提升可能是不同的，甚至也可能是负的）；他每吃下一个金苹果，代码能力就会直接'翻倍'（每个金苹果的效果都是完全相同的）。

岛上的苹果仙子用 n 个红苹果和 m 个金苹果招待了勇者，勇者必须吃光所有苹果。勇者必须按照仙子'规定的顺序'吃红苹果，但是他可以'自由安排'什么时候吃金苹果（可以在吃'任意'一个红苹果之前或之后吃'若干'个金苹果）。

求勇者在离开金苹果岛的时候的代码能力的最大值。

输入格式

第一行输入两个正整数 n（n≤10^5）和 m（ m≤10）。

第二行输入 n 个整数 a_i（|a_i|≤10）。

输出格式

输出一个整数，表示勇者在离开金苹果岛的时候的代码能力的最大值。

样例 #1

样例输入 #1

6 2
1 -2 3 1 -6 5

样例输出 #1

15

样例 #2

样例输入 #2

8 3
5 -3 -8 2 4 -11 9 1

样例输出 #2

42

提示

样例1解释

勇者吃掉红苹果 1,-2,3,1，代码能力变为 4；

勇者吃掉 2 颗金苹果，代码能力变为 16；

勇者吃掉红苹果 -6,5，代码能力变为 15。

这是勇者的最优方案。

子任务

对于 10% 的数据，a_i≥0；

对于 30% 的数据，m=0；

对于 70% 的数据，m=1；

对于 100% 的数据，n≤10^5,m≤10,|a_i|≤10。

代码

n, m = map(int, input().split())
apples = list(map(int, input().split()))

# 计算红苹果的总和
red_sum = sum(apples)

# 如果没有金苹果，直接返回红苹果的总和
if m == 0:
    print(red_sum)
    exit()

# 找到红苹果中的最小值
min_red = min(apples)

# 如果红苹果的总和小于等于0，那么直接返回红苹果的总和
if red_sum <= 0:
    print(red_sum)
    exit()

# 如果红苹果的总和大于0，那么就要考虑金苹果的影响
# 如果红苹果中的最小值大于等于0，那么直接返回红苹果的总和加上m个金苹果的效果
if min_red >= 0:
    print(red_sum + m * red_sum)
    exit()

# 如果红苹果中的最小值小于0，那么就要考虑金苹果的影响
# 先计算红苹果的总和加上m个金苹果的效果
result = red_sum + m * red_sum

# 从左往右遍历红苹果，如果遇到一个负数，就尝试用金苹果来抵消
for i in range(n):
    if apples[i] < 0:
        # 如果金苹果的数量大于等于当前红苹果的绝对值，那么可以用金苹果来抵消
        if m >= abs(apples[i]):
            # 用金苹果来抵消红苹果的效果
            result += apples[i]
            # 金苹果的数量减少
            m -= abs(apples[i])
        # 如果金苹果的数量小于当前红苹果的绝对值，那么只能用金苹果来抵消一部分
        else:
            # 用金苹果来抵消红苹果的效果
            result += m * apples[i]
            # 金苹果的数量减少
            m = 0

print(result)