C - Watering the Flower Bed Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、庭に一列に並んだ N 個の花壇を管理しています。花壇には左から順に 1, 2, \ldots, N の番号が付いており、花壇 i（1 \leq i \leq N）の土の水分量は現在 A_i です。

明日は来客があるため、高橋君はすべての花壇の水分量を目標値 T 以上にして、花を美しく咲かせたいと考えています。水分量が T を超えても構いません。

高橋君は以下の操作を好きな回数（0 回でもよい）行うことができます。

  • 操作： 1 \leq l \leq N - K + 1 を満たす整数 l を 1 つ選び、花壇 l から花壇 l + K - 1 までの連続する K 個の花壇にスプリンクラーで水をまく。これにより、それら K 個の花壇の水分量がそれぞれ 1 増加する。この操作 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
  • 1 行目には、花壇の個数 N、スプリンクラーで同時に水をまく花壇の個数 K、目標水分量 T、1 回の操作あたりの水道代 C（円）が、スペース区切りで与えられる。
  • 2 行目には、各花壇の初期水分量 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

すべての花壇の水分量を T 以上にするために必要な水道代の合計の最小値（円）を整数で 1 行に出力せよ。

入力例 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

Score : 366 pts

Problem Statement

Takahashi manages N flower beds arranged in a row in his garden. The flower beds are numbered 1, 2, \ldots, N from left to right, and the current moisture level of the soil in flower bed i (1 \leq i \leq N) is A_i.

Since he will have guests tomorrow, Takahashi wants to make all flower beds have a moisture level of at least the target value T so that the flowers bloom beautifully. It is fine if the moisture level exceeds T.

Takahashi can perform the following operation any number of times (possibly 0 times):

  • Operation: Choose an integer l satisfying 1 \leq l \leq N - K + 1, and water the K consecutive flower beds from flower bed l to flower bed l + K - 1 using a sprinkler. This increases the moisture level of each of those K flower beds by 1. Each operation costs C yen in water charges.

The value of l chosen in each operation is arbitrary, and the same value of l may be chosen in different operations.

Find the minimum total water cost (in yen) required to make the moisture level of all flower beds at least T.

Constraints

  • 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)
  • All inputs are integers
  • It is guaranteed that the answer is at most 2^{63} - 1 (i.e., it fits in a signed 64-bit integer type)

Input

N K T C
A_1 A_2 \cdots A_N
  • The first line contains the number of flower beds N, the number of flower beds watered simultaneously by the sprinkler K, the target moisture level T, and the water cost per operation C (yen), separated by spaces.
  • The second line contains the initial moisture levels of each flower bed A_1, A_2, \ldots, A_N, separated by spaces.

Output

Print the minimum total water cost (in yen) required to make the moisture level of all flower beds at least T, as an integer on a single line.

Sample Input 1

5 3 10 100
8 7 9 12 11

Sample Output 1

300

Sample Input 2

8 2 15 50
12 10 14 13 11 15 9 16

Sample Output 2

750

Sample Input 3

10 4 20 1000
18 15 12 19 17 14 16 20 13 21

Sample Output 3

15000