A262.奶牛渡河

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

FarmerJohnFarmer John以及他的 N(1N2,500)N(1 \le N \le 2,500) 头奶牛打算过一条河,但他们所有的渡河工具,仅仅是一个木筏。

由于奶牛不会划船,在整个渡河过程中,FJFJ 必须始终在木筏上。在这个基础上,木筏上的奶牛数目每增加 11FJFJ 把木筏划到对岸就得花更多的时间。

FJFJ 一个人坐在木筏上,他把木筏划到对岸需要MM(1M1000)1 \le M \le 1000)分钟。当木筏搭载的奶牛数目从 i1i-1 增加到ii时,FJFJ 得多花 MiM_i(1Mi1000)1 \le M_i \le 1000) 分钟才能把木筏划过河(也就是说,船上有 11 头奶牛时,FJFJ得花 M+M1M+M_1 分钟渡河;船上有 22 头奶牛时,时间就变成 M+M1+M2M+M_1+M_2 分钟。后面 的依此类推)。那么,FJFJ最少要花多少时间,才能把所有奶牛带到对岸呢?当然,这个时间得包括 FJFJ 一个人把木筏从对岸划回来接下一批的奶牛的时间。

输入格式

11 行: 22个用空格隔开的整数:NNMM

2..N+12..N+1 行: 第 i+1i+111 个整数:MiM_i

输出格式

11 行: 输出 11 个整数,为 FJFJ 把所有奶牛都载过河所需的最少时间。

输入输出样例

  • 输入#1

    5 10
    3
    4
    6
    100
    1

    输出#1

    50
首页