#P11141. [NOISG 2021 Finals] Pond
[NOISG 2021 Finals] Pond
题目背景
乌龟 Syrup 经常在他家旁边的池塘里游泳。这个池塘是由很久以前的冰川运动形成的,呈狭长直线状,水面平静,适合双向游泳。
题目描述
今天,Syrup 像往常一样游泳时,发现了一簇绿点——正在萌发的藻类孢子。经过暴雨冲刷,富含营养的土壤流入池塘,为藻类提供了大量养分,导致它们以惊人的速度生长。如果不加以控制,这些藻类会遮挡阳光,破坏水下生态平衡。
幸运的是,Syrup 有一个简单有效的解决方案——吃掉它们。他已经识别出池塘中 个土壤流失点,标号为 到 ,并记下了它们之间的距离 (第 点到第 点之间的距离为 )。目前,Syrup 位于第 个点,并从这里开始消灭藻类。
池塘中的每个点初始有 条藻类,并且每秒会增加 条藻类,直到 Syrup 到达该点并吃掉所有藻类。Syrup 需要选择一个方向,沿着池塘游泳,并依次吃掉遇到的所有藻类。为了让藻类不至于变得太难吃,他希望尽可能减少吃下的藻类总数。
你的任务是计算 Syrup 吃下的最少藻类总数。
输入格式
- 第一行包含两个整数 和 ,分别表示池塘中的土壤流失点数量和 Syrup 的起始位置。
- 第二行包含 个整数 ,表示相邻流失点之间的距离。
输出格式
输出一个整数,表示 Syrup 吃下的最少藻类总数。
输入输出样例 #1
输入 #1
7 3
5 2 4 2 2 5
输出 #1
86
输入输出样例 #2
输入 #2
9 5
4 3 2 1 1 3 6 10
输出 #2
129
输入输出样例 #3
输入 #3
6 4
1 1 1 1 1
输出 #3
21
说明/提示
【样例解释】
- 对于样例 ,最优路径是按顺序访问点 ,总共吃掉 条藻类。
- 对于样例 ,最优路径是按顺序访问点 ,总共吃掉 条藻类。
- 对于样例 ,最优路径是按顺序访问点 ,总共吃掉 条藻类。
【数据范围】
| 子任务编号 | 分值 | 额外限制条件 |
|---|---|---|
| 且 (对所有 满足 ) | ||
| 无额外限制 |