Submission #1239993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239993		yenthuya	Building Bridges (CEOI17_building)	Pypy 3	0 / 100	133 ms	48784 KiB

building

def min_bridge_cost(n, h, w):
    INF = float('inf')
    
    # Prefix sum để tính nhanh tổng w
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + w[i]
    
    dp = [INF] * n
    dp[0] = 0  # Trụ đầu tiên bắt buộc

    for i in range(1, n):
        for j in range(i):
            cost = dp[j] + (h[i] - h[j])**2 + (prefix[i] - prefix[j+1])
            dp[i] = min(dp[i], cost)
    
    return dp[n-1]

Compilation message (stdout)

Compiling 'building.py'...

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

=======

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