TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3569
  • 問題
  • P3569葡萄酒交易
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    一条笔直公路上分布着n(2<=n<=300000)个村庄,从左往右编号1到n,每个村庄要么需要酒,要么需要酒。

    设第i个村庄对葡萄酒的需求为Ai(-1000<=Ai<=1000),其中Ai>0表示该村需要买酒,Ai<0表示该村需要卖酒。所有村庄供需平衡,即所有Ai之和等于0

    把k升葡萄酒从一个村庄运到相邻村庄需要k块钱的运费,请你计算最少需要多少运费就可以满足所有村庄对酒的需求。结果保证在64位整数范围以内。

    入力形式

    第一行,一个整数n,表示村庄的数量
    第二行,n个空格间隔的整数,依次表示1到n号村庄对酒的需求

    出力形式

    一行,一个整数,表示最小的费用

    サンプル入力

    样例输入1:
    5
    5 -4 1 -3 1

    样例输入2:
    6
    -1000 -1000 -1000 1000 1000 1000

    サンプル出力

    样例输出1:
    9

    样例输出2:
    9000

    ヒント

    样例1说明:
    从2号村庄将4升酒运往村庄1,花费4
    从4号村庄将1升酒运往村庄3,花费1
    从4号村庄将1升酒运往村庄1,花费3
    从4号村庄将1升酒运往村庄5,花费1
    总花费为9


    ソース  改编自uva11054