luogu#P9207. 灭罪「正直者之死」
灭罪「正直者之死」
题目背景
正直的人,坚强不屈的人,刚正不阿的人。
大约这样的人会处处吃亏吧,不过这样的观点大约是从欺骗者的眼光里看到的。正直的人,即使是在死后,也是最为人尊敬的吧。
题目描述
有一台计算器,使用 位的带符号整型来对数字进行存储。也就是说,一个变量能够表示的范围是 。现在我们希望使用该计算器计算一系列数 的和。计算的伪代码如下:
由于奇怪的特性,如果两个变量在相加时得到的结果在 之外,即发生了溢出,那么这台计算器就会卡死,再也无法进行计算了。
为了防止这样的事情发生,一个变通的方法是更改 的排列顺序。容易发现这样不会改变计算出的和的值。
不过,可能不存在一种方案,使得计算出这 个数并且计算机不爆炸。但我们还是希望,计算出尽量多的数字的和。
输入格式
第一行有两个整数 ,分别表示元素个数和整型位数。
第二行有 个整数 。
输出格式
共一行一个整数,表示最多能将多少个数字计算出和。
3 3
1 2 3
2
10 4
-3 5 6 -4 5 3 -4 1 -1 0
9
提示
样例解释
- 对于样例 ,一种最优的方案是 ,这样可以在计算出前两个数的情况下不溢出。
- 对于样例 ,一种最优的方案是 ,这样可以在计算前 个数的情况下不溢出。
数据范围及约定
对于全部数据,保证 ,,。