#P18023. Restricted Removals
Restricted Removals
Restricted Removals
Alice 和 Bob 有一个长度为 的整数数组 。
Alice 先选择一个长度为 、恰好含有 个 1 的二进制串 ,并在整场游戏中固定它。
Bob 的初始得分为 。他可以进行任意次操作,也可以不操作。每次操作选择当前数组中的一个下标 ,要求 ,将当前的 加入得分,再删除这个元素。删除后数组长度减一,剩余元素重新从 开始编号。
特别注意, 作用于当前下标位置,而不是跟随原来的元素移动。原来被保护的元素在其他元素删除后,可能移到可删除的位置,反之亦然。
另外,Bob 各次操作选择的下标必须非递增。如果依次选择 ,必须满足
允许多次选择相同下标。Alice 希望 Bob 的最终得分尽可能小,Bob 希望得分尽可能大。求双方都采取最优策略时 Bob 的最终得分。
输入格式
第一行一个整数 。每组数据第一行两个整数 ,第二行 个整数 。
输出格式
每组数据输出一行一个整数,表示 Bob 的最终得分。
数据范围
,,,。
所有测试用例的 之和不超过 , 之和不超过 。
样例 1
输入
6
5 2
4 -1 7 -3 2
4 0
-5 -2 -1 -3
4 4
2 -7 5 1
1 0
-1
2 1
0 1
3 1
1 -1 1
输出
7
0
0
0
1
1