Electric poles - MarisaOJ: Marisa Online Judge

A company is responsible for constructing

n

$n$ electric poles for a city. The

i

$i$ -th electric pole has a height of

h_{i}

$h_i$ . In order to maintain urban aesthetics, the city has imposed a regulation that the company will be charged a cost based on the height difference between two adjacent poles

i

$i$ and

i + 1

$i + 1$ , given by

c_{i} \times | h_{i} - h_{i + 1} |

$c_i \times |h_i - h_{i+1}|$ . Additionally, the height difference between two neighboring poles must not exceed

d

$d$ . To meet these requirements, the company can increase the height of certain poles. However, increasing the height of the

i

$i$ -th pole by

x

$x$ units will incur a cost of

x^{2}

$x^2$ . Find the minimum cost required to comply with the city's regulations. ### Input - The first line contains two integer

n, d

$n,d$ . - The second line contains

n - 1

$n - 1$ integers

c_{i}

$c_i$ with

1 \leq i \leq n - 1

$1 \le i \le n - 1$ . - The third line contain

n

$n$ integers

h_{i}

$h_i$ . ### Output - Print an integer, the minimum cost. ### Constraints -

1 \leq n, d, h_{i} \leq 5000

$1 \le n, d, h_i \le 5000$ . -

1 \leq c_{i} \leq 10^{4}

$1 \le c_i \le 10^4$ . ### Example Input:

54222223514

$5 4 2 2 2 2 2 3 5 1 4$

Output:

15

$15$

Monotonic queue
	Nearest position
	Subarray minimum
	Peak Product
	Histogram
	Maximum subsequence value
	Deleting digits
	Electric poles
	Planting flowers
	Ring road
	Prefix minimum
	Knee surgery

Topic

Data structure

Dynamic Programming

Rating

1700

Solution (1)

Solution