CEOI '17 P4 - Building Bridges

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.4s
Memory limit: 128M

Problem type

A wide river has n pillars of possibly different heights standing out of the water. They are arranged in a straight line from one bank to the other. We would like to build a bridge that uses the pillars as support. To achieve this we will select a subset of pillars and connect their tops into sections of a bridge. The subset has to include the first and the last pillar.

The cost of building a bridge section between pillars i and j is (h_i - h_j)^2 as we want to avoid uneven sections, where h_i is the height of the pillar i. Additionally, we will also have to remove all the pillars that are not part of the bridge, because they obstruct the river traffic. The cost of removing the i^{th} pillar is equal to w_i. This cost can even be negative—some interested parties are willing to pay you to get rid of certain pillars. All the heights h_i and costs w_i are integers.

What is the minimum possible cost of building the bridge that connects the first and last pillar?


The first line contains the number of pillars, n. The second line contains pillar heights h_i in the order, separated by a space. The third line contains w_i in the same order, the costs of removing pillars.


Output the minimum cost for building the bridge. Note that it can be negative.


  • 2 \le n \le 10^5
  • 0 \le h_i \le 10^6
  • 0 \le \left| w_i \right| \le 10^6
Subtask 1 (30 points)
  • n \le 1\,000
Subtask 2 (30 points)
  • optimal solution includes at most 2 additional pillars (besides the first and last)
  • \left| w_i \right| \le 20
Subtask 3 (40 points)
  • no additional constraints

Sample Input 1

3 8 7 1 6 6
0 -1 9 1 2 0

Sample Output 1



  • 1
    maxcruickshanks  commented on May 1, 2022, 2:29 a.m.

    Since the original data were weak, an additional test case was added to subtask 1.