Submission #1146154

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146154		wikidere	Building Bridges (CEOI17_building)	Pypy 3	0 / 100	148 ms	48756 KiB

building

def min_bridge_cost(n, h, w):
    # Compute prefix sums for w
    prefix_w = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix_w[i] = prefix_w[i - 1] + w[i - 1]
    
    # Initialize dp array
    dp = [float('inf')] * (n + 1)
    dp[1] = 0  # Cost to reach the first pillar is 0
    
    # Fill dp array
    for i in range(2, n + 1):
        for j in range(1, i):
            # Cost to build bridge from j to i
            bridge_cost = (h[i - 1] - h[j - 1]) ** 2
            # Cost to remove pillars between j and i
            removal_cost = prefix_w[i - 1] - prefix_w[j]
            # Total cost
            total_cost = dp[j] + bridge_cost + removal_cost
            # Update dp[i]
            if total_cost < dp[i]:
                dp[i] = total_cost
    
    return dp[n]

# Example usage:
n = 5
h = [1, 3, 2, 4, 5]
w = [1, 2, 3, 4, 5]
print(min_bridge_cost(n, h, w))  # Output the minimum cost

Compilation message (stdout)

Compiling 'building.py'...

=======
  adding: __main__.pyc (deflated 37%)

=======

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40