Building

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 512M

Authors:

Tommypang, Tommy_Shan

Problem types

There are $N$ ~N~ buildings in the city Tommy is living at, and the $i^\text{th}$ ~i^\text{th}~ building has a height of $h_i$ ~h_i~. Initially, Tommy is at building $1$ ~1~, and he wants to go to building $N$ ~N~. He can spend $X$ ~X~ and go to the leftmost building higher than the current building, where the distance between the two buildings is at most $D$ ~D~ (i.e., if Tommy is currently at building $i$ ~i~, he can go to building $j$ ~j~ $(j > i)$ ~(j > i)~, which is the first building on the right of $i^\text{th}$ ~i^\text{th}~ building higher than $h_i$ ~h_i~ and $j-i \le D$ ~j-i \le D~ with a cost of $X$ ~X~). Also, if Tommy is at the $i^\text{th}$ ~i^\text{th}~ building, he can go to the $(i+1)^\text{th}$ ~(i+1)^\text{th}~ building or the $(i+2)^\text{th}$ ~(i+2)^\text{th}~ building with a cost of $Y$ ~Y~ if these buildings exist. Help Tommy find the minimum cost to go to building $N$ ~N~.

Constraints

$1 \le D < N \le 10^5$ ~1 \le D < N \le 10^5~

$1 \le X, Y, h_i \le 10^6$ ~1 \le X, Y, h_i \le 10^6~

Subtask 1 [20%]

$1 \le D < N \le 100$ ~1 \le D < N \le 100~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line will contain four space-separated integers, $N$ ~N~, $D$ ~D~, $X$ ~X~, and $Y$ ~Y~.

The second line will contain $N$ ~N~ space-separated integers, $h_1, h_2, \dots, h_N$ ~h_1, h_2, \dots, h_N~, respectively.

Output Specification

Output the minimum cost for Tommy to go to building $N$ ~N~.

Sample Input

5 3 1 2
1 2 5 4 3

Sample Output

Comments

0

Genius3435 commented on April 2, 2023, 1:15 p.m.

The problem statement should say

go to the leftmost building to his right, that is higher than the current building

0

Asviño commented on Sept. 4, 2022, 3:35 p.m. ← edited →

Shouldn't the problem statement say "He can spend $X$ ~X~ and go to the rightmost building higher than the current building....."? It says "leftmost" instead of "rightmost."