分数: 366 分
问题陈述
高桥管理 N 他的花园里排列着一排花坛。花坛都有编号 1, 2, \ldots, N 从左到右,以及花坛土壤当前的湿度水平 i (1 \leq i \leq N)是 A_i.
由于明天会有客人,高桥希望所有花坛的湿度至少达到目标值 T 让花朵绽放美丽。如果水分含量超过就可以了 T.
Takahashi 可以执行以下操作任意次数(可能 0 次):
- 操作: 选择一个整数 l 满意 1 \leq l \leq N - K + 1,然后浇水 K 花坛连续花坛 l 到花坛 l + K - 1 使用洒水器。这会增加每一个的水分含量 K 花坛 1。每次操作费用 C 日元水费。
的值 l 在每个操作中选择是任意的,并且相同的值 在不同的操作中可以选择 l 。
求使所有花坛的湿度至少所需的最低总水成本(日元) T.
约束
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq T \leq 10^9
- 1 \leq C \leq 10^9
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数
- 保证答案最多是 2^{63} - 1 (即,它适合签名的 64-位整数类型)
输入
N K T C A_1 A_2 \cdots A_N
- 第一行包含花坛数量 N,喷头同时浇水的花坛数量 K,目标湿度水平 T,以及每次操作的水成本 C (日元),以空格分隔。
- 第二行包含每个花坛的初始湿度水平 A_1, A_2, \ldots, A_N,用空格分隔。
输出
打印使所有花坛的湿度至少所需的最低总水成本(日元) T,作为单行上的整数。
示例输入 1
5 3 10 100 8 7 9 12 11
示例输出 1
300
示例输入 2
8 2 15 50 12 10 14 13 11 15 9 16
示例输出 2
750
示例输入 3
10 4 20 1000 18 15 12 19 17 14 16 20 13 21
示例输出 3
15000