Submission #1146155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146155		wikidere	Building Bridges (CEOI17_building)	Pypy 3	0 / 100	195 ms	84636 KiB

building

from collections import deque

def min_bridge_cost(n, h, w):
    # Prefix sum of w
    prefixW = [0] * n
    prefixW[0] = w[0]
    for i in range(1, n):
        prefixW[i] = prefixW[i - 1] + w[i]

    # dp[i] stores the minimum cost to reach pillar i
    dp = [float('inf')] * n
    dp[0] = 0  # Base case: first pillar is always included

    # Monotonic deque to optimize DP recurrence
    dq = deque([(0, 0)])  # Stores (index, dp value)

    def cost(i, j):
        """ Returns cost of moving from i to j """
        return (h[i] - h[j]) ** 2 + (prefixW[j - 1] - prefixW[i])

    for j in range(1, n):
        # Remove from deque if it's no longer optimal
        while len(dq) > 1 and cost(dq[0][0], j) >= cost(dq[1][0], j):
            dq.popleft()

        # Compute dp[j] using best available i
        best_i = dq[0][0]
        dp[j] = dp[best_i] + cost(best_i, j)

        # Maintain the deque
        while len(dq) > 1:
            i1, dp1 = dq[-2]
            i2, dp2 = dq[-1]
            if (dp[j] - dp2) * (i2 - i1) < (dp2 - dp1) * (j - i2):
                dq.pop()
            else:
                break
        dq.append((j, dp[j]))

    return dp[-1]

# Example usage
n = int(input())
h = list(map(int, input().split()))
w = list(map(int, input().split()))
print(min_bridge_cost(n, h, w))

Compilation message (stdout)

Compiling 'building.py'...

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

=======

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