A186074.加倍时刻
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
小林参加一场有 n 轮的积分挑战。比赛开始时,他的累计积分为 0。第 i 轮结束时,他的累计积分增加 ai。其中 ai 可以为正数、负数或 0,累计积分也允许为负数。
小林有一张加倍卡,可以选择在某一轮的得分加入累计积分之后,立即将当时的累计积分乘以 2。后续各轮仍然只增加该轮原本的得分。
加倍卡最多使用一次,也可以完全不使用。最后一轮结束后也可以使用。
请你求出小林在全部轮次结束并完成所选操作后,能够获得的最大累计积分。
输入格式
第一行输入一个整数 n,表示比赛轮数。
第二行输入 n 个整数 a1,a2,…,an,表示每轮得分。
输出格式
输出一个整数,表示最终累计积分的最大值。
输入输出样例
输入#1
5 4 -6 5 2 -3
输出#1
7
输入#2
3 -2 -1 -4
输出#2
-7
说明/提示
样例解释 1
前四轮的累计积分为 5。此时使用加倍卡,积分变为 10;第五轮扣除 3 分,最终得到 7 分,这是能够获得的最大值。
样例解释 2
任何一轮结束时的累计积分都为负数。最优选择是不使用加倍卡,最终积分为 −7。
数据范围
对于所有测试数据,保证:
- 1≤n≤2×105;
- −109≤ai≤109。
输入解题思路,AI测评打分。不知道怎么写?