Building

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 512M

Authors:
Problem types

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

Constraints

1D<N105

1X,Y,hi106

Subtask 1 [20%]

1D<N100

Subtask 2 [80%]

No additional constraints.

Input Specification

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

The second line will contain N space-separated integers, h1,h2,,hN, respectively.

Output Specification

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

Sample Input

Copy
5 3 1 2
1 2 5 4 3

Sample Output

Copy
4

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 and go to the rightmost building higher than the current building....."? It says "leftmost" instead of "rightmost."