A186074.加倍时刻

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小林参加一场有 nn 轮的积分挑战。比赛开始时,他的累计积分为 00。第 ii 轮结束时,他的累计积分增加 aia_i。其中 aia_i 可以为正数、负数或 00,累计积分也允许为负数。

小林有一张加倍卡,可以选择在某一轮的得分加入累计积分之后,立即将当时的累计积分乘以 22。后续各轮仍然只增加该轮原本的得分。

加倍卡最多使用一次,也可以完全不使用。最后一轮结束后也可以使用。

请你求出小林在全部轮次结束并完成所选操作后,能够获得的最大累计积分。

输入格式

第一行输入一个整数 nn,表示比赛轮数。

第二行输入 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示每轮得分。

输出格式

输出一个整数,表示最终累计积分的最大值。

输入输出样例

  • 输入#1

    5
    4 -6 5 2 -3

    输出#1

    7
  • 输入#2

    3
    -2 -1 -4

    输出#2

    -7

说明/提示

样例解释 1

前四轮的累计积分为 55。此时使用加倍卡,积分变为 1010;第五轮扣除 33 分,最终得到 77 分,这是能够获得的最大值。

样例解释 2

任何一轮结束时的累计积分都为负数。最优选择是不使用加倍卡,最终积分为 −7-7。

数据范围

对于所有测试数据,保证:

  • 1≤n≤2×1051\le n\le2\times10^5;
  • −109≤ai≤109-10^9\le a_i\le10^9。

输入解题思路,AI测评打分。不知道怎么写?

首页