#P18797. [Omi2023] 机器人调酒师马丁

[Omi2023] 机器人调酒师马丁

[Omi2023] 机器人调酒师马丁

题目描述

吧台前有 NN 位顾客,位置依次为 1,2,…,N1,2,\ldots,N。为第 ii 位顾客制作饮料需要消耗 aia_i 点能量。

马丁会把全部工具放在吧台上的某个位置 jj。当他为位置 ii 的顾客服务时,制作和运输这杯饮料的总能量消耗为

ai+∣i−j∣.a_i+|i-j|.

马丁今天恰好选择 KK 位顾客服务。每位被选中的顾客只服务一次,能量消耗分别按上式计算后相加。所选顾客的位置不必连续。

对于工具的每个可能位置 j=1,2,…,Nj=1,2,\ldots,N,求恰好服务 KK 位顾客所需的最小总能量。

不同工具位置可以选择不同的 KK 位顾客。

输入格式

第一行包含两个整数 N,KN,K。

第二行包含 NN 个整数 a1,a2,…,aNa_1,a_2,\ldots,a_N。

输出格式

输出 NN 行,每行一个整数。第 jj 行表示工具位于位置 jj 时的最小总能量。

答案可能超过 32 位有符号整数的范围。

样例输入

7 3
3 2 4 1 4 5 1

样例输出

10
9
9
9
9
10
11

样例说明

工具位于位置 11 时,可以服务位置 1,2,41,2,4 的顾客,能量为 3+3+4=103+3+4=10。

工具位于位置 55 时,可以服务位置 4,5,74,5,7 的顾客,能量为 2+4+3=92+4+3=9。

数据范围与分组

  • 1≤N≤1051\le N\le10^5;
  • 1≤K≤N1\le K\le N;
  • 1≤ai≤1051\le a_i\le10^5。
分值 额外限制
16 所有 aia_i 相同
14 K=NK=N
21 K=1K=1
10 N≤1000N\le1000
39 无额外限制