logo AlgoBeat OnlineJudge
登录 注册

#200590. [USACO09MAR] 结算日 Payback B

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

题目描述

“不放债不借债”,贝西多么希望自己可以遵循这个忠告。她已经和她的 个朋友有了债务关系,或者借债了,或者放债了。她的 个朋友依次标号为

结算日终于来临了。她知道,朋友欠她的钱比她欠朋友的钱多。她的朋友们分布在一条直线上,第 头奶牛站的位置距离谷仓 米。贝西打算沿着这条直线行走,从欠她钱的奶牛手里收钱回来,并且还钱给她欠钱的奶牛。

当她沿直线移动的时候,她可以要求任何欠她钱的奶牛还全部的钱。当她有足够的钱可以还清她的某个债,就可以把钱给对应的奶牛还清她的债。奶牛 欠贝西 ,负数表示贝西欠奶牛 钱。

贝西从谷仓出发,位置为 ,初始贝西没有钱。贝西收回她的所有借债,并且还清她的欠债所需行走的最短距离是多少?

注意:她必须在最后一头奶牛所在的位置,完成她的行走。

输入格式

第一行,一个整数

接下来第 行,第 行包含一个整数

输出格式

一个整数,贝西收回借债并且还清欠债,所需要行走的最短距离(单位为米)。

样例

样例输入 1

5
100
-200
250
-200
200

样例输出 1

9

数据范围与提示

输入解释:

头奶牛欠贝西钱;她欠 头奶牛钱。当她完成结算,她将有 元。

输出解释:

谷仓  100  -200  250 -200  200
 |     |     |    |    |    |
 ***>**+**>*****>**+
                   *            < 贝西有 350 元
             -**<***
             *                  < 贝西有 150 元
             ***>****>****>**+
                             *  < 贝西有 350 元
                       -**<***
                       *     
                       ***>***  < 贝西结束她的行走,有 150 元