SAC '22 Code Challenge 1 P5 - That Wall

View as PDF

Submit solution

Points: 12
Time limit: 1.0s
Java 2.0s
Memory limit: 256M

Problem type

You are the urban designer for a city with N piles of candy that have different heights, H_i, and are tasked with building a wall to hide them.

You will be penalized for your inaccuracy in building a wall to hide each of these piles, C_i.

Specifically, you will be fined C_i \times |S_i - H_i|, where S_i is the height that you build the final wall for the i^\text{th} pile of candy. (Showing the candy or hiding scenic scenery is equally bad.)

Each pillar of the wall has an initial height of 0.

Additionally, you can only change the height of a given wall up to K times along its length (i.e., set the heights of all the pillars of the wall from [i, N] to a height).

Find the minimum cost for this wall.

Input Specification

The first line will contain N (1 \le N \le 150) and K (1 \le K \le 150), the number of piles of candy that need to be covered and the number of changes you can make.

The second line will contain N space-separated integers, C_i (1 \le C_i \le 1\,000\,000), the cost for each difference in height between the piles of candy and wall.

The third line will contain N space-separated integers, H_i (0 \le H_i \le 1\,000\,000), the optimal height for this pillar.

Output Specification

Output the minimum cost to be fined for building this wall.

Sample Input

5 1
1 10 3 5 2
1 10 4 3 2

Sample Output


Explanation for Sample Output

Note that there are multiple valid solutions yielding the minimum cost.

Here is one valid solution:

Spend the first and only move to set the height for all pillars from [2, N] to 9, resulting in a total cost of 70.


There are no comments at the moment.