logo AlgoBeat OnlineJudge
登录 注册

#216335. [蓝桥杯 2026 省 C] 回收处理

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

在自动化工厂的水线上,依次排列着 个部件。每个部件都标有一个价格 :若执行回收,该标价即为收益;若执行处理,该标价则计为成本。

作为厂区负责人,小蓝的任务是从这 个部件中挑选出两批特定组别:

  1. 回收组:挑选出恰好 个部件进行回收,总收益记为
  2. 处理组:挑选出恰好 个部件进行处理,总成本记为

由于水线是不可逆的单向传送,挑选过程必须遵守严格的先后顺序:任何一个被回收的部件,其原始位置都必须早于所有被处理的部件(即若把回收部件的下标记为 ,处理部件的下标记为 ,则必须满足 )。

在满足上述顺序的前提下,水线上剩下的 个部件将被直接弃置,不产生任何收益或成本。

现在,小蓝希望通过合理的方案,使得回收的总收益减去处理的总成本()尽可能大。对此,请你计算出这个差值的最大可能结果。

输入格式

第一行包含一个整数 ,表示每组选取的部件数量。

第二行包含 个整数 ,表示水线上从左到右每个部件的标价。

给定的网络可能包含重边或自环。

输出格式

输出一个整数,表示在满足所有约束的前提下, 的最大可能值。

样例

样例输入 1

2
1 10 5 1 2 1

样例输出 1

13

数据范围与提示

【样例说明】

最优的方案为:回收第 个部件,处理第 个部件,此时

【评测用例规模与约定】

对于 的评测用例,

对于所有评测用例,